分数 : $2200$ 分

问题陈述

给定 $N-1$ 个子集 $\{1,2,...,N\}$。设第 $i$ 个集合为 $E_i$。

我们从每个集合 $E_i$ 中选择两个不同的元素 $u_i$ 和 $v_i$，并考虑一个图 $T$，该图有 $N$ 个顶点和 $N-1$ 条边，其顶点集为 $\{1,2,..,N\}$，边集为 $(u_1,v_1),(u_2,v_2),...,(u_{N-1},v_{N-1})$。 确定是否可以通过适当地选择 $u_i$ 和 $v_i$ 使得 $T$ 成为一棵树。 如果可以，进一步找出一组 $(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}$ 是 $E_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$)。

输出

如果 $T$ 不能成为一棵树，打印 -1；否则，打印满足条件的 $(u_i,v_i)$ 的选择，格式如下：

$u_1$ $v_1$

$:$

$u_{N-1}$ $v_{N-1}$

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

1 2
1 3
3 4
4 5

例如，如果选择如下：

• 从 $E_1$ 中选择 $(1, 2)$。
• 从 $E_2$ 中选择 $(1, 3)$。
• 从 $E_3$ 中选择 $(3, 4)$。
• 从 $E_4$ 中选择 $(4, 5)$。

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

-1

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

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