You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

[ABC197F] Construct a Palindrome

题面翻译

有一个 $N$ 个点，$M$ 条边的无向连通图（图可能不是简单的，意味着可能有环）。第 $i$ 条边连接着点 $A_i$ 和 $B_i$，上面有个英文小写字母 $C_i$。一条从点 $1$ 开始，点 $N$ 结束的回文路径满足：在路径上的边顺次取出字母（也就是取出 $C_i$），最后形成的字符串回文（注意：这并不是简单路径，可能会经过重复的点或边）。求从 $1$ 开始 $N$ 结束的最短回文路径长度。

输入格式

第一行两个整数 $N,M$ ，接下来 $M$ 行每行两个整数 $A_i,B_i$ 和一个小写英文字母 $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

样例输入 #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\ \le\ N\ \le\ 1000$
• $1\ \le\ M\ \le\ 1000$
• $1\ \le\ A_i\ \le\ N$
• $1\ \le\ B_i\ \le\ N$
• $C_i$ 是小写英文字母

样例解释 1

按 $1,\ 2,\ 3,\ 1,\ 2,\ 4,\ 5,\ 6,\ 7,\ 8$ 的顺序走，得到的字符串为 abcabbacba 是回文且是最短的，因此最小长度是 $10$ 。