# Gardening

Limits 7s, 512 MB

You are given a tree with $N$ vertices. Here, a tree is an undirected graph in which any two vertices are connected by exactly one simple path, or equivalently a connected acyclic undirected graph. A tree with $N$ vertices, contains exactly $N - 1$ undirected edges.

You have to process $Q$ queries. In each of the query, you will be given 3 positive integers $R$, $U$and $V$. You have to perform the following operations on your tree —

• Add an edge between $U$ and $V$.

• Remove an edge such that the resulting graph is still a tree. You can also remove the newly added edge.

• Minimize the sum of distance of every vertex from the vertex $R$. Formally , let $d_i$ denote the shortest distance from vertex $R$ to vertex $i$. You have to minimize $\sum_{1\le i\le n}^{} d_i$

• Print the Minimized Sum

Note that, Each query is independent which means operations in one query does not affect the other queries.

## Input

The first line of the input will contain an integer, $N$ $(2 \leq N \leq 3 \times 10^5)$ which denotes the number of vertices of the tree.

Each of the next $N - 1$ lines will contain $2$ space-separated integers $u_i$ and $v_i$$(1 \leq u_i, v_i \leq N)$, indicating an edge between vertices $u_i$ and $v_i$. It is guaranteed that the given edges form a tree.

The next line will contain an integer $Q$ $(1\leq Q\leq 3\times 10 ^ 5)$, the number of queries.

Finally, each of the next $Q$ line will contain $3$ integers $R_i$,$U_i$ and $V_i$$(1 \leq R_i, U_i, V_i \leq N)$ — representing each query.

## Output

Print the answer for each query in separate lines.

## Samples

InputOutput
5
2 1
3 1
4 3
5 1
4
4 2 1
2 1 2
4 2 1
4 4 1

9
8
9
6

InputOutput
6
1 2
2 3
3 4
4 6
1 5
2
1 5 6
1 5 4

9
9

InputOutput
10
2 1
3 2
4 3
5 3
6 4
7 2
8 4
9 8
10 7
2
1 10 4
9 1 9

27
23