P16477 [GKS 2013 #B] Hex

本题的灵感来源于一个叫作 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` 等答案将被判为错误。

### 限制 $1 \le T \le 100$。 **测试集 1 - 可见** $1 \le \mathbf{N} \le 10$。 **测试集 2 - 隐藏** $1 \le \mathbf{N} \le 100$。 翻译由 DeepSeek V4 Pro 完成