Description

两家公司，Apricot Rules LLC 和 Banana Rocks Inc.，共用同一个数据中心。数据中心是一个 $\mathbf{R}$ 行 $\mathbf{C}$ 列的矩阵，每个格子里有一台服务器塔。每台服务器塔只属于其中一家公司。

最初，他们在分配给不同公司的格子之间的边上建造了墙。这样，属于同一公司的正交相邻格子依然是连通的。同时，如果格子 $\mathbf{x}$ 与格子 $\mathbf{y}$ 之间存在直接或间接的连通路径，则认为 $\mathbf{x}$ 和 $\mathbf{y}$ 是连通的。根据这个定义，可能会出现同一公司分配的两个格子不连通的情况，这是不可接受的。

两家公司同意在格子的顶点处修建狭窄的走廊，使得两个对角相邻的格子可以直接连通。我们用 $(\mathbf{i}, \mathbf{j})$ 表示第 $\mathbf{i}$ 行第 $\mathbf{j}$ 列的格子。每个顶点最多只能建一条狭窄的走廊，这意味着要么连接 $(\mathbf{i}, \mathbf{j})$ 和 $(\mathbf{i} + 1, \mathbf{j} + 1)$，要么连接 $(\mathbf{i} + 1, \mathbf{j})$ 和 $(\mathbf{i}, \mathbf{j} + 1)$，要么两者都不连，但不能同时连。当然，只有分配给同一公司的格子之间才能建走廊。

给定一个矩阵，每个格子用 $\mathbf{A}$ 或 $\mathbf{B}$ 标记，表示分配给哪家公司。请你为每个测试用例设计一种对角连通方案，使得所有 $\mathbf{A}$ 格子连通，所有 $\mathbf{B}$ 格子连通。

Input Format

第一行输入测试用例数 $\mathbf{T}$。接下来有 $\mathbf{T}$ 组测试数据。每组测试数据第一行包含两个整数 $\mathbf{R}$ 和 $\mathbf{C}$，表示数据中心的行数和列数。接下来有 $\mathbf{R}$ 行，每行包含 $\mathbf{C}$ 个字符，表示矩阵 $\mathbf{M}$。

Output Format

对于每个测试用例，首先输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 若无法通过对角连通方案使所有 $\mathbf{A}$ 格子连通且所有 $\mathbf{B}$ 格子连通，则输出 IMPOSSIBLE，否则输出 POSSIBLE。如果输出 POSSIBLE，则接下来输出 $\mathbf{R} - 1$ 行，每行 $\mathbf{C} - 1$ 个字符，表示一种合法的对角连通方案。第 $\mathbf{i}$ 行第 $\mathbf{j}$ 个字符为 \ 表示连接 $(\mathbf{i}, \mathbf{j})$ 和 $(\mathbf{i} + 1, \mathbf{j} + 1)$，为 / 表示连接 $(\mathbf{i} + 1, \mathbf{j})$ 和 $(\mathbf{i}, \mathbf{j} + 1)$，为 . 表示两对都不连。

3
2 2
AB
BA
2 3
AAB
ABB
3 4
BBAA
BABA
BBAA

Case #1: IMPOSSIBLE
Case #2: POSSIBLE
..
Case #3: POSSIBLE
//\
.//

Hint

样例解释

在样例 1 中，A 格子和 B 格子都需要连通，但由于两条连通路径会交叉在同一个顶点，最多只能连通一对。

在样例 2 中，输入中的格子已经满足连通要求，无需额外连通。注意你可以添加多余但合法的连通方案，因此 // 也是合法答案，但 \. 就不合法。

在样例 3 中，也有多种合法方案，样例给出其中一种。

数据范围

• $1 \leq \mathbf{T} \leq 100$。
• $2 \leq \mathbf{C} \leq 100$。
• 对所有 $\mathbf{i}, \mathbf{j}$，$\mathbf{M}_{\mathbf{i}, \mathbf{j}}$ 仅为大写字母 A 或 B。
• 至少有一个格子为 A，至少有一个格子为 B。

测试点 1（10 分，公开）

• $2 \leq \mathbf{R} \leq 4$。

测试点 2（13 分，隐藏）

• $2 \leq \mathbf{R} \leq 100$。

由 ChatGPT 4.1 翻译