分数: 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