CF566E Restoring Map

考古学家发现了一些关于古代“Treeland”国度的信息。我们已知 Treeland 由 $n$ 个城市构成，通过 $n-1$ 条道路相连，形成一个任意两个城市之间都可以通过道路到达的连通网络。但这些道路的具体设计已佚失。考古学家们仅能依赖保存下来的关于“相近城市”的记录。 在 Treeland，如果两个城市之间，可以仅经过至多两条道路互达，则称它们为“相近城市”。同时，一个城市总是与自己相近。在最近的考古发掘中，考古学家们找到了 $n$ 份记录，每份记录包含了与某个城市相近的城市编号列表。但不幸的是，这些记录并不能让我们明确知道列表中的序号和实际所对应的原始城市编号。 请你帮助考古学家们，恢复出一个 Treeland 的公路网结构，使其符合所给的“相近城市”信息。

第一行包含整数 $n$（$2 \le n \le 1000$），表示国家的城市数。 接下来的 $n$ 行描述考古学家发现的“相近城市”列表。每一行以一个整数 $k$（$1 \le k \le n$）开头，表示列表中“相近城市”的数量，后面紧跟着 $k$ 个城市编号，均为 $1$ 到 $n$ 之间的不同整数。 保证给出的数据至少存在一种满足条件的道路设计方案。

输出 $n-1$ 行，每行两个整数 $a_i, b_i$（$1 \le a_i, b_i \le n$，$a_i \ne b_i$），表示城市 $a_i$ 和 $b_i$ 之间有一条道路直接相连。 输出方案需满足输入中给定的“相近城市”要求。你可以按任意顺序输出各条道路，也可以按任意顺序输出每条道路所连接的两个城市编号。 若存在多种满足条件的方案，输出任意一种即可。

由 ChatGPT 5 翻译