12950번 - 팰린드롬 보행

정점 N개로 이루어진 무방향 그래프 G가 주어진다. G의 정점은 0번부터 N-1번까지 번호가 매겨져 있다. 그래프의 간선에는 알파벳 소문자가 하나 쓰여 있다.

그래프의 보행은 같은 정점과 간선을 여러 번 방문할 수 있는 경로이다. 보행의 길이는 포함되어 있는 간선의 개수와 같다. 그래프 보행의 값은 포함되어 있는 간선에 쓰여 있는 소문자를 이어 붙인 것이며, 포함된 순서를 지켜야 한다.

팰린드롬은 앞에서 부터 읽을 때랑 뒤에서 부터 읽을 때가 같은 문자열을 말한다. "a", "abba", "racecar"는 팰린드롬이다.

0번 정점에서 1번 정점으로 가는 보행 중에서 보행의 값이 팰린드롬인 것 중에서 길이가 가장 짧은 것을 찾는 프로그램을 작성하시오.

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N(N-1)/2)

둘째 줄부터 M개의 줄에는 그래프의 간선 정보 a, b, c가 주어진다. a와 b는 정점 번호이고, c는 간선에 쓰여 있는 알파벳이다. 간선의 양 끝점은 항상 다르며, 두 정점을 연결하는 간선은 최대 하나이다.

첫째 줄에 그래프의 보행 중에서 값이 팰린드롬인 것 중에 길이가 제일 짧은 것의 길이를 출력한다. 그러한 보행이 없으면 -1을 출력한다.