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 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 y2xN-1 yN-1
Q
a1 b1
a2 b2aQ 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

Submitting .cpp to 'closedpath'


You're not logged in! Click here to login

Time Limit: 1 Seconds
Memory Limit: 1024MB
Your best score: 0
Source: Dunjudge Archive

Subtask Score
1 30
2 70
3 0