题目描述

本题的灵感来源于一个叫作 Hex 的棋盘游戏，该游戏由 Piet Hein 和 John Nash 分别独立设计。本题与 Hex 想法类似，但并不要求你玩过 Hex。

此游戏在一块 $\mathbf{N} \times \mathbf{N}$ 的棋盘上进行，每个格子是一个六边形。有两名玩家：红方（使用红色棋子）和蓝方（使用蓝色棋子）。棋盘初始为空，两名玩家轮流在棋盘内的某个格子上放置一枚属于自己颜色的棋子。每位玩家可以将棋子放在未被其他任何颜色棋子占据的任意格子上。没有要求棋子必须放在同色棋子的旁边。先手玩家由随机决定（两名玩家概率相等）。

棋盘的上边界和下边界被标记为红色，另外两条边界被标记为蓝色。游戏的目标是让一名玩家的棋子形成一条连通路径，连通标记为该玩家颜色的两条棋盘边界。率先达成此目标的玩家获胜。注意，四个角被视为同时连通两种颜色。

一旦有玩家获胜，游戏立即结束。

给定一个游戏状态，请你帮助刚接触该游戏的人判断游戏棋盘的状态。请输出以下四种情况之一：

• Impossible：如果两名玩家不可能按照规则进行并达到该游戏状态。
• Red wins：如果执红色棋子的玩家已经获胜。
• Blue wins：如果执蓝色棋子的玩家已经获胜。
• Nobody wins：如果还没有玩家获胜。注意，一局 Hex 游戏不可能在没有获胜者的情况下结束！

注意，对于任何不可能的状态，即使红方或蓝方已经形成了连通标记为己方颜色的棋盘边界的路径，唯一正确的答案仍是 Impossible。

以下是一个 $6 \times 6$ 棋盘上蓝方获胜的示例对局。蓝方是先手玩家，在标有 $1$ 的格子上放置了蓝色棋子。随后红方在标有 $2$ 的格子上放置，接着蓝方在标有 $3$ 的格子上放置，以此类推。在第 $11$ 枚棋子落下后，蓝方获胜。

:::align{center} :::

输入格式

输入的第一行给出测试用例的个数 $T$。接下来是 $T$ 个测试用例。每个测试用例以整数 $\mathbf{N}$ 开始，表示棋盘的边长。随后是 $\mathbf{N}$ 行、每行 $\mathbf{N}$ 个字符，构成棋盘。字符仅由 B、R 和 . 组成。B 表示该格被蓝色棋子占据，R 表示该格被红色棋子占据，. 表示空格。

输出格式

对于每个测试用例，输出一行形如 Case #x: y 的内容，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是游戏棋盘的状态。$y$ 可以是 Impossible、Blue wins、Red wins 或 Nobody wins（不含引号）。请注意，评测系统区分大小写，因此 impossible、blue wins、red wins 和 nobody wins 等答案将被判为错误。

7
1
.
1
B
1
R
2
BR
BB
4
BBBB
BBB.
RRR.
RRRR
4
BBBB
BBBB
RRR.
RRRR
6
......
..R...
BBBBBB
..R.R.
..RR..
......

Case #1: Nobody wins
Case #2: Blue wins
Case #3: Red wins
Case #4: Impossible
Case #5: Blue wins
Case #6: Impossible
Case #7: Blue wins

提示

限制

$1 \le T \le 100$。

测试集 1 - 可见

$1 \le \mathbf{N} \le 10$。

测试集 2 - 隐藏

$1 \le \mathbf{N} \le 100$。

翻译由 DeepSeek V4 Pro 完成