問題一覧 > 通常問題

No.1612 I hate Construct a Palindrome

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 41
作問者 : 👑 ygussanyygussany / テスター : nok0nok0 tatyamtatyam
2 ProblemId : 6381 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-07-21 18:14:17

問題文

P.P. 君は回文恐怖症で,回文を見ると嫌な気持ちになります. そんな P.P. 君が,各辺に英小文字のラベルが付いた $N$ 頂点 $M$ 辺の連結な無向グラフに閉じ込められてしまいました. P.P. 君は今頂点 $1$ に居て,出口が頂点 $N$ にあることが分かっています.

P.P. 君のために,通った辺のラベルを順に並べてできる文字列が回文にならないような脱出経路を $1$ つ見つけてあげてください. 同じ頂点や同じ辺を複数回経由しても構いませんが,経路があまりにも長いと P.P. 君が可哀相なので,辺を通るのべ回数が $2N$ 以下のものを出力してください.

入力

$N$ $M$
$A_1\ \ B_1\ \ C_1$
$A_2\ \ B_2\ \ C_2$
    $\vdots$
$A_M\ \ B_M\ \ C_M$

  • $2 \le N \le 10^5$
  • $1 \le M \le 2 \times 10^5$
  • $1 \le A_i, B_i \le N,\ A_i \neq B_i \ \ (1 \le i \le M)$
  • $C_i \ (1 \le i \le M)$ は英小文字である.
  • 入力は $C_i$ $(1 \le i \le M)$ を除き全て整数である.
  • 与えられるグラフは連結無向グラフである.
  • 頂点には $1, 2, \dots, N$ の番号が付いている.
  • 辺には $1, 2, \dots, M$ の番号が付いている.
  • 辺 $i$ は頂点 $A_i$ と頂点 $B_i$ を双方向に結ぶ.

出力

通った辺のラベルを順に並べてできる文字列が回文にならないような頂点 $1$ から頂点 $N$ への移動経路であって,辺を通るのべ回数が $2N$ 以下のものを出力してください.

$1$ 行目には辺を通るのべ回数 $k$ を出力し,$2$ 行目から $k + 1$ 行目には通る辺の番号を順に出力してください. ただし,条件を満たす経路が存在しない場合には,$1$ 行目に $-1$ のみを出力してください.

サンプル

サンプル 1
入力
3 3
1 2 a
2 3 a
1 3 b
出力
3
1
1
3

辺 $1, 1, 3$ を通って $1 \to 2 \to 1 \to 3$ と移動すれば,ラベルを順に並べてできる文字列は aab となり,これは回文ではありません. 他にも,辺 $1, 2, 3, 3$ を通って aabb となる移動経路などもあり,いずれを出力しても正解となります.

辺 $3, 2, 1, 3$ を通って $1 \to 3 \to 2 \to 1 \to 3$ と移動すると,得られる文字列は baab となり,これは回文なので不適当です. また,辺 $3, 2, 1, 3, 3, 1, 2$ を通って $1 \to 3 \to 2 \to 1 \to 3 \to 1 \to 2 \to 3$ と移動すると,回文ではない baabbaa が得られますが,辺を通るのべ回数が $7 > 6 = 2N$ となり不適当です.

サンプル 2
入力
4 4
1 2 a
1 2 b
2 3 a
3 4 b
出力
3
1
3
4

P.P. 君が閉じ込められたグラフは単純であるとは限りません.

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

唯一の辺 $1$ を何度通っても aaa...a という回文にしかならず,残念ながら P.P. 君は脱出できません.

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