Havannah (작은 입력)

Havannah는 Christian Freeling이 만든 추상 전략 보드게임이다. 한 변에 육각형이 $S$개씩 놓인 육각형 판 위에서 진행한다. 육각형마다 가로 변이 2개, 비스듬한 변이 4개 있다. 각 육각형은 정수 두 개의 쌍으로 나타낸다. 판의 아래쪽 꼭짓점에 있는 육각형은 $(1, 1)$이다. $(x, y)$에서 2시 방향으로 이웃한 육각형은 $(x, y+1)$이고, 10시 방향으로 이웃한 육각형은 $(x+1, y)$이다. 다음은 $S = 5$인 판이다.

육각형 하나에는 돌을 최대 하나만 놓을 수 있다. 한 번 놓은 돌은 치우지도 옮기지도 않는다. 목표는 아래 세 가지 중 하나에 해당하는, 서로 이어진 돌의 집합을 만드는 것이다.

• ring: 빈 육각형을 하나 이상 둘러싼다. 둘러싸인 육각형 중 적어도 하나는 비어 있어야 한다. 즉 돌이 놓인 육각형에 막혀서 판의 바깥 경계와 이어지지 않는 빈 육각형이 있어야 한다. 이 규칙은 원래 Havannah 규칙과 다르다.
• bridge: 판의 꼭짓점 두 곳을 잇는다.
• fork: 판의 여섯 변 중 세 변을 잇는다. 꼭짓점은 양옆 어느 변에도 속하지 않는다.

다음 그림은 이기는 모양의 예시다.

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

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 정수 두 개 $S$와 $M$이 주어진다. $S$는 판 한 변의 육각형 개수이고, $M$은 놓는 수의 개수다. 이어지는 $M$개의 줄에는 돌을 놓는 순서대로 육각형의 좌표 $x$와 $y$가 공백으로 구분되어 주어진다. 모든 수는 크기가 $S$인 판 위에 있다. 각 테스트 케이스는 빈 판에서 시작하고, 같은 육각형에 두 번 놓는 일은 없다.

제한

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

각 테스트 케이스마다 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$은 테스트 케이스 번호, $k$는 이기는 모양을 완성한 수의 번호다. 둘 다 1부터 센다.

Havannah는 Christian Freeling과 MindSports가 만들었다. Christian Freeling과 MindSports는 이 문제를 보증하지 않으며, 이 문제와 아무런 관련이 없다.