Palindrome Walk

You are given an undirected graph $G$ with $N$ vertices. The vertices are numbered 0 through $N-1$, and one lowercase letter is written on each edge.

A walk is a route that may pass through the same vertex and the same edge more than once. The length of a walk is the number of edges it uses. The value of a walk is the string obtained by concatenating the letters on its edges in the order they are used.

A palindrome is a string that reads the same forward and backward. "a", "abba", and "racecar" are palindromes.

Among the walks that start at vertex 0 and end at vertex 1, find the ones whose value is a palindrome, and report the length of the shortest such walk.

The first line contains the number of vertices $N$ and the number of edges $M$. ($2 \le N \le 20$, $1 \le M \le N(N-1)/2$)

Each of the next $M$ lines contains one edge as $a$, $b$, $c$, separated by spaces. $a$ and $b$ are the numbers of the two vertices the edge joins, and $c$ is the lowercase letter written on that edge. The two endpoints of an edge are always different, and at most one edge joins any pair of vertices. The graph is not guaranteed to be connected.

Print the minimum length of a walk from vertex 0 to vertex 1 whose value is a palindrome. Print -1 if no such walk exists.