Paradox Sort (Small)

Vlad likes candy. You have a bag of distinct candies, and you are going to let Vlad keep exactly one of them. You first choose an order for the candies, then hand them to Vlad one at a time in that order. Starting with the second candy, Vlad compares the candy he just received to the one he is holding, keeps the one he prefers, and throws the other away. A candy that has been thrown away never comes back.

You might expect Vlad to finish holding his favorite candy no matter which order you choose. That is not what happens. Vlad does not necessarily have a favorite candy. His choice between any two candies is known, but those choices do not have to come from a single ranking. He may pick Orange over Lemon, Banana over Orange, and Lemon over Banana.

There is a particular candy $A$ that you want Vlad to finish with. Given Vlad's preference for every pair of candies, decide whether some order leaves Vlad holding candy $A$. If one exists, find the lexicographically smallest such order.

The first line contains the number of test cases, $T$. $T$ test cases follow.

Each test case starts with a line containing two integers $N$ and $A$ separated by one space. $N$ is the number of candies and $A$ is the number of the candy you want Vlad to finish with. The candies are numbered from $0$ to $N-1$.

The next $N$ lines each contain $N$ characters. Character $j$ of line $i$ is Y if Vlad prefers candy $i$ to candy $j$, N if he prefers candy $j$ to candy $i$, and - if $i = j$. Lines and characters are both numbered from $0$. For $i \neq j$, character $j$ of line $i$ differs from character $i$ of line $j$.

Limits

• $1 \le T \le 100$
• $1 \le N \le 10$
• $0 \le A \le N-1$

For each test case, print Case #x: followed by the answer. x is the test case number, starting at $1$.

If no order leaves Vlad holding candy $A$, print IMPOSSIBLE. Otherwise print the lexicographically smallest such order as candy numbers separated by one space. Orders are compared lexicographically as sequences of candy numbers.