文理学院程序设计在线练习


生物进化

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 49   Accepted Submission(s): 27
Problem Description

在研究生物进化中,常用一种类似树状分支的图形来概括各种(类)生物之间的亲缘关系。下面就是一棵生物进化树。

树可分为 有根树(rooted tree)和 无根树(unrooted tree)两类,为了便于讨论,这里我们只涉及有根树。有根树是具有方向的树,选择其中某个确定的节点,将其作为树中所有物种的共同祖先(根)。有根树这种结构在计算机科学中极为常见,尤其适用表述层次结构。下面就是在计算机科学中常见的有根树的示意图(注意:我们把树根放在了图的顶部,树叶放在了底部)。

给定2种生物的种类,请你判断,它们具有哪一个相同的祖先,当然由于树根一定满足这个要求,可能的答案不唯一,这里只要求你给出离这2种生物最近的祖先。
例如:对于上图,2,3的最近祖先是10,而9,7的最近祖先是8,特别需要注意,10,11的最近祖先是10。

Input

输入数据首先包含一个整数T(1<=T<=20),表示测试实例的个数,然后是T组测试数据。
每组测试数据的第一行是1个整数n(节点(物种)从1到n编号,2<=n<=1000),表示节点总数,然后是n-1个整数对a, b(1<=a,b<=n,且a<>b),表示a是b的父节点(直接祖先)。请注意,n个节点(物种)的有根树恰好具有n-1条边。接下来是最多不超过1000次的询问(各占一行),每个询问包含2个互不相同的整数c,d(1<=c,d<=n),请你求解c,d的最近祖先。当c==d==0时,表示本组测试结束。

具体格式请参看Sample。

Output

对于每组测试数据, 分别按行输出求得的最近祖先.

Sample Input
2
11
8 4
8 5
8 10
5 9
5 6
10 2
10 3
10 1
2 7
2 11
6 11
7 10
0 0
5
2 3
5 1
5 2
5 4
1 3
5 1
0 0
Sample Output
8
10
5
5
Author

flx

Source

zscas第三届程序设计竞赛