Havannah Winning Structures

Havannah is an abstract strategy board game created by Christian Freeling. It is played on a hexagonal board with $S$ hexagons along each side, and each hexagon has two horizontal edges and four slanted edges. Hexagons are identified by pairs of integers. The hexagon in the bottom corner of the board is $(1, 1)$. The hexagon adjacent to $(x, y)$ in the two o'clock direction is $(x, y+1)$, and the hexagon adjacent to $(x, y)$ in the ten o'clock direction is $(x+1, y)$. Here is a board with $S = 5$.

The hexagons of the board are therefore the pairs $(x, y)$ that satisfy $1 \le x \le 2S-1$, $1 \le y \le 2S-1$ and $|x - y| \le S-1$. The six corner hexagons are $(1, 1)$, $(1, S)$, $(S, 1)$, $(S, 2S-1)$, $(2S-1, S)$ and $(2S-1, 2S-1)$. A hexagon lies on an edge of the board when it satisfies one of $x = 1$, $y = 1$, $x = 2S-1$, $y = 2S-1$, $y - x = S-1$, $x - y = S-1$ and is not a corner, so each of the six edges holds $S-2$ hexagons.

Each hexagon can be occupied by at most one stone. A stone that is put on the board is never removed and never moved. The goal is to build a connected set of stones of one of the three winning kinds.

• A ring encircles one or more empty hexagons. At least one of the enclosed hexagons must be empty: some empty hexagon is separated from the outermost boundary of the board by hexagons with stones. This rule differs from the official game of Havannah.
• A bridge connects any two corners of the board.
• A fork connects any three of the six edges of the board. A corner belongs to neither of the two edges next to it.

This picture shows examples of winning structures.

You are given the sequence of moves of a single player. Decide whether that sequence builds a winning structure. If it does, print the name of the structure and the number of the move that completed it. A move that completes several rings, connects more than two corners, or connects more than three edges still counts as one ring, one bridge, or one fork. If a move completes structures of different kinds at once, print the names of all of them. Only the first winning move matters, so ignore every move after it. If no winning structure is on the board once all the moves are played, print none.

The first line contains the number of test cases $T$. $T$ test cases follow.

The first line of each test case contains two integers $S$ and $M$, the number of hexagons along each side of the board and the number of moves in the sequence. Each of the next $M$ lines contains a pair of integers $x$ and $y$, one hexagon of the sequence, in order. Every move lies on the board of size $S$. In each test case the board starts empty and no hexagon is played twice.

Limits

• $1 \le T \le 20$
• $2 \le S \le 3000$
• $0 \le M \le 10000$

For each test case print one line containing Case #n: followed by one of:

• 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

Test cases are numbered from 1 as $n$, and moves are numbered from 1 as $k$. When several names apply, join them with hyphens in the order bridge, fork, ring.

Havannah was created by Christian Freeling and MindSports. MindSports and Christian Freeling do not endorse this problem and have no involvement with it.