23208번 - 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₁, b₁), (a₂, b₂), . . . , (a_k, b_k), find a non-empty sequence s₁, s₂, . . . , s_m such that the following is true:

a_s1 a_s2 . . . a_sm = b_s1 b_s2 . . . b_sm

where a_s1 a_s2 . . . indicates string concatenation. The modified puzzle that Emil sent added the following restriction: for all i ≠ j, s_i ≠ s_j. You don’t have enough time to solve Emil’s original puzzle. Can you solve the modified version?

Each test case starts with a line containing an integer 1 ≤ k ≤ 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 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 length of the output). If there are multiple shortest sequences, choose the one that is lexicographically first. Follow the format of the sample output.