AtCoder Beginner Contest 197（Sponsored by Panasonic）
翻译中…
Problem Statement
翻译中…
We have a connected undirected graph with $N$ vertices and $M$ edges, which is not necessarily simple.
Edge $i$ connects Vertex $A_i$ and Vertex $B_i$, and has a character $C_i$ written on it.
Let us make a string by choosing a path from Vertex $1$ to Vertex $N$ (possibly with repetitions of the same edge and vertex) and arrange the characters written on the edges in that path.
Determine whether this string can be a palindrome. If it can, find the minimum possible length of such a palindrome.
翻译中…
Constraints
翻译中…
$2 \le N \le 1000$$1 \le M \le 1000$$1 \le A_i \le N$$1 \le B_i \le N$$C_i$is a lowercase English letter.- The given graph is connected.
翻译中…
Input
翻译中…
Input is given from Standard Input in the following format:
翻译中…
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翻译中…
Output
翻译中…
If a palindrome can be made, print the minimum possible length of such a palindrome; otherwise, print -1.
翻译中…
样例
Input #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
Output #1
10
By traversing the edges in the order $1, 2, 3, 1, 2, 4, 5, 6, 7, 8$, we can make a string `abcabbacba`, which is a palindrome.
It is impossible to make a shorter palindrome, so the answer is $10$.
Input #2
4 5
1 1 a
1 2 a
2 3 a
3 4 b
4 4 a
Output #2
5
By traversing the edges in the order $2, 3, 4, 5, 5$, we can make a string `aabaa`, which is a palindrome.
Note that repetitions of the same edge and vertex are allowed.
Input #3
3 4
1 1 a
1 2 a
2 3 b
3 3 b
Output #3
-1
We cannot make a palindrome.
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。