No.2914 正閉路検出
タグ : / 解いたユーザー数 26
作問者 : 👑 p-adic / テスター : Shirotsume
問題文
入力の最初に 個の正整数 が与えられます。
ある村には 個の広場と、それらを双方向に結ぶ 本の道があります。
広場は 以下の各正整数 で番号付けられ広場 と呼ばれます。
道は 以下の各正整数 で番号付けられ道 と呼ばれ、道 は広場 と広場 を結んでいます( は相異なる 以下の正整数)。
直進大好きbotはこの村の道を直進するのが大好きなbotです。直進大好きbotはどの道をどの方向に直進したかに従って爽快度という整数値が変化します。
具体的には、 以下の任意の正整数 に対し、直進大好きbotが道 を広場 から広場 に向かって直進した時は爽快度が 増え、逆向きに直進した時は爽快度が 減ります( は非負整数)。
直進大好きbotはこの村のある広場を出発して道だけを直進してもとの広場に戻ってくる経路であって、以下の 条件を満たすものを爽快な経路と呼んで探し求めています。
- 経路中に同じ道を方向問わず二度は通らない。
- 出発時点の爽快度より帰還時点の爽快度が高くなる。
あなたが直進大好きbotの代わりに爽快な経路を探してあげてください。
入力
入力は以下の形式で標準入力から 行で与えられます:
- 行目に が半角空白区切りで与えられます。
- 以下の各正整数 に対し、 行目に が半角空白区切りで与えられます。
制約
入力は以下の制約を満たします:
- は を満たす整数である。
- は を満たす整数である。
- 以下の任意の正整数 に対し、
- は かつ かつ を満たす整数である。
- は を満たす整数である。
出力
爽快な経路が存在しない場合は-1
と出力してください。
-1
爽快な経路が存在する場合は、その つを以下の形式で 行で出力してください:
- 行目に、通る道の本数を表す正整数 を出力してください。
- 行目に、出発する広場に対応する番号を出力してください。
- 行目に、通る順に 本の道に対応する番号を半角空白区切りで出力してください。
(出発する広場に対応する番号) ( 本目に通る道に対応する番号) ( 本目に通る道に対応する番号)
この問題はスペシャルジャッジ問題です。正解が複数ある場合はどれを出力しても構いません。
ただし出力の形式は上述したものを守ってください。例えば末尾に余計な空白を入れた場合のジャッジの挙動は保証されません。
最後に改行してください。
サンプル
サンプル1
入力
2 1 1 2 1
出力
-1
爽快な経路は存在しません。道 が広場 と広場 を結んでいますが、他に道はないので、どの広場を出発しても同じ道を二度通らずには元の広場に戻って来れません。
サンプル2
入力
2 2 1 2 0 2 1 1
このように同一の広場の組を複数の道が結んでいることもあることに注意してください。
出力
2 1 1 2
道 が広場 と広場 を結んでおり、道 をどちら向きに直進しても爽快度は変化しません。
道 が広場 と広場 を結んでおり、広場 から広場 に向かって道 を直進すると爽快度が 増え、逆向きに直進すると爽快度が 減ります。
従って広場 から出発して道 、道 の順に直進することで爽快度を 増やした状態で広場 に戻ることが可能です。
この他にも例えば
2 2 2 1
と出力しても正解となります。
サンプル3
入力
3 3 1 2 1 2 3 2 1 3 3
出力
-1
爽快な経路は存在しません。例えば広場 から出発して道 、道 、道 の順に直進して広場 に戻っても最終的な爽快度の変化は です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。