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/A

N/A

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