构造回文路径

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

给定一个包含 $N$ 个顶点和 $M$ 条边的连通无向图，图中可能有自环和重边。第 $i$ 条边连接顶点 $A_i$ 与顶点 $B_i$，边上写有一个小写英文字母 $C_i$。

你需要从顶点 $1$ 走到顶点 $N$，途中可以多次经过同一条边或同一个顶点。把依次经过的边上的字母连接起来，会得到一个字符串。

请判断能否使这个字符串成为回文串。若可以，求最短回文串的长度；否则输出 $-1$。

输入格式

第一行包含两个整数 $N,M$。

接下来 $M$ 行，第 $i$ 行包含两个整数 $A_i,B_i$ 和一个小写英文字母 $C_i$，表示一条无向边。

输出格式

若能构造出回文串，输出最短长度；否则输出 $-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

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

样例输出 2

5

样例输入 3

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

样例输出 3

-1

样例解释

在样例 1 中，依次经过编号为 $1,2,3,1,2,4,5,6,7,8$ 的边，可以得到回文串 abcabbacba，其长度为 $10$，且不存在更短的方案。

在样例 2 中，可以得到回文串 aabaa。注意，同一条边或同一个顶点可以经过多次。

样例 3 中不存在满足条件的路径。

数据范围

• $2\le N\le 1000$；
• $1\le M\le 1000$；
• $1\le A_i,B_i\le N$；
• $C_i$ 是小写英文字母；
• 输入图连通。