← 返回题目列表

AtCoder · agc029_f

F. 构建一棵树

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

分数: 2200 点

问题陈述

你被给予 N-1 的子集 \{1,2,...,N\}。让 i-第组为 E_i.

让我们选择两个不同的元素 每组中的 u_i 和 v_i 从每组 E_i,并考虑一个图表 T 与 N 顶点和 N-1 边,其顶点集为 \{1,2,..,N\} 其边缘集是 (u_1,v_1),(u_2,v_2),...,(u_{N-1},v_{N-1})。 确定是否 T 通过正确决定可以成为一棵树 u_i 和 v_i。 如果可以的话,另外找到一个实例 (u_1,v_1),(u_2,v_2),...,(u_{N-1},v_{N-1}) 这样 T 实际上是一棵树。

约束

  • 2 \leq N \leq 10^5
  • E_i 是一个子集 \{1,2,..,N\}.
  • |E_i| \geq 2
  • 总和 |E_i| 最多是 2 \times 10^5.

输入

输入由标准输入按以下格式给出:

N
c_1 w_{1,1} w_{1,2} ... w_{1,c_1}
:
c_{N-1} w_{N-1,1} w_{N-1,2} ... w_{N-1,c_{N-1}}

在这里, c_i 代表元素的数量 E_i,和 w_{i,1},...,w_{i,c_i} 是 c_i 中的元素 c_i。 在这里, 2 \leq c_i \leq N, 1 \leq w_{i,j} \leq N,和 w_{i,j} \neq w_{i,k} (1 \leq j < k \leq c_i)保持。

输出

If T 不能是树,打印 -1;否则,打印以下选项 满足条件的 (u_i,v_i) ,格式如下:

u_1 v_1
:
u_{N-1} v_{N-1}

示例输入 1

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

示例输出 1

1 2
1 3
3 4
4 5

示例输入 2

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

示例输出 2

-1

示例输入 3

10
5 1 2 3 4 5
5 2 3 4 5 6
5 3 4 5 6 7
5 4 5 6 7 8
5 5 6 7 8 9
5 6 7 8 9 10
5 7 8 9 10 1
5 8 9 10 1 2
5 9 10 1 2 3

示例输出 3

1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10