题目描述

$N$ 頂点 $M$ 辺の、単純とは限らない連結な無向グラフがあります。
辺 $i$ は頂点 $A_i$ と頂点 $B_i$ を結んでおり、文字 $C_i$ が書かれています。
頂点 $1$ から頂点 $N$ へのパス (同じ辺や頂点を複数回通っても構わない) を $1$ つ選び、通る辺に書かれている文字を順に並べて文字列を作ります。
この文字列が回文になることはあるかを判定し、あるならばそのような回文の長さとして考えられる最小値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $A_1$ $B_1$ $C_1$ $A_2$ $B_2$ $C_2$ $A_3$ $B_3$ $C_3$ $\hspace{25pt}\ \vdots$ $A_M$ $B_M$ $C_M$

输出格式

作る文字列が回文になることがあるならば、そのような回文の長さの最小値を、ないならば -1 を出力せよ。

题目大意

有一个 $N$ 个点，$M$ 条边的无向联通图（图可能不是简单的，意味着可能有环）。第 $i$ 条边连接着点 $A_i$ 和 $B_i$，上面有个英文小写字母 $C_i$。一条从点 $1$ 开始，点 $N$ 结束的回文路径满足：在路径上的边顺次取出字母（也就是取出 $C_i$），最后形成的字符串回文（注意：这并不是简单路径，可能会经过重复的点或边）。求从 $1$ 开始 $N$ 结束的最短回文路径长度。

8 8
1 2 a
2 3 b
1 3 c
3 4 b
4 5 a
5 6 c
6 7 b
7 8 a

10

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

5

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

-1

提示

制約

• $2\ \le\ N\ \le\ 1000$
• $1\ \le\ M\ \le\ 1000$
• $1\ \le\ A_i\ \le\ N$
• $1\ \le\ B_i\ \le\ N$
• $C_i$ は英小文字
• 与えられるグラフは連結である

Sample Explanation 1

辺 $1,\ 2,\ 3,\ 1,\ 2,\ 4,\ 5,\ 6,\ 7,\ 8$ の順に通ると、出来上がる文字列は abcabbacba となり、回文となります。 これより短い回文を作ることはできないので、答えは $10$ です。

Sample Explanation 2

辺 $2,\ 3,\ 4,\ 5,\ 5$ の順に通ると aabaa という文字列を作ることができ、これは回文です。 同じ辺や頂点を複数回通っても構わないことに注意してください。

Sample Explanation 3

出来上がる文字列が回文となることはありません。