12040번 - Password Security (Small1) 스페셜 저지다국어

You just bought your young nephew Andrey a complete set of 26 English wooden alphabet letters from A to Z. Because the letters come in a long, linear package, they appear to spell out a 26-letter message.

You use N different passwords to log into your various online accounts, and you are concerned that this message might coincidentally include one or more of them. Can you find any arrangement of the 26 letters, such that no password appears in the message as a continuous substring?

The first line of the input gives the number of test cases, T. T test cases follow. Each consists of one line with an integer N, and then another line with N different strings of uppercase English letters P₁, P₂, ..., P_N, which are the passwords.

Limits

• 1 ≤ T ≤ 100.
• 1 ≤ length of P_i ≤ 26, for all i. (Each password is between 1 and 26 letters long.)
• P_i ≠ P_j for all i ≠ j. (All passwords are different.
• N = 1.

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is a permutation of the entire uppercase English alphabet that contains no password as a continuous substring, or the word IMPOSSIBLE if there is no such permutation.

For each of the non-IMPOSSIBLE cases, the sample output shows only one possible answer. There are many valid answers for these inputs.

Note that only sample cases #1, #2, and #3 would appear in Small dataset 1. Any of the sample cases could appear in Small dataset 2.