Havannah (Small)

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

A hexagon holds at most one stone. A stone that has been placed is never removed and never moved. The goal is to build a connected set of stones of one of three kinds:

• A ring encircles one or more empty hexagons. At least one of the enclosed hexagons must be empty: there is an empty hexagon that is cut off from the outer border of the board by hexagons with stones. This rule differs from the official rules of Havannah.
• A bridge connects any two corners of the board.
• A fork connects any three of the six board edges. A corner belongs to neither of the two edges next to it.

This picture shows examples of the winning structures:

A sequence of moves by a single player is given. Decide whether the moves build a winning structure. If they do, report 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. A move that completes structures of different kinds at the same time reports every one of their names. Only the first winning move matters: ignore every move after it. If no winning structure exists once all the moves have been played, print none.

The first line contains the number of test cases $T$. 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. The next $M$ lines give the moves in order, each holding a hexagon's coordinates $x$ and $y$ separated by a space. Every move lies on the board of size $S$. Each test case starts from an empty board, and no hexagon is played twice.

Limits

• $1 \le T \le 200$
• $2 \le S \le 50$
• $0 \le M \le 100$

For each test case print one line holding 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

Here $n$ is the test case number and $k$ is the number of the move that completed the winning structure. Both are counted from 1.

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