pog loves szh III

Time Limit: 12000/6000 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)

Description

Pog and Szh are playing games. Firstly Pog draw a tree on the paper. Here we define 1 as the root of the tree.Then Szh choose some nodes from the tree. He wants Pog helps to find the least common ancestor (LCA) of these node.The question is too difficult for Pog.So he decided to simplify the problems.The nodes picked are consecutive numbers from $l_i$ to $r_i$ $([l_i, r_i])$.

Hint : You should be careful about stack overflow !

Input

Several groups of data (no more than 3 groups,$n \geq 10000$ or $Q \geq 10000$).

The following line contains ans integers,$n (2 \leq n \leq 300000)$.

AT The following $n-1$ line, two integers are $b_i$ and $c_i$ at every line, it shows an edge connecting $b_i$ and $c_i$.

The following line contains ans integers,$Q (Q \leq 300000)$.

AT The following $Q$ line contains two integers li and ri($1 \leq li \leq ri \leq n$).

Output

For each case,output $Q$ integers means the LCA of $[l_i,r_i]$.

Sample Input

5 1 2 1 3 3 4 4 5 5 1 2 2 3 3 4 3 5 1 5

Sample Output

1 1 3 3 1
Hint
Be careful about stack overflow.

Hint

hujie

Source

BestCoder Round #43

提交代码