Bob had N isolated nodes. He decided to connect the nodes by creating new edges and make a tree. So he planned and made a list of (N - 1) edges. The ith edge connects node Ui and node Vi.
Bob's list of edges has an interesting property. If he selects any range (L, R) and adds only the edges from Lth to Rth and then removes the isolated nodes, he will get a tree containing exactly (R - L + 2) nodes. This statement is true for all pair of (L, R) (1 ≤ L ≤ R ≤ N - 1).
Now Bob has Q queries to answer. In each query, he will be given two integers X and Y. If he connects all the edges from Xth to Yth and get a tree, what will be the diameter of this tree?
Input
The first line of input contains an integer N (2 ≤ N ≤ 105), denoting the total number of nodes.
Each of the next (N - 1) lines contain two integers Ui (1 ≤ Ui ≤ N) and Vi (1 ≤ Vi ≤ N), denoting an edge.
The next line contains an integer Q (1 ≤ Q ≤ 106), denoting the number of queries.
Each of the next Q lines contain two integers X and Y (1 ≤ X ≤ Y ≤ N - 1).
Output
For each query, print the diameter of the tree.
Sample
| Input | Output |
|---|---|
4 1 2 3 1 4 1 2 3 3 1 3 | 1 2 |
The diameter of a tree is the maximum distance between any pair of nodes in the tree.
The distance between two nodes in a tree is the number of edges in the simple path between them.
An isolated node is a node which does not contain any edge.
