{"problem":{"name":"Construct a Palindrome","description":{"content":"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","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc197_f"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nInput 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc197_f","tags":[],"sample_group":[["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","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$."],["4 5\n1 1 a\n1 2 a\n2 3 a\n3 4 b\n4 4 a","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."],["3 4\n1 1 a\n1 2 a\n2 3 b\n3 3 b","\\-1\n\nWe cannot make a palindrome."]],"created_at":"2026-03-03 11:01:13"}}