pog loves szh III

pog在与szh玩游戏，首先pog在纸上画了一棵有根树，这里我们定义1为这棵树的根，然后szh在这棵树中选了若干个点，想让pog帮忙找找这些点的最近公共祖先在哪里，一个点为S的最近公共祖先当且仅当以该点为根的子树包含S中的所有点，且该点深度最大。然而，这个问题是十分困难的，出于szh对pog的爱，他决定只找编号连续的点，即$l_i$~$r_i$。

若干组数据(不超过$3$组$n \geq 10000$或$Q \geq 10000$)。
每组数据第一行一个整数$n(1 \leq n \leq 300000)$，表示树的节点个数。
接下来$n-1$行，每行两个数$A_i，B_i$，表示存在一条边连接这两个节点。
接下来一行一个数$Q(1 \leq Q \leq 300000)$，表示有$Q$组询问。
接下来Q行每行两个数$l_i,r_i(1 \leq li \leq ri \leq n)$，表示询问编号为$l_i$~$r_i$的点的最近公共祖先。

对于每组的每个询问，输出一行，表示编号为li~ri的点的最近公共祖先的编号。

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

珍爱生命，远离爆栈。