← 返回题目列表

Codeforces · 847/L

L. Berland SU计算机网络

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

Berland 州立大学的计算机网络中有 n 个路由器,编号从 1 到 n。一些路由器对通过跳线连接。信息可以通过跳线双向传输。网络的布置方式使得任何两个路由器之间(直接或通过其他路由器)都可以进行通信。网络中没有环路,因此每对路由器之间只有一条通过跳线的路径。

不幸的是,管理员丢失了网络的确切拓扑。为了恢复它,收集了以下辅助信息。

对于直接连接到路由器i的每个接插线p,相对于i位于接插线p后面的路由器列表是已知的。换句话说,从 p 到路由器 i 的所有路由器路径都是已知的。因此,对于每个路由器 i 都有 ki 列表,其中 ki 是连接到 i 的跳线数量。

例如,假设网络由连接在链 1 - 2 - 3 中的三个路由器组成。则:

- 路由器 1:对于连接到第一个路由器的单个跳线,有一个包含两个路由器的列表:2 和 3;
- 路由器 2:对于连接到第二个路由器的每条跳线,都有一个列表:一个列表包含路由器 1,另一个列表包含路由器 3;
- 路由器 3:对于连接到第三个路由器的单个跳线,有一个包含两个路由器的列表:1 和 2。

你的任务是帮助管理员恢复网络拓扑,即: e.识别通过跳线直接连接的所有路由器对。

输入

第一行包含一个整数 n (2 ≤ n ≤ 1000) — 网络中路由器的数量。

以下 n 行中的第 i 行包含路由器 i 的列表的描述。

每个列表的描述都以其中路由器的数量开始。然后是符号“:”,然后给出列表中的路由器编号。这些数字以逗号分隔。列表由符号“-”分隔。

可以保证,对于每个路由器 i,其列表中的路由器总数等于 n - 1,并且每个路由器的列表中的所有数字都是不同的。对于每个路由器 i 列表不包含数字 i。

输出

如果不存在解,则打印 -1。

在另一种情况下,打印到第一行 n - 1 — 网络中的跳线总数。在接下来的 n - 1 行中,每一行打印两个整数——通过跳线直接连接的路由器。每条跳线的信息必须打印一次。

跳线和路由器可以按任意顺序打印。

示例

输入 #1

3
2:3,2
1:1-1:3
2:1,2

输出 #1

2
2 1
2 3

输入 #2

5
4:2,5,3,4
1:4-1:1-2:5,3
4:4,5,2,1
4:2,1,3,5
1:3-3:4,2,1

输出 #2

4
2 1
2 4
5 2
3 5

输入 #3

3
1:2-1:3
1:1-1:3
1:1-1:2

输出 #3

-1

注意

语句中分析第一个例子。

第二个例子的答案如图所示。

第一个路由器有一个列表,其中包含所有其他路由器。第二个路由器有三个列表:第一个 - 单个路由器 4,第二个 - 单个路由器 1,第三个 - 两个路由器 3 和 5。第三个路由器有一个列表,其中包含所有其他路由器。第四个路由器也有一个列表,其中包含所有其他路由器。第五个路由器有两个列表:第一个 - 单个路由器 3,第二个 - 三个路由器 1、2 和 4。