MegaDamas

MegaDamas는 두 사람이 하는 보드 게임으로, 잘 알려진 체커(다마)와 매우 비슷하다. 보드는 직사각형이고, 작은 정사각형 칸이 $N$행 $M$열의 격자로 놓여 있다. 칸은 보통의 체커 판처럼 밝은 색과 어두운 색으로 번갈아 칠해져 있다. 어두운 색 칸을 "집"이라고 부른다. 다만 보기 쉽도록 아래 그림에서는 집을 흰 칸으로 그렸다.

게임을 시작할 때 각 플레이어는 말을 몇 개씩 가지고, 자신이 고른 보드 가장자리에 가장 가까운 집에 말을 놓는다. 두 플레이어는 서로 반대쪽 가장자리를 고른다. 게임 중에 말은 보드의 집에만 놓일 수 있다.

게임의 동작 중 하나는 상대의 말을 대각선으로 뛰어넘어 그 너머의 인접한 집으로 옮겨 가서 그 말을 "잡는" 것이다. 이때 도착하는 집은 비어 있어야 하고, 잡힌 상대의 말은 보드에서 제거된다. 잡기에 관련된 세 집(내 말이 출발하는 집, 상대의 말이 있는 집, 내 말이 도착하는 빈 집)은 아래 그림처럼 한 대각선 위에 연달아 인접해 있어야 한다.

MegaDamas에서는 말이 대각선 앞쪽으로도 뒤쪽으로도 뛰어넘어 상대의 말을 잡을 수 있다(대부분의 체커 변형에서는 앞쪽으로 뛰어넘을 때만 잡을 수 있다). 말 하나로 빈 집을 향해 상대 말을 연달아 뛰어넘는 연속 잡기도 할 수 있다. 연속 잡기에서는 방향을 바꿀 수 있어서, 처음에는 한 방향으로 뛰고 다음에는 다른 방향으로 뛰어도 된다. 한 번 뛸 때 잡을 수 있는 말은 하나뿐이지만, 연달아 뛰어서 여러 개를 잡을 수 있다. 자기 말은 뛰어넘을 수 없고, 같은 상대 말을 두 번 이상 뛰어넘을 수 없다. 움직이는 말이 떠난 집은 빈 집이 된다.

보드의 크기와 현재 게임 상태가 주어진다. 지금은 당신의 차례이다. 한 번의 잡기 동작으로 잡을 수 있는 상대 말의 최대 개수를 구하시오. 잡을 수 있는 말이 없으면 답은 0이다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫째 줄에는 보드의 행의 수 $N$과 열의 수 $M$이 주어진다 ($3 \le N \le 20$, $3 \le M \le 20$, $N \times M \le 200$). 보드에서 내 쪽 가장자리의 가장 왼쪽 칸은 집이다. 따라서 내 쪽부터 센 $i$번째 줄($i$는 1부터 센다)에서는 $i$가 홀수이면 1, 3, 5, ...번째 열이, 짝수이면 2, 4, 6, ...번째 열이 집이다.

둘째 줄에는 게임 상태가 주어진다. 게임 상태는 공백 하나로 구분된 $\lceil (N \times M)/2 \rceil$개의 정수이고, 각 정수는 보드의 집 하나에 대응한다. 집에는 1부터 $\lceil (N \times M)/2 \rceil$까지 번호가 붙어 있다. 번호는 내 쪽 가장자리의 줄부터 상대 쪽 가장자리의 줄까지 차례로 매기고, 한 줄 안에서는 왼쪽에서 오른쪽으로 매긴다. 게임 상태에서 0은 빈 집, 1은 내 말이 있는 집, 2는 상대 말이 있는 집을 뜻한다. 보드 위에 있는 각 플레이어의 말은 $\lfloor (N \times M)/4 \rfloor$개 이하이다.

입력의 끝은 $N = M = 0$인 줄로 표시한다.

그림 1: (a) $8 \times 8$ 보드와 (b) $5 \times 3$ 보드의 집 번호.

각 테스트 케이스마다 한 번의 잡기 동작으로 잡을 수 있는 상대 말의 최대 개수를 한 줄에 하나씩 출력한다.