Setting

Being a faithful student of computer science doesn't come without sacrifice. One of the first things you'll lose, apart from your mind, is a sense of what non-computer science people do in their free time. But that's alright since you have much more interesting things in mind anyway.

Your current project is learning foreign languages (as in, Spanish and Esperanto, not Whitespace and Brainfuck). But since that is not hard enough already for the bright student that you are, you decide to play with yourself. From all languages you know, you select one as the source language and one as the target language. You then try finding a way from the source to the target language through a sequence of words that appear in more than one language. For example, the word amigo appears in both Portuguese ad Spanish, while red is a word in both Spanish and English, so you can use the sequence amigo red to go from Portuguese to English.

To make it harder on yourself, you impose the following additional restrictions on your sequence of words:

  1. The sequence must have the smallest number of letters in total (not counting spaces between words).
  2. Two consecutive words must not have the same initial letter.

Input

The input consists of several test cases. The first line of a test case contains one integer \(1 \leq w \leq 2000\) representing the total number of words in the test case. The second line contains two distinct words separated by one space of which the first indicates the source and the second indicates the target language.

Each of the next \(w\) lines contains three strings \(I_1, I_2, P\), separated by one space each, representing a word \(P\) that appears in two languages (\(I_1\) and \(I_2\)). All strings will have length at least 1 and at most 50, and will be composed of lower-case letters only. Each word will only appear once in a test case.

The end of the input is indicated by \(w = 0\).

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 your restrictions, or the word impossivel (lower case, meaning impossible in Portuguese) if there is no way to go from the source to the target language.

Sample Input

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

Sample Output

12
impossivel
5

This is challenge 11492 of the ACM International Collegiate Programming Contest. Test input is provided by uDebug.

Upload Solution

Please log in to submit your solution.

Statistics

Difficulty (1 vote)
Average test runtime 0.54
Points (changes over time) 10
Tried by 3 users
Solved by 2 users

Global ranking

# Name Runtime Points worth
1 Mac 0.47 11
2 Dark 0.61 9