题目描述

我们有一个有 $N$ 个点和 $M$ 条边的连通无向图，可能有重边或自环。

边 $i$ 连接点 $A_i$ 和 $B_i$，上面写着一个字符 $C_i$。

我们要选一条从点 $1$ 到点 $N$ 的路径（点和边可以多次经过）的路径，把经过的边上字符依次写下来，构成一个字符串。

判断能否构造一个回文字符串。若能，求出它的最小长度。 限制

	$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。

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

	样例二

输入 
4 5

1 1 a

1 2 a

2 3 a

3 4 b

4 4 a

输出 
5
	样例三

输入 
3 4

1 1 a

1 2 a

2 3 b

3 3 b

输出 
-1```