构造回文路径

题目描述

有一个 $N$ 个顶点、$M$ 条边的不一定简单的连通无向图。

边 $i$ 连接顶点 $A_i$ 和顶点 $B_i$，上面写着字符 $C_i$。

选择一条从顶点 $1$ 到顶点 $N$ 的路径（可以多次经过同一条边或同一个顶点），把经过的边上写着的字符按顺序排列来构造一个字符串。

判断这个字符串是否可能成为回文，如果可能，求这样的回文长度的最小可能值。

输入格式

输入按以下格式从标准输入给出：

$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。

样例

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

按边的顺序 $1, 2, 3, 1, 2, 4, 5, 6, 7, 8$ 经过时，构造出的字符串为 abcabbacba，是回文。

无法构造出比这更短的回文，所以答案是 $10$。

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

5

按边的顺序 $2, 3, 4, 5, 5$ 经过时，可以构造出字符串 aabaa，它是回文。

注意可以多次经过同一条边或同一个顶点。

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$ 是小写英文字母
• 给定的图是连通的