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:
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\).
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.
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
Please log in to submit your solution.
|Average test runtime||0.54|
|Points (changes over time)||10|
|Tried by||3 users|
|Solved by||2 users|