说明

一棵树如下图所示，每个节点都标有 $\{1,2,...,16\}$的整数，节点 $8$ 是树根。

若节点 $x$ 位于根和 $y$ 之间的路径中，则 $x$ 是 $y$ 的祖先，节点也是自己的祖先。

如下图：$8$、$4$、$10$ 和 $16$ 是 $16$ 的祖先，$8$、$4$、$6$ 和 $7$ 是 $7$ 的祖先。

若 $x$ 是 $y$ 的祖先和 $z$ 的祖先，则 $x$ 被称为 $y$ 和 $z$ 的公共祖先，如：$8$ 和 $4$ 是 $16$ 和 $7$ 的公共祖先。

若 $x$ 是 $y$ 和 $z$ 的公共祖先并且在它们的公共祖先中最接近 $y$ 和 $z$，则 $x$ 被称为 $y$ 和 $z$ 的最近公共祖先，如：$16$ 和 $7$ 的最近公共祖先是 $4$。

若 $y$ 是 $z$ 的祖先，则 $y$ 和 $z$ 的最近公共祖先是 $y$，如：$4$ 和 $12$ 的最近公共祖先是 $4$。

编写一个程序，找到树中两个不同节点的最近公共祖先。

输入

第$1$行包含一个整数 $T$，表示测试用例的数量。

每个测试用例的第 $1$ 行都包含整数 $N(2≤N≤10,000)$，表示树中的节点数。节点用$1,2, ..., N$标记。

接下来的 $N-1$ 行，每行都包含一对表示边的整数，第 $1$ 个整数是第 $2$ 个整数的父节点（有 $N$ 个节点的树则恰好有 $N-1$ 条边）。

每个测试用例的最后一行都包含两个不同的整数，求其最近公共祖先。

输出

对每个测试用例，都单行输出两个节点的最近公共祖先。

样例

2
16
1 14
8 5
10 16
5 9
4 6
8 4
4 10
1 13
6 15
10 11
6 7
10 2
16 3
8 1
16 12
16 7
5
2 3
3 4
3 1
1 5
3 5

4
3

来源

POJ1330