바둑

바둑은 2,000년도 더 전에 중국에서 시작된 두 사람이 겨루는 보드 게임이다. 규칙은 비교적 단순하지만 전략이 깊은 게임으로 알려져 있다.

두 사람은 가로 세로 $N$개의 선이 만드는 격자의 빈 교점에 검은 돌과 흰 돌을 번갈아 놓는다. 자기 돌로 상대보다 넓은 영역을 차지하는 것이 목표다.

가로선은 위에서 아래로 1부터 $N$까지 번호를 붙이고, 세로선은 왼쪽에서 오른쪽으로 1부터 $N$까지 번호를 붙인다.

두 교점 또는 두 돌이 위, 아래, 왼쪽, 오른쪽으로 맞닿아 있으면 인접하다고 한다. 어떤 집합의 임의의 두 원소가 그 집합 안의 인접한 교점 또는 돌만 거쳐 이어질 때, 이 집합을 연결 그룹이라고 한다.

빈 교점으로 이루어진 연결 그룹이나 돌로 이루어진 연결 그룹에 인접한 모든 교점이 어떤 색의 돌로 채워져 있으면, 그 그룹은 그 색에 둘러싸였다고 한다.

한 사람의 영역은 자기 돌이 놓인 교점 전부와, 자기 돌 색에 둘러싸인 빈 교점 연결 그룹 전부로 이루어진다.

간단하게 바꾼 규칙은 다음과 같다.

1. 게임을 시작할 때 판은 비어 있다.
2. 두 사람은 각각 한 가지 색(검은색 또는 흰색)의 돌을 쓴다.
3. 흑이 먼저 두고, 그다음부터 두 사람이 차례를 번갈아 가진다.
4. 한 수는 자기 색 돌 하나를 판의 빈 교점에 놓는 것이다.
5. 자기 차례에 언제든지 패스해서 차례를 상대에게 넘길 수 있다.
6. 같은 색 돌로 이루어진 연결 그룹은 상대에게 둘러싸이는 순간 잡혀서 판에서 제거된다.
7. 자기가 둔 수 때문에 자기 돌이 잡혀서 제거되기도 한다. 이것이 자살수다.
8. 한 수로 두 사람의 그룹이 함께 잡히는 경우, 상대 그룹을 잡는 쪽이 자살수보다 먼저 적용된다.

그룹에 인접한 교점이 아예 없을 수도 있다($N = 1$인 경우). 이때도 같은 정의를 그대로 적용한다. 인접한 빈 교점이 하나도 없는 돌 그룹은 잡히고, 인접한 돌이 하나도 없는 빈 교점 그룹은 어느 쪽의 영역도 아니다.

판의 크기와 수의 순서가 주어진다. 이 순서를 검사해서 잘못된 첫 번째 수의 번호를 출력한다. 번호는 1부터 시작한다. 이미 돌이 놓인 교점에 돌을 놓으려고 하는 수가 잘못된 수다. 모든 수가 올바르면 마지막 수를 둔 뒤 두 사람의 영역 크기를 출력한다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다($1 \le T \le 100$). 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스는 $S + 1$개의 줄로 이루어진다. 첫째 줄에는 판의 크기 $N$과 검사할 수의 개수 $S$가 주어진다($1 \le N \le 20$, $1 \le S \le 1000$). 이어지는 $S$개의 줄에는 각각 두 정수가 주어진다. 두 정수가 모두 0이면 패스이고, 그렇지 않으면 그 수를 둔 가로선 번호 $R$과 세로선 번호 $C$다($1 \le R, C \le N$).

각 줄이 한 번의 차례에 해당한다. 패스도 차례를 소모하므로 첫째 줄은 흑, 둘째 줄은 백, 셋째 줄은 다시 흑의 차례다.

각 테스트 케이스마다 다음 두 가지 중 하나를 한 줄에 출력한다.

• 잘못된 수가 하나라도 있으면 Invalid X를 출력한다. $X$는 가장 먼저 나오는 잘못된 수의 번호다. 차례를 상대에게 넘기는 패스는 수로 세지 않는다.
• 잘못된 수가 없으면 B W를 출력한다. $B$와 $W$는 각각 흑과 백의 영역 크기다.

$N = 4$인 판을 생각해 보자. 흑이 (1, 2), 백이 (1, 1), 이어서 흑이 (2, 1)에 둔다. (1, 1)의 백돌에 인접한 교점은 (1, 2)와 (2, 1)뿐이고 둘 다 흑돌이므로 이 백돌은 잡힌다. 백은 (1, 1)에 다시 둘 수 있다. 그 교점이 비었으니 올바른 수지만, 놓는 순간 흑에게 둘러싸여 자살수로 제거된다. 다음으로 흑이 (2, 2)에 두면 판에는 흑돌 세 개가 남는다. 남은 빈 교점 열세 개는 두 그룹으로 나뉘고 두 그룹 모두 흑돌에만 인접하므로, 흑의 영역은 16, 백의 영역은 0이다.