Problem H
Limited Correspondence
Emil, a Polish mathematician, sent a simple puzzle by post to his British friend, Alan. Alan sent a reply saying he didn’t have an infinite amount of time he could spend on such non-essential things. Emil modified his puzzle (making it a bit more restricted) and sent it back to Alan. Alan then solved the puzzle.
Here is the original puzzle Emil sent: given a sequence of pairs of strings $(a_1, b_1), (a_2, b_2), \ldots , (a_ k, b_ k)$, find a non-empty sequence $s_1, s_2, \ldots , s_ m$ such that the following is true:
\[ a_{s_1}a_{s_2}\ldots a_{s_ m} = b_{s_1}b_{s_2}\ldots b_{s_ m} \]where $a_{s_1} a_{s_2} \ldots $ indicates string concatenation. The modified puzzle that Emil sent added the following restriction: for all $i\neq j$, $s_ i\neq s_ j$.
You don’t have enough time to solve Emil’s original puzzle. Can you solve the modified version?
Input
Input consists of up to $5$ test cases, ending at end of file. Each case starts with a line containing an integer $1 \leq k \leq 11$, followed by $k$ lines. Each of the $k$ lines contains two space-separated lowercase alphabetic strings which represent a pair. Each individual string will be non-empty and at most $100$ characters long.
Output
For each case, display the case number followed by the sequence found (if it is possible to form one) or “IMPOSSIBLE” (if it is not possible to solve the problem). If it is possible but there are multiple sequences, you should prefer the shortest one (in terms of the number of characters output). If there are multiple shortest sequences, choose the one that is lexicographically first. Follow the format of the sample output.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 are yo you u how nhoware alan arala dear de 8 i ie ing ding resp orres ond pon oyc y hello hi enj njo or c 3 efgh efgh d cd abc ab 3 a ab b bb c cc |
Case 1: dearalanhowareyou Case 2: ienjoycorresponding Case 3: abcd Case 4: IMPOSSIBLE |
