题目描述

Vlad likes candies. You have a bag of different candies, and you're going to let Vlad keep one of them. You choose an order for the candies, then give them to Vlad one at a time. For each candy Vlad receives (after the first one), he compares the candy he had to the one he was just given, keeps the one he likes more, and throws the other one away.

You would expect that for any order you choose, Vlad will always end up with his favorite candy. But this is not the case! He does not necessarily have a favorite candy. We know for any pair of candies which one he will prefer, but his choices do not necessarily correspond to a simple ranking. He may choose Orange when offered Orange and Lemon, Banana when offered Orange and Banana, and Lemon when offered Lemon and Banana!

There is a particular candy you want Vlad to end up with. Given Vlad's preferences for each pair of candies, determine if there is an ordering such that Vlad will end up with the right candy. If there is, find the lexicographically-smallest such ordering.

输入格式

The first line of the input gives the number of test cases, $\mathrm{T}$. $\mathrm{T}$ test cases follow. Each test case will start with a line containing the integers $\mathrm{N}$ and $\mathrm{A}$, separated by a space. $\mathrm{N}$ is the number of candies, and $\mathrm{A}$ is the number of the candy we want Vlad to finish with. The candies are numbered from 0 to $\mathrm{N}-1$. The next $\mathrm{N}$ lines each contains $\mathrm{N}$ characters. Character $\mathrm{j}$ of line $\mathrm{i}$ will be 'Y' if Vlad prefers candy $\mathrm{i}$ to candy $\mathrm{j}$, 'N' if Vlad prefers candy $\mathrm{j}$ to candy $\mathrm{i}$, and '-' if $\mathrm{i}=\mathrm{j}$. Note that if $\mathrm{i} \neq \mathrm{j}$, the $\mathrm{j}$ th character of the $\mathrm{i}$ th row must be different from the $\mathrm{i}$ th character of the $\mathrm{j}$ th row.

输出格式

For each test case output "Case #x: ", where $\mathrm{x}$ is the case number, followed by either "IMPOSSIBLE" or a space-separated list of the lexicographically-smallest ordering of candies that leaves Vlad with $\mathrm{A}$.

3
2 0
-Y
N-
2 0
-N
Y-
4 3
-YNN
N-YY
YN-Y
YNN-

Case #1: 0 1
Case #2: IMPOSSIBLE
Case #3: 1 2 0 3

提示

Limits

• $1 \leqslant \mathrm{T} \leqslant 100$.

Small dataset(4 Pts)

• Time limit: 60 3 seconds.
• $1 \leqslant \mathrm{N} \leqslant 10$.

Large dataset(28 Pts)

• Time limit: 120 5 seconds.
• $1 \leqslant \mathrm{N} \leqslant 100$.