[AGC029F] Construction of a tree

给定 $n-1$ 个点集（全集为 $\{1,2,\ldots,n\}$），从每个集合内选两个点连边，使得最后形成一棵树。输出方案。 $n-1$ 条边按顺序对应这 $n-1$ 个集合输出。 $n \leq 10^5$，$\sum |S| \leq 2 \times 10^5$。

[problemUrl]: https://atcoder.jp/contests/agc029/tasks/agc029_f $ \{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} $

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 $ 以下である。