AT_agc029_f [AGC029F] Construction of a tree

[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\

$ T $ を木とすることができない場合は `-1` を出力せよ。そうでない場合は以下の形式に従って条件を満たす $ (u_i,v_i) $ を出力せよ。 > $ u_1 $ $ v_1 $ $ : $ $ u_{N-1} $ $ v_{N-1} $

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