Construct a Palindrome

题目描述

我们有一个连通的无向图，包含 $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

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$ 是小写英文字母。 给定的图是连通的。沿着边的顺序 $1, 2, 3, 1, 2, 4, 5, 6, 7, 8$ 行走，可以得到字符串 $abcabbacba$，它是回文串。
不可能构造更短的回文串，所以答案是 $10$.
沿着边的顺序 $2, 3, 4, 5, 5$ 行走，可以得到字符串 $aabaa$，它是回文串。
注意允许重复经过相同的边和顶点。
我们无法构造回文串。

标签: AtCoder|abc197F

来源

AtCoder|abc197F