바벨

조앙지뉴와 마리아지냐는 외국어 수업에 푹 빠진 남매로, 둘 다 여러 학원에서 서로 다른 언어를 배우고 있다. 집에 오면 문법, 어휘, 여러 나라의 문화 같은 이야기를 나눈다. 그러다 어떤 단어는 뜻이 꼭 같지 않더라도 둘 이상의 언어에 공통으로 있다는 사실을 알게 되었다. 예를 들어 "amigo"는 포르투갈어와 스페인어에 모두 있고 뜻도 같다. "date"는 프랑스어와 영어에 모두 있지만 뜻이 다를 수 있는데, 영어의 "date"는 달력의 날짜뿐 아니라 데이트도 뜻하기 때문이다. "red"는 스페인어로 그물을, 영어로 빨간색을 뜻한다. "actual"은 영어로 실제의, 스페인어로 (포르투갈어처럼) 현재의라는 뜻이다.

이 발견에 신이 난 남매는 떠오르는 공통 단어를 모두 공책에 적고, 각 단어에 언어 한 쌍을 짝지어 두었다. 관찰력이 좋은 조앙지뉴는 마리아지냐에게 도전 과제를 냈다. 출발 언어와 도착 언어가 주어지면 단어를 차례로 적되, 첫 단어는 반드시 출발 언어에 속하고 마지막 단어는 도착 언어에 속해야 한다. 이웃한 두 단어는 반드시 같은 언어에 함께 속해야 한다. 예를 들어 출발 언어가 포르투갈어이고 도착 언어가 프랑스어라면 마리아지냐는 amigo actual date(포르투갈어/스페인어, 스페인어/영어, 영어/프랑스어)라고 적을 수 있다.

정확히 말하면 단어열 $w_1, w_2, \ldots, w_k$ ($k \ge 1$)가 올바르려면 언어 $L_0, L_1, \ldots, L_k$가 존재해서 $L_0$은 출발 언어, $L_k$는 도착 언어이고, 모든 $i$에 대해 $w_i$가 언어 $L_{i-1}$과 $L_i$의 공통 단어여야 한다. 같은 단어를 여러 번 써도 된다.

마리아지냐가 이 문제를 너무 쉽게 풀자 조앙지뉴는 놀랐다. 동생의 성공에 약이 오른 그는 조건 두 가지를 더해 문제를 어렵게 만들었다. 마리아지냐는 단어 사이의 공백을 빼고 센 전체 길이가 가장 짧은 단어열을 찾아야 하고, 연속한 두 단어는 첫 글자가 같으면 안 된다.

그러면 앞의 답은 "amigo"와 "actual"의 첫 글자가 같아서 올바르지 않다. 하지만 다른 답인 amigo red date를 찾을 수 있고, 전체 길이는 12이다.

조앙지뉴는 인터넷을 샅샅이 뒤져 엄청나게 긴 단어 목록을 만들고 마리아지냐에게 문제를 풀어 보라고 했다. 답이 여러 개일 수 있으므로 그는 조건을 만족하는 가장 짧은 단어열의 길이만, 또는 답이 없다는 사실만 말해 달라고 했다. 마리아지냐를 도와줄 수 있겠는가?

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫째 줄에는 조앙지뉴가 모은 단어의 수 $M$ ($1 \le M \le 2000$)이 주어진다. 둘째 줄에는 서로 다른 두 문자열 $O$와 $D$가 공백 하나를 사이에 두고 주어지며, 각각 출발 언어와 도착 언어를 나타낸다. 다음 $M$개의 줄에는 각각 세 문자열 $I_1$, $I_2$, $P$가 공백 하나를 사이에 두고 주어진다. 이는 두 언어 $I_1$, $I_2$와 두 언어의 공통 단어 $P$를 뜻한다($I_1$과 $I_2$는 항상 다르다). 모든 문자열의 길이는 1 이상 50 이하이고, 알파벳 소문자로만 이루어져 있다. 같은 언어 쌍에 여러 단어가 연결될 수 있지만, 한 테스트 케이스 안에서 같은 단어 $P$가 두 번 나오지는 않는다.

입력의 끝은 0 하나만 있는 줄로 나타낸다.

각 테스트 케이스마다 조앙지뉴의 조건을 만족하는 가장 짧은 단어열의 길이를 정수 하나로 출력한다. 조건을 만족하는 단어열이 없으면 impossivel을 출력한다(모두 소문자, 악센트 없음).