全域木の出力 2（paizaランク B 相当）

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

下記の問題をプログラミングしてみよう！

1, ..., n の番号がついた n 個の頂点とそれらをつなぐ枝からなる無向グラフを考えます。ただし、自己ループと多重辺は考えません。

隣接リストと枝集合 E が与えられます。このとき、この隣接リストから E に含まれない枝を n-1 個選んで全域木を構成し、出力してください。
E の枝を使わなければ全域木を構成できない場合は -1 と出力してください。

入力される値

n
v_1
a_{1,1} a_{1,2} ... a_{1,v_1}
v_2
a_{2,1} ... a_{2,v_2}
...
v_n
a_{n,1} ... a_{n,v_n}
k
e_1 d_1
e_2 d_2
...

・ 1 行目に、頂点の個数を表す整数 n が与えられます。

・ 2i 行目には頂点 i に隣接している頂点の個数が与えられ、 2i+1 行目には頂点 i に隣接している頂点の番号が半角スペース区切りで与えられます。(1 ≦ i ≦ n)

・ 2n+2 行目には全域木に使用できない枝集合 E の要素数 k が与えられ、続く k 行では、その枝を表す端点が半角スペース区切りで与えられます。

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

期待する出力: 全域木を構成するために選んだ E に含まれない枝をそれぞれ 1 つずつ改行して出力してください。各行は枝の端点である 2 つの頂点の番号を半角スペースで区切って出力してください。各行の頂点の順番は問いません。また、出力する枝の順番も問いません。全域木であるため合計行数は n-1 行となります。E の枝を使わなければ全域木を構成できない場合は -1 と出力してください。

条件: すべてのテストケースにおいて、以下の条件をみたします。

・ 3 ≦ n ≦ 20

・ 1 ≦ v_i ≦ n-1 (1 ≦ i ≦ n)

・ 1 ≦ i ≦ n について

・ v_i = 1 のとき : 1 ≦ a_{i,1} ≦ n

・ v_i > 1 のとき : 1 ≦ a_{i,j} < a_{i,j+1} ≦ n (1 ≦ j ≦ (v_i)-1)

・ 1 ≦ k ≦ 1/2Σv_i - (n-1)

・ 1 ≦ e_i < d_i ≦ n (1 ≦ i ≦ k)

すべての頂点が連結していることが保証されています。

入力例1: 4
1
2
3
1 3 4
2
2 4
2
2 3
1
2 3

出力例1: 1 2
2 4
4 3

入力例2: 5
2
2 5
3
1 3 5
3
2 4 5
2
3 5
4
1 2 3 4
3
2 3
3 5
4 5

出力例2: -1

問題一覧へ戻る