F - 构造回文串

得分：$600$ 分

问题描述

我们有一个有 $N$ 个顶点和 $M$ 条边的无向连通图，图不一定是简单图。
边 $i$ 连接顶点 $A_i$ 和顶点 $B_i$，并且在边上有一个字符 $C_i$。
我们通过选择一个从顶点 $1$ 到顶点 $N$ 的路径（可能出现相同的边和顶点），并将该路径上边上的字符排列起来，形成一个字符串。
确定该字符串是否可以是回文串。如果可以，找到这样一个回文串的最小可能长度。

约束

• $2 \le N \le 1000$
• $1 \le M \le 1000$
• $1 \le A_i \le N$
• $1 \le B_i \le N$
• $C_i$ 是小写英文字母。
• 给定的图是连通图。

输入

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

$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

我们无法构造一个回文串。