問題文

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$ のみを出力してください．

サンプル

3 3
1 2 a
2 3 a
1 3 b

3
1
1
3

4 4
1 2 a
1 2 b
2 3 a
3 4 b

3
1
3
4

2 1
1 2 a

-1