팰린드롬 보행

면접 대비

시간 제한2초메모리 제한512 MB

요약

간선마다 소문자가 적힌 무방향 그래프에서 꼭짓점 0에서 1로 가는 보행 중 간선 문자를 이어 붙인 문자열이 회문이 되는 가장 짧은 보행의 길이를 구하고, 없으면 -1을 출력한다.

난이도: 보통10점 중 7점
유형: BFS, 그래프, 문자열, 동적 계획법
정답자: 아직 제출이 없습니다

문제

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

보행은 같은 정점과 같은 간선을 여러 번 지나도 되는 경로다. 보행의 길이는 지나간 간선의 개수다. 보행의 값은 지나간 순서대로 간선의 소문자를 이어 붙인 문자열이다.

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

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

입력

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

둘째 줄부터 $M$ 개의 줄에 간선 정보 $a$ , $b$ , $c$ 가 공백으로 구분되어 주어진다. $a$ 와 $b$ 는 간선이 잇는 두 정점의 번호이고, $c$ 는 그 간선에 쓰여 있는 알파벳 소문자다. 간선의 두 끝점은 항상 다르고, 두 정점을 잇는 간선은 최대 하나다. 그래프가 연결되어 있다는 보장은 없다.

출력

첫째 줄에 0번 정점에서 1번 정점으로 가는 보행 중 값이 팰린드롬인 것의 최소 길이를 출력한다. 그런 보행이 없으면 -1을 출력한다.

예제3

예제 1
입력
```
5 5
2 0 a
2 1 b
0 3 x
3 4 y
4 1 x
```
예상 출력
```
3
```
예제 2
입력
```
5 5
2 0 a
2 1 b
0 3 x
3 4 y
4 1 z
```
예상 출력
```
-1
```

예제 3

입력

예상 출력