P13267 [GCJ 2014 Finals] Paradox Sort

Vlad 喜欢糖果。你有一袋不同种类的糖果，你打算让 Vlad 最后保留其中一颗。你会为这批糖果指定一个出场顺序，然后依次将糖果一个接一个地递给 Vlad。Vlad 每次收到糖果时（第一颗除外），会将当前手里的糖果与新收到的糖果进行比较，保留他更喜欢的那一颗，把另一颗丢掉。 你可能会以为，无论你选择怎样的顺序，Vlad 最终都会留下他最喜欢的糖果。但事实并非如此！Vlad 不一定有明确的“最喜欢”糖果。我们知道，对于任意一对糖果，他总能做出选择，但这种偏好关系不一定构成一个一致的排名结构。比如：他可能在橘子和柠檬之间选择橘子，在香蕉和橘子之间选择香蕉，但又在柠檬和香蕉之间选择柠檬！ 现在你有一个特别想让 Vlad 最后留下的糖果。已知 Vlad 对每对糖果的偏好，请你判断是否存在一种糖果顺序，使得 Vlad 最终会留下你指定的那一颗。如果存在，请找出按字典序排列的最小的那一种顺序。

输入的第一行为测试用例个数 $\mathrm{T}$。 接下来是 $\mathrm{T}$ 个测试用例，每个测试用例包含如下内容： - 第一行包含两个整数 $\mathrm{N}$ 和 $\mathrm{A}$，中间以空格分隔。$\mathrm{N}$ 表示糖果的总数，$\mathrm{A}$ 表示你希望 Vlad 最终留下的糖果编号（糖果从 $0$ 到 $\mathrm{N}-1$ 编号）。 - 接下来 $\mathrm{N}$ 行，每行包含 $\mathrm{N}$ 个字符。第 $i$ 行第 $j$ 个字符表示 Vlad 对第 $i$ 颗和第 $j$ 颗糖果的偏好： - 若为 `'Y'`，表示 Vlad 更喜欢糖果 $i$； - 若为 `'N'`，表示 Vlad 更喜欢糖果 $j$； - 若为 `'-'`，表示 $i = j$，即同一颗糖果自身，无需比较。 保证当 $i \neq j$ 时，第 $i$ 行第 $j$ 个字符与第 $j$ 行第 $i$ 个字符不同。

对于每个测试用例，输出一行，格式为 `"Case #x: "`（$x$ 为测试用例编号，从 $1$ 开始），后接： - 若不存在一种顺序能让 Vlad 最终保留糖果 $\mathrm{A}$，输出 `"IMPOSSIBLE"`； - 否则，输出一个以空格分隔的糖果编号序列（表示字典序最小的有效顺序）。

## 限制条件 - $1 \leq \mathrm{T} \leq 100$ ### Small 数据集（4 分） - 时间限制：~~60~~ 3 秒 - $1 \leq \mathrm{N} \leq 10$ ### Large 数据集（28 分） - 时间限制：~~120~~ 5 秒 - $1 \leq \mathrm{N} \leq 100$ 翻译由 ChatGPT-4o 完成