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