pog loves szh III

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 !

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$).

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

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

1
1
3
3
1

Be careful about stack overflow.

BestCoder Round #43