题目描述

$\{1,2,...,N\}$ の部分集合が $N-1$ 個与えられます。$i$ 番目の集合を $E_i$ とします。

各集合 $E_i$ から相異なる $2$ 要素 $u_i,v_i$ を選び、$\{1,2,..,N\}$ を頂点集合、 $(u_1,v_1),(u_2,v_2),...,(u_{N-1},v_{N-1})$ を辺集合とするような、$N$ 頂点 $N-1$ 辺グラフ $T$ を考えます。 うまく $u_i,v_i$ を定めることにより、$T$ を木にすることができるかどうか判定してください。 さらに可能な場合は、$T$ が実際に木となるような $(u_1,v_1),(u_2,v_2),...,(u_{N-1},v_{N-1})$ を一つ求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$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}$

题目大意

给定 $n-1$ 个点集（全集为 $\{1,2,\ldots,n\}$），从每个集合内选两个点连边，使得最后形成一棵树。输出方案。

$n-1$ 条边按顺序对应这 $n-1$ 个集合输出。

$n \leq 10^5$，$\sum |S| \leq 2 \times 10^5$。

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

1 2
1 3
3 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

提示

制約

• $2\ \leq\ N\ \leq\ 10^5$
• $E_i$ は $\{1,2,..,N\}$ の部分集合である。
• $|E_i|\ \geq\ 2$
• $|E_i|$ の和は $2\ \times\ 10^5$ 以下である。