题目描述

给定 $N$ 个元素的集合 $\{1,2,\ldots,N\}$ 的 $N-1$ 个子集。第 $i$ 个集合记为 $E_i$。

你需要从每个集合 $E_i$ 中选择两个不同的元素 $u_i, v_i$，以 $\{1,2,\ldots,N\}$ 作为顶点集，$(u_1,v_1),(u_2,v_2),\ldots,(u_{N-1},v_{N-1})$ 作为边集，构造一个 $N$ 个顶点、$N-1$ 条边的图 $T$。请判断是否可以通过合理选择 $u_i, v_i$，使得 $T$ 是一棵树。如果可以，请给出一组实际的 $(u_1,v_1),(u_2,v_2),\ldots,(u_{N-1},v_{N-1})$ 使得 $T$ 是一棵树。

输入格式

输入通过标准输入给出，格式如下：

$N$ $c_1$ $w_{1,1}$ $w_{1,2}$ $\ldots$ $w_{1,c_1}$ $:$ $c_2$ $w_{2,1}$ $w_{2,2}$ $\ldots$ $w_{2,c_2}$ $:$ $\ldots$ $:$ $c_{N-1}$ $w_{N-1,1}$ $w_{N-1,2}$ $\ldots$ $w_{N-1,c_{N-1}}$

其中，$c_i$ 表示 $E_i$ 的元素个数，$w_{i,1},\ldots,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_1,v_1),(u_2,v_2),\ldots,(u_{N-1},v_{N-1})$，格式如下：

$u_1$ $v_1$ $:$ $u_2$ $v_2$ $:$ $\ldots$ $:$ $u_{N-1}$ $v_{N-1}$

样例 1

输入

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

输出

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

输出

-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

输出

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

说明/提示

限制条件

• $2 \leq N \leq 10^5$
• $E_i$ 是 $\{1,2,\ldots,N\}$ 的子集。
• $|E_i| \geq 2$
• 所有 $|E_i|$ 的总和不超过 $2 \times 10^5$。

由 ChatGPT 4.1 翻译