题目描述

在计算机科学与工程领域，有根树是一种广为人知的数据结构。一个示例如图所示：

在图中，每个节点都用集合 ${1, 2,...,16}$ 中的一个整数进行标记。节点 $8$ 是这棵树的根节点。如果节点 $x$ 在根节点到节点 $y$ 的路径上，那么节点 $x$ 就是节点 $y$ 的祖先。例如，节点 $4$ 是节点 $16$ 的祖先，节点 $10$ 也是节点 $16$ 的祖先。事实上，节点 $8$、$4$、$10$ 和 $16$ 都是节点 $16$ 的祖先。要记住，一个节点也是它自身的祖先。节点$8$、$4$、$6$ 和 $7$ 是节点 $7$ 的祖先。

如果节点$x$ 既是节点 $y$ 的祖先，又是节点 $z$ 的祖先，那么节点 $x$ 就被称为两个不同节点 $y$ 和 $z$ 的公共祖先。因此，节点 $8$ 和 $4$ 是节点 $16v 和节点 $7$ 的公共祖先。如果节点$x$ 是节点 $y$ 和节点 $z$ 的公共祖先，并且在它们的所有公共祖先中，$x$ 是距离 $y$ 和 $z$ 最近的，那么节点 $x$ 就被称为节点 $y$ 和节点 $z$ 的最近公共祖先。所以，节点 $16$ 和节点 $7$ 的最近公共祖先是节点 $4$，因为节点 $4$ 比节点 $8$ 更接近节点 $16$ 和节点 $7$。

再举一些例子，节点 $2$ 和节点 $3$ 的最近公共祖先是节点 $10$，节点 $6v 和节点 $13$ 的最近公共祖先是节点 $8$，节点 $4$ 和节点 $12$ 的最近公共祖先是节点 $4$。在最后这个例子中，如果 $y$ 是 $z$ 的祖先，那么 $y$ 和 $zv 的最近公共祖先就是$y$。

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

输入

输入由 $T$ 个测试用例组成。测试用例的数量 $T$ 会在输入文件的第一行给出。每个测试用例以一个整数$N$ 开始，$N$ 表示树中节点的数量，$2 <= N <= 10,000$。这些节点用整数 $1, 2,..., N$ 进行标记。接下来的 $N - 1$ 行，每行包含一对整数，表示一条边——第一个整数是第二个整数的父节点。请注意，一棵有 $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

来源

2002年大田竞赛