Go

Go is a board game for two players that started in China more than 2,000 years ago. The game is known for deep strategy even though its rules are fairly simple.

The two players alternately place black and white stones on the vacant intersections of a grid of $N \times N$ orthogonal lines. Each player tries to claim a larger territory than the opponent.

The horizontal lines are numbered from top to bottom from 1 to $N$, and the vertical lines are numbered from left to right from 1 to $N$.

Two intersections or two stones are adjacent when one of them sits directly right, left, above or below the other. A solidly connected group is a set of intersections or stones in which every pair is joined by a path of adjacent intersections or stones from the same set.

A solidly connected group of empty intersections, or of stones, is surrounded by a color when every intersection adjacent to the group holds a stone of that color.

A player's territory is every intersection holding one of that player's stones, plus every solidly connected group of empty intersections surrounded by that player's stone color.

Here are the rules of a simplified version of the game.

1. The board is empty at the beginning of the game.
2. Each player has stones of one color, black or white.
3. Black gets the first turn, then the players alternate turns.
4. A move consists of placing one stone of one's own color on an empty intersection on the board.
5. A player may pass his turn at any time and give the turn to the other player.
6. A solidly connected group of stones of one color is captured and removed from the board once it is surrounded by the opponent.
7. Self-capture happens when your move causes some of your stones to be captured and thus removed.
8. In case of a move causing a group from both players to be captured, capture of the opponent takes precedence over self-capture.

A group can have no adjacent intersections at all, which happens when $N = 1$. The same definitions still apply. A group of stones with no adjacent empty intersection is captured, and a group of empty intersections with no adjacent stone belongs to neither player.

You are given the size of the board and a sequence of moves. Validate this sequence and print the index of the first invalid move, counting from 1. A move is invalid when the player tries to put a stone on an intersection that is not empty. If all moves are valid, print the sizes of the territories for each player after the last move.

The first line contains a single integer $T$, the number of test cases ($1 \le T \le 100$). After that follow the specifications of $T$ test cases.

Each test case is specified on $S + 1$ lines. The first line contains two integers $N$ and $S$, the size of the board and the number of moves to validate ($1 \le N \le 20$, $1 \le S \le 1000$). Each of the remaining $S$ lines contains either two zeros, which means a pass turn, or two integers $R$ and $C$, the horizontal and vertical line numbers of the player's move ($1 \le R, C \le N$).

Each line is one turn. A pass uses up a turn, so the first line is black's turn, the second line is white's turn, and the third line is black's turn again.

For each test case, print one of two outputs on a single line.

• Invalid X if there is at least one invalid move, where $X$ is the index of the earliest invalid move. Passing the turn to the other player does not count as a move.
• B W if there are no invalid moves, where $B$ and $W$ are the sizes of the black and white territories.

Take a board with $N = 4$. Black plays (1, 2), white plays (1, 1), then black plays (2, 1). The only intersections adjacent to the white stone on (1, 1) are (1, 2) and (2, 1), and black holds both, so that white stone is captured. White may play (1, 1) again, because the intersection is empty now, but the new stone is immediately surrounded by black and removed as a self-capture. Black then plays (2, 2), which leaves three black stones on the board. The remaining thirteen empty intersections split into two groups, and both touch black stones only, so black's territory is 16 and white's is 0.