{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"$LCA$ ( $Lowest\\ Common\\ Ancestors$ ),即最近公共祖先,是指在有根树中,找出某两个节点 $u$ 和 $v$ 最近的公共祖先。(若 $u$ 为 $v$ 的祖先或者 $v$ 为 $u$ 的祖先,则 $LCA(u,v)$ 就是作为祖先的那个节点)。\r\n\r\n现在有一棵以 $1$ 为根的有根树,树上一共有 $n$ 个节点。现在有 $m$ 次查询,每次询问两个节点的 $LCA$ 。\r\n\r\n![题2599.png](https://upload.51nod.com/Problem/2599/Description_1.png)\r\n\r\n如图所示的数据中, $LCA(3,5)\u003d1,LCA(2,5)\u003d2,LCA(3,4)\u003d1,LCA(2,4)\u003d2,LCA(5,5)\u003d5$ 。"}},{"title":"Input","value":{"format":"MD","content":"第 $1$ 行:一个正整数 $n$ ,表示树上节点的个数。 $(1\\le n\\le 1000)$\r\n第 $2\\sim n$ 行:每行两个正整数 $u,v$ ,表示节点 $u$ 到节点 $v$ 有一条边。 $(1\\le u,v\\le n)$\r\n第 $n+1$ 行:一个正整数 $m$ ,表示查询的次数。 $(1\\le m\\le 1000)$\r\n第 $n+2\\sim n+m+1$ 行:每行两个正整数 $a,b$ ,表示要查询的两个节点的编号。 $(1\\le a,b\\le n)$"}},{"title":"Output","value":{"format":"MD","content":"对于每个询问,输出一个正整数表示答案,并换行。"}},{"title":"Sample 1","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\u003e5\n1 2\n1 3\n2 4\n2 5\n5\n3 5\n2 5\n3 4\n2 4\n5 5\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n2\n1\n2\n5\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}