Problem Description

You are given a connected undirected graph consisting of $ n $ vertices and $ n-1 $ edges. Each vertex is numbered from $ 1 $ to $ n $.

In graph theory, a graph satisfying these conditions is called a tree, which has the property of containing no cycles. Consider adding one additional edge $ (a,b) $ that is not originally in the graph. This new graph will contain exactly one cycle. Your task is to output the length of this cycle (the number of edges in the cycle) for each such additional edge candidate. Note that there are several candidate additional edges, and you are given $ Q $ of them. You need to output the answer for all of them.

Input Format

The input is given from the standard input in the following format:

$ N $ $x_1\ y_1$ $x_2\ y_2$ ： $x_{N-1}\ y_{N-1}$ $ Q $ $a_1\ b_1$ $a_2\ b_2$ ： $a_{Q}\ b_{Q}$

• The first line contains an integer $N\ (1≦N≦100,000)$, representing the number of vertices in the graph.
• The next $ N-1 $ lines contain the edge information of the graph. The $ i $th line contains two integers $ x_i $ and $ y_i $ separated by a space, representing the vertices connected by the edge.
• The next line contains an integer $Q\ (1≦Q≦100,000)$, representing the number of additional edge candidates.
• The next $ Q $ lines contain the information of the $ i $th additional edge candidate. The $ i $th line contains two integers $ a_i $ and $ b_i $ separated by a space, representing the vertices connected by the additional edge.
• All given edges connect existing vertices.
• The graph does not contain self-loops. That is, for any $ i $, $ x_i≠y_i $.
• The graph does not contain multiple edges. That is, for any $ i,j(i≠j) $, either $ x_i≠x_j $ or $ y_i≠y_j $.
• The additional edges are guaranteed to be edges not originally in the graph and are not self-loops.

Output Format

For each additional edge candidate, output the length of the cycle formed when that edge is added to the original graph, from the first line to the $ Q $th line in order. Ensure a newline at the end of the output.

Sample Input and Output

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

Notes/Hints

Partial Points

This problem has two datasets, each with partial points assigned:

• If you correctly solve dataset 1 where $ Q=1 $, you will be awarded $ 30 $ points.
• If you correctly solve dataset 2 without additional constraints, you will be awarded an additional $ 70 $ points, separate from the points for dataset 1.

Sample Explanation 1

The diagram is as follows:

见题面 Input 部分

见题面 Output 部分