问题说明

树是一种很常见的数据结构。现在小Q面临一个问题，在一个有 n 个节点的树上，节点编号分别是 1 ... n 。小Q想知道一些节点之间的最近公共祖先是哪个节点。

输入格式

第一行输入一个整数 n （ 2 <= n<= 10,000 ），表示树上有 n 个节点。

接下来的 n-1 行，每行输入两个整数 a ， b （ 1 <= a,b <= n ）代表节点 a ， b 之间有一条 a 到 b 边，a 是 b 的父亲。

接下来输入一个整数 q ，代表小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 5

1
2