URI Online Judge | 1085

Babel

By Pedro Demasi Brazil

Timelimit: 5

John and Mary are brothers, and are enthusiastic about their courses on foreign languages. Each one is taking several language courses. When they get home they comment about grammar, vocabulary, culture of the different countries and so on. In one of those conversations they realized that some words are common to more than one language, even though the words may have different meanings in the languages. For example, the word "amigo" exists in Portuguese and Spanish and has the same meaning, while "date" is a word that exists in English and French and may have different meanings, since "date" is also a fruit, besides meaning a calendar date. On the other hand, "red" in Spanish is a network, while in English it is a color.

Thrilled by these findings, the brothers decided to write in a notepad all words in common they could think of, associating each word to a pair of languages. Observant and smart, John proposed a challenge to Mary: given one language to start and one language to finish, write down a sequence of words such that the first word is included in the vocabulary of the start language, and the last word is included in the vocabulary of the finish language. Two adjacent words in the sequence must be in the vocabulary of the same language. For example, if the start language is Portuguese and the finish language is French, Mary could write the sequence "amigo actual date" (Portuguese/Spanish, Spanish/English, English/French).

To John's surprise, Mary solved the problem rather easily. Annoyed by his sister's success, he decided to make the problem more difficult: Mary must find a solution in which the sequence has the smallest number of letters in total (not counting spaces between words), and, besides, two consecutive words must not have the same initial letter.

Note that the previous solution is now invalid, as "amigo" and "actual" share the same initial letter. It is possible, however, to find another solution, "amigo red date", with a total length equal to 12.

John did an extensive research on the Internet and compiled an enormous list of words, and challenged Mary to solve the problem. As there may be more than one solution, he asked her to answer if there is a solution, and in that case to answer the number of letters in the best solution. Can you help Mary?

Input

The input contains several test cases. The first line of a test case contains one integer M (1 ≤ M ≤ 2000), representing the total number of words compiled by John. The second line contains two distinct strings O and D, separated by one space, indicating respectively the start language and the finish language. Each of the next M lines contains three strings I1, I2 and P, separated by one space, representing respectively two languages and one word in common between both languages (I1 and I2 arealways distinct). All strings will have length at least 1 and at most 50, and will be composed of lower case letters only. The same pair of languages may have several words associated to it, but a word P will be never repeated in a test case.

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

Output

For each test case in the input, your program must print a line with a single integer, the length of the shortest sequence that satisfies John's restrictions, or the word "impossivel" (lowercase, meaning "impossible" in Portuguese) in case it is not possible.

Input Sample Output Sample

4
portugues frances
ingles espanhol red
espanhol portugues amigo
frances ingles date
espanhol ingles actual
4
portugues alemao
ingles espanhol red
espanhol portugues amigo
frances ingles date
espanhol ingles actual
6
portugues frances
ingles espanhol red
espanhol portugues amigo
frances ingles date
frances espanhol la
portugues ingles a
espanhol ingles actual
0

12
impossivel
5