智乃的LCA
题号：NC229662
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述


智乃学习了LCA，给定一颗有根树，对于树上的任意一点x来说，树上从根节点到x节点所构成简单路径上所有的节点均为x的祖先（包括x节点本身）。那么对于树上任意两点x,y,如果z同时是x和y的祖先，则称z为x和y的公共祖先。
x和y的最近公共祖先指所有x和y的公共祖先中深度最高的点，记为lca(x,y)。
如果树结构确定，并且x和y的值给定，那么lca(x,y)的值将只与根节点有关。
所以就可以定义无根树的lca(root,x,y)表示求以root为根时，x和y的最近公共祖先。
请你编写程序，计算在无根树结构给定情况下的lca(root,x,y)。

输入描述:

第一行是一个整数，表示树有n个节点。
接下来n-1行每行两个正整数表示树上的一条边。
然后是一行一个整数，表示有m个查询。
接下来m行，每行三个整数表示询问lca(root,x,y)。

输出描述:

请输出m行，每行一个正整数，表示询问的答案。
示例1

输入

复制 
11
1 2
2 3
3 4
3 8
1 5
5 9
5 7
5 6
6 11
10 6
12
2 4 1
10 7 6
11 8 7
1 5 2
7 6 11
10 1 9
1 5 7
7 5 1
5 7 1
1 4 11
5 9 10
5 10 11

输出

复制 
2
6
5
1
6
5
5
5
5
1
5
6

备注:

树结构如下
lca(2,4,1)=2
lca(10,7,6)=6
lca(11,8,7)=5
lca(1,5,2)=1
lca(7,6,11)=6
lca(10,1,9)=5
lca(1,5,7)=5
lca(7,5,1)=5
lca(5,7,1)=5
lca(1,4,11)=1
lca(5,9,10)=5
lca(2,4,1)=2
lca(5,10,11)=6
 
对于样例1，n,m<=100，树结构为随机生成。
对于样例2,3，n,m<=1000,树结构为随机生成。
对于样例4,n,m<=100000，树为完全二叉树，1为树根，且保证查询中root恒等于1。
对于样例5, n,m<=100000，树为完全二叉树。
对于样例6,7,n,m<=100000，树完全退化为一条树链。
对于样例8,9，n,m<=100000，树为随机生成。
对于样例10，树的最长链>50000，但不完全退化为一条链。
对于全部的样例，保证查询中x≠y