단어 일치시키기

두 단어 $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를 출력합니다.