Description

Havannah 是一款由 Christian Freeling 创作的抽象策略棋类游戏。Havannah 在一个六边形棋盘上进行，棋盘每边有 $S$ 个六边形格子。每个六边形格子有两条水平边和四条斜边。每个六边形用一对整数标识。棋盘左下角的格子为 $(1, 1)$。与 $(x, y)$ 相邻、指向两点钟方向的格子是 $(x, y+1)$，指向十点钟方向的相邻格子是 $(x+1, y)$。下图是 $S=5$ 时的棋盘示例：

在 Havannah 游戏中，每个格子最多只能被一个棋子占据。棋子一旦落下，不会被移走或移动。游戏目标是用棋子构成以下三种连通结构之一。获胜结构包括：

• 环（ring）：形成一个包围了一个或多个空格的环。即，至少有一个内部格子是空的。更具体地说，存在一个空格，它被棋子包围，与棋盘的外边界隔开。注意，这条规则与官方 Havannah 游戏不同。
• 桥（bridge）：连接棋盘上任意两个角的结构。
• 叉（fork）：连接棋盘六条边中任意三条的结构。角不算作任何一条边的一部分。

下图展示了获胜结构的例子：

你的程序需要判断，单一玩家的一系列落子是否形成了获胜结构。如果形成，则输出结构名称及完成该结构的步数。如果某一步同时完成了多个环、连接了多于两个角，或连接了多于三条边，依然只算作“环”、“桥”或“叉”。但如果某一步同时完成了不同类型的结构，你需要输出所有结构的名称。我们只关心首次形成获胜结构的那一步：之后的落子全部忽略。如果全部落子后棋盘上没有任何获胜结构，则输出 none。

Input Format

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据。每组第一行为两个整数 $S$ 和 $M$，分别表示棋盘每边六边形的数量和落子数。接下来 $M$ 行，每行一个用空格分隔的二元组 $(x, y)$，表示落子的位置。所有落子都在 $S$ 阶棋盘范围内，且无重复。本组测试数据的棋盘初始为空。

Output Format

对于每个测试用例，输出一行 "Case #$n$: "，后接如下之一：

• none
• bridge in move $k$
• fork in move $k$
• ring in move $k$
• bridge-fork in move $k$
• bridge-ring in move $k$
• fork-ring in move $k$
• bridge-fork-ring in move $k$

测试用例编号从 1 开始，落子编号也从 1 开始。

7
2 4
1 1
1 2
2 3
3 3
3 6
2 1
2 2
2 3
2 4
1 2
4 4
3 7
3 3
2 2
2 3
3 4
4 4
4 3
3 2
3 6
2 2
2 3
3 4
4 4
4 3
3 2
3 8
1 1
2 1
1 3
2 4
1 2
3 2
3 3
3 4
3 7
1 1
2 2
3 5
3 4
5 3
4 3
3 3
3 3
1 1
1 3
3 5

Case #1: bridge in move 2
Case #2: fork in move 5
Case #3: none
Case #4: ring in move 6
Case #5: bridge-fork in move 5
Case #6: bridge in move 7
Case #7: none

Hint

限制条件

测试集 1（8 分，结果可见）

• 时间限制：30 3 秒
• $1 \leq T \leq 200$
• $2 \leq S \leq 50$
• $0 \leq M \leq 100$

测试集 2（12 分，结果隐藏）

• 时间限制：60 6 秒
• $1 \leq T \leq 20$
• $2 \leq S \leq 3000$
• $0 \leq M \leq 10000$

翻译由 ChatGPT-4.1 完成。