«数据输入:
由文件input.txt给出输入数据。第一行有1 个正整
数n,表示给定的树有n个顶点,编号为1,2,…,n
。编号为1 的顶点是树根。接下来的n 行中,第i+1 行
描述与i 个顶点相关联的子结点的信息。每行的第一个
正整数k表示该顶点的儿子结点数。其后k个数中,每
1 个数表示1个儿子结点的编号。当k=0 时表示相应的
结点是叶结点。
文件的第n+2 行是1 个正整数m,表示要计算最
近公共祖先的m个结点对。接下来的m行,每行2 个
正整数,是要计算最近公共祖先的结点编号。
«结果输出:
将计算出的m个结点对的最近公共祖先结点编号
输出到文件output.txt。每行3 个正整数,前2 个是结
点对编号,第3 个是它们的最近公共祖先结点编号。