Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

A New Tree

By fsshakkhor · Limits 1s, 512 MB

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

InputOutput
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.

Discussion

Statistics


85% Solution Ratio

EgorKulikovEarliest, Mar '20

mahdi.hasnatFastest, 0.2s

mahdi.hasnatLightest, 7.1 MB

serotoninShortest, 733B

Submit

Login to submit

Editorial

Observation: Look at the special property of this tree. If I select any range of edges, I will get a...

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.