题目描述

Marlin 是一条丢失了儿子的鱼，正在努力寻找他的儿子。幸运的是，他遇到了正在和兄弟 Wally 与 Seymour 一起游泳的海龟 Cynthia。Cynthia 知道 Marlin 需要去哪里，并且她可以非常精确地给出指引。虽然 Marlin 很聪明，能够完美地按照指令行动，但要记住一长串指令还是很困难的。Cynthia 需要想办法让指令列表尽可能简短。

Marlin 生活在一个有 $\mathbf{R}$ 行 $\mathbf{C}$ 列的矩阵中。矩阵中的某些格子是危险的，不能进入。Marlin 和他的儿子目前分别位于两个不同的非危险格子中。Marlin 的儿子不会移动。Cynthia 决定以程序的形式给 Marlin 指路，这个程序由若干条指令组成，每条指令占一行。每条指令有以下 5 种类型之一：

• $\mathbf{N}$：向北（上）移动一格，
• $\mathbf{S}$：向南（下）移动一格，
• $\mathbf{W}$：向西（左）移动一格，
• $\mathbf{E}$：向东（右）移动一格，
• $\mathbf{G}(\mathbf{i})$：跳转到指令列表的第 $i$ 行（从 1 开始计数）。

每当执行前 4 种指令中的任意一种后，如果还有下一行指令，Marlin 会跳到下一行继续执行。如果没有下一行指令，Marlin 就会原地停留，永远不再移动。

例如，假如 Marlin 执行如下程序：

1. $\mathbf{N}$
2. $\mathbf{E}$
3. $\mathbf{G}(6)$
4. $\mathbf{S}$
5. $\mathbf{G}(1)$
6. $\mathbf{W}$
7. $\mathbf{G}(4)$

他会先向北移动（第 1 行），然后向东移动（第 2 行），接着跳转到第 6 行（第 3 行），然后向西移动（第 6 行），再跳转到第 4 行（第 7 行），然后向南移动（第 4 行），再跳转到第 1 行（第 5 行），然后向北移动（第 1 行），如此循环往复。

如果某一时刻 Marlin 和他的儿子处于同一个格子，他们就会团聚，Marlin 也会停止执行任何指令。海龟 Cynthia 想知道，能够让 Marlin 安全到达他儿子所在格子的最短程序需要多少行指令，且在此过程中 Marlin 不能进入危险格子，也不能走出矩阵边界。所有 $\mathbf{G}$ 指令必须跳转到程序中已存在的行。

输入格式

输入的第一行为测试用例数 $\mathbf{T}$。接下来有 $\mathbf{T}$ 组测试数据。每组测试数据的第一行为两个整数 $\mathbf{R}$ 和 $\mathbf{C}$，表示矩阵的行数和列数。接下来有 $\mathbf{R}$ 行，每行包含一个长度为 $\mathbf{C}$ 的字符串。第 $i$ 行第 $j$ 列的字符 $\mathbf{A}_{ij}$ 表示矩阵中第 $i$ 行第 $j$ 列的格子。若该格子为危险格子，则为字符 $\#$；若为 Marlin 当前所在格子，则为大写字母 $\mathbf{M}$；若为 Marlin 儿子当前所在格子，则为大写字母 $\mathbf{N}$；若为未被占用的非危险格子，则为 $\mathbf{.}$。

输出格式

对于每组测试数据，输出一行，格式为 Case #x: y，其中 $x$ 为测试用例编号（从 1 开始），$y$ 为在上述条件下能让 Marlin 到达他儿子所在格子的最短程序所需的指令行数。如果不存在这样的程序，则输出 $\text{IMPOSSIBLE}$。

输入输出样例 #1

输入 #1

5
2 5
N...#
....M
2 5
N#...
...#M
5 5
N..##
#.###
#...#
##.##
##..M
5 5
..N##
#.###
#...#
##.##
##..M
3 3
#M#
###
#N#

输出 #1

Case #1: 4
Case #2: 7
Case #3: 5
Case #4: 6
Case #5: IMPOSSIBLE

说明/提示

样例说明

下面是每个样例的最短程序示例。

• 样例 1：

1: W
2: N
3: S
4: G(1)

或

1: W
2: N
3: W
4: G(3)

• 样例 2：

1: N
2: W
3: W
4: S
5: W
6: W
7: N

• 样例 3：

1: W
2: W
3: N
4: N
5: G(2)

• 样例 4：

1: W
2: W
3: N
4: N
5: E
6: G(1)

样例解释

• $1 \leq \mathbf{T} \leq 100$。
• 对所有 $i$ 和 $j$，$\mathbf{A}_{ij}$ 只可能为 $\#$、$\mathbf{.}$、大写字母 $\mathbf{M}$ 或大写字母 $\mathbf{N}$。
• 恰好有一对 $i$ 和 $j$ 使得 $\mathbf{A}_{ij} = \mathbf{M}$。
• 恰好有一对 $i$ 和 $j$ 使得 $\mathbf{A}_{ij} = \mathbf{N}$。

测试点 1（19 分，公开）

• 时间限制：30 秒。
• $1 \leq \mathbf{R} \leq 10$。
• $1 \leq \mathbf{C} \leq 10$。

测试点 2（30 分，隐藏）

• 时间限制：120 秒。
• 最多 10 个测试用例满足：
  • $1 \leq \mathbf{R} \leq 100$。
  • $1 \leq \mathbf{C} \leq 100$。
• 其余测试用例满足：
  • $1 \leq \mathbf{R} \leq 50$。
  • $1 \leq \mathbf{C} \leq 50$。