Paradox Sort (Large)

Vlad likes candy. You have a bag of distinct candies and you are going to let him keep one of them. You choose an order for the candies, then hand them to Vlad one at a time. For each candy after the first, Vlad compares the candy he was holding with the one he just received, keeps the one he likes more, and throws the other one away.

You would expect that any order leaves Vlad with his favorite candy. That is not the case, because he does not necessarily have a favorite. For every pair of candies we know which one he prefers, but his choices do not have to come from a single ranking. He may choose Orange when offered Orange and Lemon, Banana when offered Orange and Banana, and Lemon when offered Lemon and Banana.

One particular candy is the one you want Vlad to end up with. Given his preference for every pair of candies, decide whether some order leaves him with that candy. If such an order exists, find the lexicographically smallest one.

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

Each test case starts with a line containing the integers $N$ and $A$, separated by a 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$. If $i \ne j$, then character $j$ of line $i$ differs from character $i$ of line $j$.

Limits

• $1 \le T \le 100$
• $1 \le N \le 100$

For each test case, output "Case #x: ", where x is the test case number starting from $1$. After it, print IMPOSSIBLE if no order leaves Vlad with candy $A$, and otherwise print the lexicographically smallest order that does. The order contains every candy number from $0$ to $N-1$ exactly once, separated by single spaces.