题目描述

Hamilton 是加拿大多伦多附近的一座城市，也是一个适合徒步旅行的好地方。

在本问题中，Hamilton 被表示为一个由 $2R$ 行 $2C$ 列单位单元格组成的网格，每个单元格要么是空的（用 * 表示），要么包含一座建筑（用 # 表示）。第 $i$ 行第 $j$ 列的单元格记为 $A_{i,j}$，其中 $1 \le i \le 2R$，$1 \le j \le 2C$。不能进入包含建筑的单元格，且只能移动到与当前单元格共享一条边的相邻单元格（不仅仅是角点）。网格满足：如果将网格均匀划分为 $2 \times 2$ 的单元格块，则每个块中的四个单元格要么全部为空，要么全部被建筑占据。将由单元格 $A_{2i-1,2j-1}$、$A_{2i-1,2j}$、$A_{2i,2j-1}$ 和 $A_{2i,2j}$ 组成的块记为 $B_{i,j}$，其中 $1 \le i \le R$，$1 \le j \le C$。

Grace 是一位游客，她想参观 Hamilton 中的所有空单元格。Grace 当前位于单元格 $A_{1,1}$ 中。重复访问同一个单元格可能会让她感到无聊。因此，Grace 希望恰好访问每个空单元格一次，并最终回到单元格 $A_{1,1}$。你能帮助 Grace 提供一个字符串（由方向移动字符 $\{N, E, S, W\}$ 组成，分别表示向北、向东、向南、向西移动一个单位），使得 Grace 按照该字符串移动，能够访问每个空单元格一次，并最终回到 $A_{1,1}$。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。

每个测试用例的第一行包含两个整数 $R$ 和 $C$。

接下来的 $R$ 行，每行包含 $C$ 个字符。

其中第 $i$ 行第 $j$ 个字符表示块 $B_{i,j}$，该块由以下四个单元格组成：$A_{2i-1,2j-1}$、$A_{2i-1,2j}$、$A_{2i,2j-1}$ 和 $A_{2i,2j}$。

如果 $B_{i,j} = \#$，则 $B_{i,j}$ 中的四个单元格全部被建筑占据。

否则，如果 $B_{i,j} = \ast$，则 $B_{i,j}$ 中的四个单元格全部为空。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是问题的答案，具体如下：

如果无解，则 $y$ 应为 IMPOSSIBLE。否则，$y$ 应为一个由集合 $\{N, E, S, W\}$ 中字符组成的序列，表示一条有效路径中的单位移动（分别对应北、东、南、西），从 $A_{1,1}$ 出发，如上文所述。

注意，你的最后一步移动应使你回到 $A_{1,1}$；这一步不算作重复访问同一单元格。

如果存在多个有效解，你可以输出其中任意一个。

3
1 1
*
2 2
**
*#
3 4
****
*#*#
****

Case #1: SENW
Case #2: SSSENNEENWWW
Case #3: ESSSSEEENNNWWNEEEEESWWSSSEESWWWW

3
3 1
*
*
#
1 3
*#*
3 4
**#*
**#*
****

Case #1: SSSENNNW
Case #2: IMPOSSIBLE
Case #3: ESSSSENNNNESSSSEEENNNNESSSSSWWWW

提示

样例输出展示了一组答案。其他答案也可能存在。

在样例 #1 中，Grace 将按照路径 $A_{1,1}$、$A_{2,1}$、$A_{2,2}$、$A_{1,2}$ 移动，最后回到 $A_{1,1}$。注意 ESWN 是另一个可能的有效答案。

下图展示了样例 #1 的一种可能路径。

:::align{center} :::

下图展示了样例 #2 的一种可能路径。

:::align{center} :::

限制条件

$1 \le T \le 100$。

$1 \le R \le 200$。

$1 \le C \le 200$。

网格中的所有字符均来自集合 $\{\#, \ast\}$。

每个测试用例输入网格的第一行的第一个字符为 *，即 $B_{1,1} = \ast$。

测试集 1

块中包含建筑当且仅当其行号和列号均为偶数。即 $B_{i,j} = \# \iff ((i \bmod 2 = 0) \land (j \bmod 2 = 0))$。

测试集 2

无额外限制。

翻译由 DeepSeek V4 Pro 完成