Description

Vlad 喜欢糖果。你有一袋不同种类的糖果，你打算让 Vlad 最后保留其中一颗。你会为这批糖果指定一个出场顺序，然后依次将糖果一个接一个地递给 Vlad。Vlad 每次收到糖果时（第一颗除外），会将当前手里的糖果与新收到的糖果进行比较，保留他更喜欢的那一颗，把另一颗丢掉。

你可能会以为，无论你选择怎样的顺序，Vlad 最终都会留下他最喜欢的糖果。但事实并非如此！Vlad 不一定有明确的“最喜欢”糖果。我们知道，对于任意一对糖果，他总能做出选择，但这种偏好关系不一定构成一个一致的排名结构。比如：他可能在橘子和柠檬之间选择橘子，在香蕉和橘子之间选择香蕉，但又在柠檬和香蕉之间选择柠檬！

现在你有一个特别想让 Vlad 最后留下的糖果。已知 Vlad 对每对糖果的偏好，请你判断是否存在一种糖果顺序，使得 Vlad 最终会留下你指定的那一颗。如果存在，请找出按字典序排列的最小的那一种顺序。

Input Format

输入的第一行为测试用例个数 $\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$ 个字符不同。

Output Format

对于每个测试用例，输出一行，格式为 "Case #x: "（$x$ 为测试用例编号，从 $1$ 开始），后接：

• 若不存在一种顺序能让 Vlad 最终保留糖果 $\mathrm{A}$，输出 "IMPOSSIBLE"；
• 否则，输出一个以空格分隔的糖果编号序列（表示字典序最小的有效顺序）。

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

Hint

限制条件

• $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 完成