AT_abc197_f [ABC197F] Construct a Palindrome

题目描述

有一个包含 $N$ 个顶点和 $M$ 条边的连通无向图（不一定是简单图）。
第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$，并且上面写有一个字母 $C_i$。
你可以从顶点 $1$ 走到顶点 $N$，路径上可以多次经过同一条边或顶点。
请任选一条这样的路径，将经过的边上的字母按顺序排列，得到一个字符串。
请判断是否存在使得该字符串为回文串的路径。如果存在，求所有可能的回文串中最短的长度；如果不存在，输出 $-1$。

输入格式

输入以如下格式从标准输入读入。

$N$ $M$
$A_1$ $B_1$ $C_1$
$A_2$ $B_2$ $C_2$
$A_3$ $B_3$ $C_3$
$\vdots$
$A_M$ $B_M$ $C_M$

输出格式

如果可以构造出回文串，输出所有可能回文串长度的最小值；否则输出 $-1$。

输入输出样例 #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

输入输出样例 #2

输入 #2

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

输出 #2

5

输入输出样例 #3

输入 #3

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

输出 #3

-1

说明/提示

限制条件

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

样例解释 1

按边 $1, 2, 3, 1, 2, 4, 5, 6, 7, 8$ 的顺序经过，得到的字符串为 abcabbacba，这是一个回文串。无法构造更短的回文串，因此答案为 $10$。

样例解释 2

按边 $2, 3, 4, 5, 5$ 的顺序经过，可以得到字符串 aabaa，这是一个回文串。注意可以多次经过同一条边或顶点。

样例解释 3

无法构造出回文串。

由 ChatGPT 4.1 翻译