节点的最近公共祖先
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
树是一种很常见的数据结构。现在徐老师面临一个问题，在一个有 n 个节点的树上，节点编号分别是 1 ... n 。徐老师想知道一些节点之间的最近公共祖先是那些节点。
输入格式
第一行输入一个整数 n （ 2 <= n<= 10,000 ），表示树上有 n 个节点。
接下来的 n-1 行，每行输入两个整数 a ， b （ 1 <= a,b <= n ）代表节点 a ， b 之间有一条 a 到 b 边，a 是 b 的父亲。
接下来输入一个整数 q ，代表徐老师的 q 次提问。（ 1 <= q<= 1,000 ）
接下来的 q 行，每行输入两个整数 c ， d （ 1 <= c,d <= n ）代表询问 c ， d 两个节点的最近公共祖先。
输出格式
对于每次询问，输出公共祖先的节点编号，占一行。
样例
5
1 2
2 3
1 4
2 5
2
3 4
3 51
2
