#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

### 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`. 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

_{i},y_{i})`Q`candidate edges we want to add, the

`j`one connecting

^{th}`(a`. For each of the

_{i},b_{i})`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`^{5}`1 ≤ Q ≤ 10`^{5}`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:

Nx_{1}y_{1}x：_{2}y_{2}x_{N-1}y_{N-1}Qa_{1}b_{1}a：_{2}b_{2}a_{Q}b_{Q}

### 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

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 30 | 10 | 1s | 256MB | Minimum |

2 | 70 | 35 | 1s | 256MB | Minimum |

3 | 0 | 3 | 1s | 256MB | Minimum |

### Judge Compile Command

g++-7 ans.cpp -o closedpath -Wall -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512