問題一覧 > 教育的問題

No.2914 正閉路検出

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 26
作問者 : 👑 p-adicp-adic / テスター : ShirotsumeShirotsume
1 ProblemId : 10509 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-07-31 08:03:14

問題文

入力の最初に 22 個の正整数 N,MN, M が与えられます。

ある村には NN 個の広場と、それらを双方向に結ぶ MM 本の道があります。

広場は NN 以下の各正整数 ii で番号付けられ広場 ii と呼ばれます。

道は MM 以下の各正整数 jj で番号付けられ道 jj と呼ばれ、道 jj は広場 uju_j と広場 vjv_j を結んでいます(uj,vju_j, v_j は相異なる NN 以下の正整数)。

 

直進大好きbotはこの村の道を直進するのが大好きなbotです。直進大好きbotはどの道をどの方向に直進したかに従って爽快度という整数値が変化します。

具体的には、MM 以下の任意の正整数 jj に対し、直進大好きbotが道 jj を広場 uju_j から広場 vjv_j に向かって直進した時は爽快度が wjw_j 増え、逆向きに直進した時は爽快度が wjw_j 減ります(wjw_j は非負整数)。

 

直進大好きbotはこの村のある広場を出発して道だけを直進してもとの広場に戻ってくる経路であって、以下の 22 条件を満たすものを爽快な経路と呼んで探し求めています。

  • 経路中に同じ道を方向問わず二度は通らない。
  • 出発時点の爽快度より帰還時点の爽快度が高くなる。

あなたが直進大好きbotの代わりに爽快な経路を探してあげてください。

入力

入力は以下の形式で標準入力から 1+M1 + M 行で与えられます:

  • 11 行目に N,MN, M が半角空白区切りで与えられます。
  • MM 以下の各正整数 jj に対し、1+j1 + j 行目に uj,vj,wju_j , v_j , w_j が半角空白区切りで与えられます。
NN MM
u1u_1 v1v_1 w1w_1
\vdots
uMu_M vMv_M wMw_M

制約

入力は以下の制約を満たします:

  • NN2N1052 \leq N \leq 10^5 を満たす整数である。
  • MM1M1051 \leq M \leq 10^5 を満たす整数である。
  • MM 以下の任意の正整数 jj に対し、
    • uj,vju_j, v_jujvju_j \neq v_j かつ 1ujN1 \leq u_j \leq N かつ 1vjN1 \leq v_j \leq N を満たす整数である。
    • wjw_j0wj1050 \leq w_j \leq 10^5 を満たす整数である。

出力

爽快な経路が存在しない場合は-1と出力してください。

-1

爽快な経路が存在する場合は、その 11 つを以下の形式で 33 行で出力してください:

  • 11 行目に、通る道の本数を表す正整数 LL を出力してください。
  • 22 行目に、出発する広場に対応する番号を出力してください。
  • 33 行目に、通る順に LL 本の道に対応する番号を半角空白区切りで出力してください。
LL
(出発する広場に対応する番号)
(11 本目に通る道に対応する番号) \cdots (LL 本目に通る道に対応する番号)

この問題はスペシャルジャッジ問題です。正解が複数ある場合はどれを出力しても構いません。

ただし出力の形式は上述したものを守ってください。例えば末尾に余計な空白を入れた場合のジャッジの挙動は保証されません。

最後に改行してください。

サンプル

サンプル1
入力
2 1
1 2 1
出力
-1

爽快な経路は存在しません。道 11 が広場 11 と広場 22 を結んでいますが、他に道はないので、どの広場を出発しても同じ道を二度通らずには元の広場に戻って来れません。

サンプル2
入力
2 2
1 2 0
2 1 1

このように同一の広場の組を複数の道が結んでいることもあることに注意してください。

出力
2
1
1 2

11 が広場 11 と広場 22 を結んでおり、道 11 をどちら向きに直進しても爽快度は変化しません。

22 が広場 22 と広場 11 を結んでおり、広場 22 から広場 11 に向かって道 22 を直進すると爽快度が 11 増え、逆向きに直進すると爽快度が 11 減ります。

従って広場 11 から出発して道 11、道 22 の順に直進することで爽快度を 11 増やした状態で広場 11 に戻ることが可能です。

この他にも例えば

2
2
2 1

と出力しても正解となります。

サンプル3
入力
3 3
1 2 1
2 3 2
1 3 3
出力
-1

爽快な経路は存在しません。例えば広場 11 から出発して道 11、道 22、道 33 の順に直進して広場 11 に戻っても最終的な爽快度の変化は 1+23=01 + 2 - 3 = 0 です。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。