分数: 600 点
问题陈述
我们有一个连通的无向图 N 顶点和 M 边缘,这不一定简单。
边缘 i 连接顶点 A_i 和顶点 B_i,并且有一个字符 C_i 。
让我们通过从 Vertex 选择路径来创建一个字符串 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.
示例输入 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
示例输出 1
10
通过按顺序遍历边 1, 2, 3, 1, 2, 4, 5, 6, 7, 8,我们可以制作一个字符串 abcabbacba,这是一个回文。
不可能制作更短的回文,所以答案是 10.
示例输入 2
4 5 1 1 a 1 2 a 2 3 a 3 4 b 4 4 a
示例输出 2
5
通过按顺序遍历边 2, 3, 4, 5, 5,我们可以制作一个字符串 aabaa,这是一个回文。
请注意,允许重复相同的边和顶点。
示例输入 3
3 4 1 1 a 1 2 a 2 3 b 3 3 b
示例输出 3
-1
我们无法制作回文。