closedpath
Problem Statement
You are given an undirected, connected graph with N vertices numbered from 1 to N and N-1 edges, with the ith edge connecting vertices (xi,yi). 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 jth one connecting (ai,bi). 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 ≤ 105
- 1 ≤ Q ≤ 105
- 1 ≤ xi, yi, aj, bj ≤ N
- For all i, xi ≠ yi
- For all i ≠ j, (xi,yi) ≠ (xj,yj)
- For all i, j, (xi,yi) ≠ (aj,bj)
- 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