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 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.


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
are yo
you u
how nhoware
alan arala
dear de
i ie
ing ding
resp orres
ond pon
oyc y
hello hi
enj njo
or c
efgh efgh
d cd
abc ab
a ab
b bb
c cc
Case 1: dearalanhowareyou
Case 2: ienjoycorresponding
Case 3: abcd

Please log in to submit a solution to this problem

Log in