단어 일치시키기

시간 제한1초메모리 제한128 MB

요약

주어진 단어들을 x와 y 뒤에 원하는 만큼 이어 붙여 두 단어를 같게 만들고, 필요한 최소 연산 횟수를 구하거나 불가능하면 NIE를 출력한다.

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

문제

두 단어 $x$ , $y$ 와 $k$ 개의 단어로 이루어진 열 $(w_1, w_2, \ldots, w_k)$ 가 주어집니다. 연산 $w \oplus w_i$ 는 단어 $w$ 의 뒤에 열의 단어 $w_i$ ( $1 \le i \le k$ )를 이어 붙이는 것(연결)을 뜻합니다. 즉 $w$ 바로 뒤에 $w_i$ 를 쓰는 것입니다.

열의 단어들을 $x$ 와 $y$ 의 뒤에 (각 단어를 원하는 만큼 여러 번, 어느 쪽에든 자유롭게) 이어 붙여서 두 단어를 완전히 똑같게 만들 수 있는지 판단하세요. 만들 수 있다면 필요한 $\oplus$ 연산의 최소 횟수를, 만들 수 없다면 NIE(폴란드어로 "아니오")를 출력합니다.

예를 들어 단어 abba와 ab는 열 baaabad, aa, badccaa, cc를 이용해 일치시킬 수 있습니다. abba에는 aa와 badccaa를 붙이고, ab에는 차례로 baaabad, cc, aa를 붙이면 양쪽 모두 abbaaabadccaa가 됩니다. 이때 사용한 연산은 모두 $2 + 3 = 5$ 번입니다.

입력

첫째 줄에 열의 길이인 양의 정수 $k$ ( $1 \le k \le 40$ )가 주어집니다. 둘째 줄과 셋째 줄에는 각각 단어 $x$ 와 $y$ 의 정보가, 이어지는 $k$ 개의 줄에는 열의 단어 $w_1, w_2, \ldots, w_k$ 의 정보가 한 줄에 하나씩 주어집니다. 각 단어의 정보는 단어의 길이(자연수)와 단어 자체가 공백 하나로 구분되어 주어집니다. 모든 단어는 소문자 a부터 z까지로만 이루어지며 길이는 2,000 이하입니다. 주어지는 모든 단어의 길이의 합은 5,000 이하입니다.

출력

$x$ 와 $y$ 를 일치시킬 수 있으면 필요한 $\oplus$ 연산의 최소 횟수(음이 아닌 정수)를 출력합니다. 일치시킬 수 없으면 NIE를 출력합니다.

예제2

예제 1

입력

4
4 abba
2 ab
7 baaabad
2 aa
7 badccaa
2 cc

예상 출력

예제 2
입력
```
4
1 a
2 ab
2 bb
2 ab
2 ba
2 aa
```
예상 출력
```
NIE
```