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?
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).
For each query, print the diameter of the tree.
4 1 2 3 1 4 1 2 3 3 1 3
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.
Login to submit
Observation: Look at the special property of this tree. If I select any range of edges, I will get a...