閉路の出力 2
(paizaランク B 相当)
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
1, ..., n の番号がついた n 個の頂点とそれらをつなぐ枝からなる無向グラフを考えます。ただし、自己ループと多重辺は考えません。
隣接リストとある枝 e が与えられます。このとき、e を通過する閉路をどれか 1 つ、枝 e を先頭にして出力してください。ただし、ここで枝 e を通過する閉路とは、e を構成する片方の頂点である e1 を出発し e を辿ってもう片方の e2 に移動したあと、他の頂点を辿って e1 に戻ってくる経路で、同じ頂点を 2 回以上通らないもののことを言います。そのような閉路が存在しない場合、-1 を出力してください。
- 入力される値
-
n e1 e2
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}
・ 1 行目に、頂点の個数を表す整数 n と、枝 e を構成する頂点の番号 e1 と e2 が与えられます。
・ 2i 行目には頂点 i に隣接している頂点の個数が与えられ、 2i+1 行目には頂点 i に隣接している頂点の番号が半角スペース区切りで与えられます。(1 ≦ i ≦ n)
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
枝 e を通過する閉路を 1 つ求め、その閉路が辿る頂点の番号を左から順番に e1, e2 となるように半角スペース区切りで 1 行で出力してください。一番左が e1、二番目が e2 で一番右が e1 となります。そのような閉路が存在しない場合、
-1を出力してください。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 3 ≦ n ≦ 12
・ 1 ≦ e1,e2 ≦ n
・ e1 ≠ e2
・ 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
-
4 2 3
3
2 3 4
3
1 3 4
3
1 2 4
3
1 2 3
- 出力例1
-
2 3 1 4 2
- 入力例2
-
5 5 3
2
2 5
3
1 3 5
3
2 4 5
2
3 5
4
1 2 3 4
- 出力例2
-
5 3 2 1 5
- 入力例3
-
6 1 2
1
2
5
1 3 4 5 6
4
2 4 5 6
4
2 3 5 6
4
2 3 4 6
4
2 3 4 5
- 出力例3
-
-1
