← 返回题目列表

Codeforces · 566/E

E. 恢复地图

中文机器翻译题面 查看原题

考古学家发现了一些关于树地古老土地的信息。我们确信 Treeland 由 n 个城市组成,由 n - 1 条道路连接,这样你就可以沿着道路从每个城市到达任何其他城市。然而,有关林地道路具体设计的信息已经丢失。考古学家唯一可以利用的是保存下来的有关附近城市的信息。

如果可以通过最多两条道路从一个城市移动到另一个城市,则称 Treeland 的两个城市为邻近。此外,一座城市被认为距离其自身较近。在最近的发掘中,考古学家发现了一组 n 个笔记,每个笔记代表一个城市列表,靠近该国 n 个城市中的一些。然而,不幸的是,找到的记录都无法让您了解城市在列表中的排列顺序以及列表中列出的靠近该城市的城市。

帮助考古学家恢复任何符合所发现信息的 Treeland 地图变体。

输入

第一行包含整数 n (2 ≤ n ≤ 1000) — 该国城市的数量。

接下来的 n 行描述了找到的附近城市的列表。每个列表从数字 k (1 ≤ k ≤ n) 开始,表示列表中城市的数量,后跟 k 个城市编号。每个列表中的所有数字都是不同的。

保证给定的信息确定至少一个可能的路线图。

输出

打印 n - 1 对代表国家道路的数字。第i行必须包含两个整数ai,bi(1≤ai,bi≤n,ai≠bi),表明城市ai和bi之间有一条路。

您打印的答案必须满足输入的邻近城市的描述。您可以按任何顺序打印各国的道路。由道路连接的城市也可以按任何顺序打印。

如果有多个好的答案,您可以打印其中任何一个。

示例

输入 #1

5
4 3 2 4 1
5 5 3 2 4 1
5 4 2 1 5 3
4 2 1 4 3
3 1 4 5

输出 #1

1 4
1 2
1 3
4 5

输入 #2

6
5 6 1 3 4 2
5 2 1 3 4 6
6 3 6 2 5 4 1
6 6 1 2 5 3 4
3 5 2 4
5 3 1 2 4 6

输出 #2

2 4
1 2
2 3
2 6
4 5