closedpath

closedpath

Problem Statement

You are given an undirected, connected graph with N vertices numbered from 1 to N and N-1 edges, with the i^th edge connecting vertices (x_i,y_i). In graph theory language, such a graph is called a tree, and it has the property that there does not exist a cycle in this graph. If we add an edge to this graph, a single cycle is formed. There are Q candidate edges we want to add, the j^th one connecting (a_i,b_i). For each of the Q queries, output the length of the cycle when this edge is added to the graph. Note that each of the Q queries are independed of each other, and that no edges are actually added to the graph.

Constraints

• 1 ≤ N ≤ 10⁵
• 1 ≤ Q ≤ 10⁵
• 1 ≤ x_i, y_i, a_j, b_j ≤ N
• For all i, x_i ≠ y_i
• For all i ≠ j, (x_i,y_i) ≠ (x_j,y_j)
• For all i, j, (x_i,y_i) ≠ (a_j,b_j)
• The given graph forms a tree.

Partial Scores

• In the test set worth 30 points, Q = 1.

Input

Input is given from Standard Input in the following format:

N
x1 y1
x2 y2
：
xN-1 yN-1
Q
a1 b1
a2 b2
：
aQ bQ

Output

For each of the Q queries, output a single integer, the length of the cycle when the corresponding edge is added to the graph.

Sample Input 1

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

Sample Output 1

3
4
3

Sample Input 2

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

Sample Output 2

3
4
5
6

Sample Input 3

7
3 1
2 1
2 4
2 5
3 6
3 7
5
4 5
1 6
5 6
4 7
5 3

Sample Output 3

3
3
5
5
4