Babel

Joãozinho and Mariazinha are siblings who are very excited about their language classes; each of them attends several different language courses. When they get home they talk about grammar, vocabulary, the culture of different countries, and so on. In one of these conversations they noticed that some words exist in more than one language, even if the meaning is not necessarily the same. For example, "amigo" exists in Portuguese and Spanish with the same meaning, while "date" is a word common to French and English that can mean different things, since in English "date" also refers to a romantic meeting besides a calendar date. In Spanish "red" means a net, while in English it is the color. Another example is "actual", which means real in English and present, current in Spanish (as in Portuguese).

Excited by these discoveries, they wrote down in a notebook every common word they could think of, associating each one with a pair of languages. Being observant, Joãozinho set Mariazinha a challenge: given an origin language and a destination language, write a sequence of words where the first word must belong to the origin language and the last word must belong to the destination language. Two adjacent words in the sequence must belong to a common language. For example, if the origin language were Portuguese and the destination French, Mariazinha could write the sequence amigo actual date (Portuguese/Spanish, Spanish/English, English/French).

Precisely, a sequence of words $w_1, w_2, \ldots, w_k$ ($k \ge 1$) is valid if there are languages $L_0, L_1, \ldots, L_k$ such that $L_0$ is the origin language, $L_k$ is the destination language, and for every $i$ the word $w_i$ is a common word of languages $L_{i-1}$ and $L_i$. The same word may be used more than once.

To Joãozinho's surprise, Mariazinha solved the problem very easily. Annoyed by his sister's success, he made the problem harder with two restrictions: Mariazinha must find the sequence with the smallest total length, not counting the spaces between words, and two consecutive words cannot have the same first letter.

Under these rules the previous solution becomes invalid, because "amigo" and "actual" have the same first letter. It is possible, however, to find another solution, amigo red date, whose total length is 12.

Joãozinho searched the internet extensively, compiled a huge list of words and challenged Mariazinha to solve the problem. Since there may be more than one solution, he asked her only for the length of the shortest sequence satisfying the restrictions, or to say that there is no possible solution. Can you help Mariazinha?

The input contains several test cases. The first line of a test case contains an integer $M$ ($1 \le M \le 2000$), the number of words compiled by Joãozinho. The second line contains two distinct strings $O$ and $D$, separated by a single space, giving the origin and destination languages respectively. Each of the next $M$ lines contains three strings $I_1$, $I_2$ and $P$, separated by single spaces, representing two languages and a word common to both ($I_1$ and $I_2$ are always different). Every string has length at least 1 and at most 50 and contains only lowercase letters. The same pair of languages may have several different words associated with it, but a word $P$ never appears twice within a test case.

The end of input is indicated by a line containing only a zero.

For each test case, print a single integer: the length of the shortest sequence that satisfies Joãozinho's restrictions, or impossivel (lowercase, without an accent) if no such sequence exists.