{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"根树是计算机科学和工程中一个众所周知的数据结构。下面是一个例子:\r\u003cbr\u003e\r\u003cbr\u003e\u003cimg src\u003d\"CDN_BASE_URL/a4cf40017a91cfbd4f81b13b267ec9ee?v\u003d1710901635\"\u003e\r\u003cbr\u003e在图中,每个节点都标有来自{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是节点16和7的共同祖先。如果x是y和z的共同祖先并且在y和z的共同祖先中离y和z最近,那么节点x被称为节点y和z的最近共同祖先。因此,节点16和7的最近共同祖先是节点4。节点4比节点8更接近节点16和7。\r\u003cbr\u003e\r\u003cbr\u003e对于其他例子,节点2和3的最近共同祖先是节点10,节点6和13的最近共同祖先是节点8,节点4和12的最近共同祖先是节点4。在最后一个例子中,如果y是z的祖先,那么y和z的最近共同祖先是y。\r\u003cbr\u003e\r\u003cbr\u003e编写一个程序,找到树中两个不同节点的最近共同祖先。\r\u003cbr\u003e\r\u003cbr\u003e"}},{"title":"输入","value":{"format":"HTML","content":"输入包括T个测试用例。输入文件的第一行给出测试用例的数量T。每个测试用例以包含一个整数N的行开始,N是树中节点的数量,2≤N≤10,000。节点用整数1, 2,..., N标记。接下来的N-1行中,每行包含一对整数,表示一条边--第一个整数是第二个整数的父节点。请注意,具有N个节点的树恰好有N-1条边。每个测试用例的最后一行包含两个不同的整数,需要计算它们的最近共同祖先。"}},{"title":"输出","value":{"format":"HTML","content":"每个测试用例输出一行。该行应包含一个整数,即最近共同祖先。"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n16\r\n1 14\r\n8 5\r\n10 16\r\n5 9\r\n4 6\r\n8 4\r\n4 10\r\n1 13\r\n6 15\r\n10 11\r\n6 7\r\n10 2\r\n16 3\r\n8 1\r\n16 12\r\n16 7\r\n5\r\n2 3\r\n3 4\r\n3 1\r\n1 5\r\n3 5\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\r\n3\r\n\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}