{"raw_statement":[{"iden":"problem statement","content":"We have a connected undirected graph with $N$ vertices and $M$ edges, which is not necessarily simple.  \nEdge $i$ connects Vertex $A_i$ and Vertex $B_i$, and has a character $C_i$ written on it.  \nLet 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.  \nDetermine whether this string can be a palindrome. If it can, find the minimum possible length of such a palindrome."},{"iden":"constraints","content":"*   $2 \\le N \\le 1000$\n*   $1 \\le M \\le 1000$\n*   $1 \\le A_i \\le N$\n*   $1 \\le B_i \\le N$\n*   $C_i$ is a lowercase English letter.\n*   The given graph is connected."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $B_1$ $C_1$\n$A_2$ $B_2$ $C_2$\n$A_3$ $B_3$ $C_3$\n$\\hspace{25pt} \\vdots$\n$A_M$ $B_M$ $C_M$"},{"iden":"sample input 1","content":"8 8\n1 2 a\n2 3 b\n1 3 c\n3 4 b\n4 5 a\n5 6 c\n6 7 b\n7 8 a"},{"iden":"sample output 1","content":"10\n\nBy 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.  \nIt is impossible to make a shorter palindrome, so the answer is $10$."},{"iden":"sample input 2","content":"4 5\n1 1 a\n1 2 a\n2 3 a\n3 4 b\n4 4 a"},{"iden":"sample output 2","content":"5\n\nBy traversing the edges in the order $2, 3, 4, 5, 5$, we can make a string `aabaa`, which is a palindrome.  \nNote that repetitions of the same edge and vertex are allowed."},{"iden":"sample input 3","content":"3 4\n1 1 a\n1 2 a\n2 3 b\n3 3 b"},{"iden":"sample output 3","content":"\\-1\n\nWe cannot make a palindrome."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}