하바나 승리 구조 판정

하바나(Havannah)는 크리스티안 프렐링이 만든 추상 전략 보드게임이다. 판은 한 변에 육각형 칸이 $S$개씩 놓인 큰 육각형이고, 각 칸은 수평인 변 두 개와 기울어진 변 네 개로 이루어진다. 칸은 정수 두 개의 쌍으로 나타낸다. 판의 맨 아래 꼭짓점 칸이 $(1, 1)$이다. 칸 $(x, y)$에서 2시 방향으로 이웃한 칸은 $(x, y+1)$, 10시 방향으로 이웃한 칸은 $(x+1, y)$이다. 다음은 $S = 5$인 판의 예이다.

따라서 판 위의 칸은 $1 \le x \le 2S-1$, $1 \le y \le 2S-1$, $|x - y| \le S-1$을 모두 만족하는 $(x, y)$이다. 꼭짓점 칸은 $(1, 1)$, $(1, S)$, $(S, 1)$, $(S, 2S-1)$, $(2S-1, S)$, $(2S-1, 2S-1)$ 여섯 개이다. 변에 놓인 칸은 $x = 1$, $y = 1$, $x = 2S-1$, $y = 2S-1$, $y - x = S-1$, $x - y = S-1$ 가운데 하나를 만족하는 칸에서 꼭짓점을 뺀 것이고, 여섯 변에는 각각 칸이 $S-2$개씩 있다.

각 칸에는 돌을 최대 한 개까지 놓을 수 있다. 한 번 놓은 돌은 치우거나 옮기지 않는다. 목표는 다음 세 가지 승리 구조 가운데 하나를 이루는 연결된 돌 집합을 만드는 것이다.

• 링: 빈 칸을 하나 이상 둘러싼 고리. 둘러싸인 칸 가운데 적어도 하나는 비어 있어야 한다. 더 정확히 말하면, 돌이 놓인 칸에 가로막혀 판의 가장 바깥 경계에 닿을 수 없는 빈 칸이 있어야 한다. 이 규칙은 실제 하바나 게임의 규칙과 다르다.
• 브리지: 판의 꼭짓점 두 개를 잇는 연결.
• 포크: 판의 여섯 변 가운데 세 개를 잇는 연결. 꼭짓점은 양옆 어느 변에도 속하지 않는다.

다음 그림은 승리 구조의 예이다.

한 사람이 돌을 놓는 순서가 주어진다. 이 순서가 승리 구조를 만드는지 판정하고, 만든다면 구조의 이름과 그 구조를 완성한 수의 번호를 출력한다. 한 수가 링을 여러 개 완성하거나, 꼭짓점을 셋 이상 잇거나, 변을 넷 이상 이어도 각각 링 하나, 브리지 하나, 포크 하나로 센다. 한 수가 서로 다른 종류의 구조를 동시에 완성하면 이름을 모두 출력한다. 처음으로 이기는 수만 보고 그 뒤의 수는 모두 무시한다. 주어진 수를 모두 놓은 뒤에도 승리 구조가 없으면 none을 출력한다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 판 한 변의 칸 수 $S$와 놓는 수의 개수 $M$이 공백을 사이에 두고 주어진다. 다음 $M$개의 줄에는 돌을 놓는 순서대로 칸의 좌표 $x$와 $y$가 공백을 사이에 두고 주어진다. 모든 수는 크기가 $S$인 판 안의 칸이다. 각 테스트 케이스에서 판은 비어 있는 상태로 시작하고, 같은 칸에 두 번 놓지 않는다.

제한

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

각 테스트 케이스마다 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

$n$은 테스트 케이스 번호로 1부터 세고, $k$는 승리 구조를 완성한 수의 번호로 1부터 센다. 이름이 여러 개일 때는 bridge, fork, ring 순서로 하이픈을 넣어 이어 붙인다.

하바나는 크리스티안 프렐링과 MindSports가 만든 게임이다. MindSports와 크리스티안 프렐링은 이 문제를 보증하지 않으며 이 문제와 아무 관련이 없다.