5934: 进阶2.2.1最近公共祖先

一棵树如下图所示，每个节点都标有｛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~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