회문 생성기

면접 대비

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

요약

사전의 단어와 허용된 인접 쌍만으로 만들 수 있는 가장 긴 회문의 길이를 구합니다. 회문이 없으면 0을, 길이에 제한이 없으면 -1을 출력합니다.

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

문제

회문 장인은 이른 아침에 일을 시작한다. 맑은 공기 속에서 회문을 다듬을 수 있다.

이날 아침 그는 국제 회문 장인 대회에 출품할 작품을 만들고 있다.

회문을 만들 때 그는 특별한 사전을 사용한다. 이 사전에는 단어의 집합과 단어의 순서쌍의 집합이 들어 있다. 회문에 쓰는 모든 단어와 연속한 단어의 순서쌍은 반드시 사전에 있어야 한다.

사전은 이미 가지고 있다. 그가 만들 수 있는 회문이 얼마나 긴지 알아보자.

입력

첫 줄에 두 정수 N ( $1 \le N \le 100$ )과 M ( $0 \le M \le 1000$ )이 주어진다. N은 사전에 있는 단어의 개수이고, M은 단어 순서쌍의 개수이다.

다음 N개 줄은 사용할 수 있는 단어를 나타낸다. i번째 줄(1부터 시작)에는 i번 단어가 적혀 있다. 단어는 소문자로만 이루어지며, 길이는 1 이상 10 이하이다.

다음 M개 줄은 연속해서 사용할 수 있는 단어 순서쌍을 나타낸다. j번째 줄(1부터 시작)에는 두 정수 Xj와 Yj ( $1 \le X_j, Y_j \le N$ )가 적혀 있다. 회문에서 Xj번 단어 바로 뒤에 Yj번 단어가 올 수 있다는 뜻이다.

출력

만들 수 있는 회문 길이의 최댓값을 한 줄에 출력한다. 회문을 하나도 만들 수 없으면 0을 출력한다. 임의로 긴 회문을 만들 수 있으면 -1을 출력한다.

예제3

예제 1
입력
```
2 2
ab
ba
1 1
1 2
```
예상 출력
```
4
```
예제 2
입력
```
2 2
ab
ba
1 1
2 2
```
예상 출력
```
0
```
예제 3
입력
```
2 2
ab
a
1 1
1 2
```
예상 출력
```
-1
```