题目描述

编写一个程序，输入一棵有根树和若干顶点对。对于每对顶点 $(u,v)$，程序需要确定它们在树中的最近公共祖先。最近公共祖先是指同时是 $u$ 和 $v$ 的祖先且深度最大的节点（一个节点可以是自己的祖先，例如在图1中，节点 $2$ 的祖先是 $2$ 和 $5$）。

输入格式

数据从标准输入读取，格式如下：

1. 树的描述：

   • 第一行：节点数量 $nr\_of\_vertices$（$n \leq 900$）
   • 接下来的 $n$ 行：每个节点的描述，格式为

     vertex:(nr_of_successors) successor1 successor2 ... successorn
     

     其中，$vertex$ 是节点编号（$1$ 到 $n$），$nr\_of\_successors$ 是子节点数量，$successor1$ 到 $successorn$ 是子节点列表。

2. 顶点对列表：

   • 第一行：顶点对数量 $nr\_of\_pairs$
   • 接下来的行：每对顶点 $(u\ v)$，可以自由换行或添加空格。

输入包含多组数据（至少一组）。

输出格式

对于每个公共祖先，输出其编号及其作为最近公共祖先的次数，按节点编号升序排列，格式为：

ancestor:times

输入样例 1

5
5:(3) 1 4 2
1:(0)
4:(0)
2:(1) 3
3:(0)
6
(1 5) (1 4) (4 2)
      (2 3)
(1 3) (4 3)

输出样例 1

2:1
5:5

提示

输入数据量可能较大，建议使用 scanf 读取。

来源

Southeastern Europe 2000