← 返回题目列表

AtCoder · abc197_f

F. 构造一个回文

中文机器翻译题面 查看原题

分数: 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

我们无法制作回文。