F - Construct a Palindrome Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

N 頂点 M 辺の、単純とは限らない連結な無向グラフがあります。
辺 i は頂点 A_i と頂点 B_i を結んでおり、文字 C_i が書かれています。
頂点 1 から頂点 N へのパス (同じ辺や頂点を複数回通っても構わない) を 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 は英小文字
  • 与えられるグラフは連結である

入力

入力は以下の形式で標準入力から与えられる。

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

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

辺 1, 2, 3, 1, 2, 4, 5, 6, 7, 8 の順に通ると、出来上がる文字列は abcabbacba となり、回文となります。
これより短い回文を作ることはできないので、答えは 10 です。

入力例 2

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

出力例 2

5

辺 2, 3, 4, 5, 5 の順に通ると aabaa という文字列を作ることができ、これは回文です。
同じ辺や頂点を複数回通っても構わないことに注意してください。

入力例 3

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

出力例 3

-1

出来上がる文字列が回文となることはありません。

Score : 600 points

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.

Sample 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

Sample 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.

Sample Input 2

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

Sample 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.

Sample Input 3

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

Sample Output 3

-1

We cannot make a palindrome.