Problem K
Captured by Aliens

“While the Baroque rules of Chess could only have been created by humans, the rules of Go are so elegant, organic, and rigorously logical that if intelligent life forms exist elsewhere in the universe they almost certainly play Go.” – Edward Lasker

Astounding news, it was found that aliens exist, and they do play Go! To check that no planets with intelligent life are in the way of an intergalactic highway construction project for a hyperspace express route, they have broadcast a number of game records to see if there is any intelligent response. It is up to you to reply to the aliens with the number of stones captured in each game, and prevent the imminent destruction of our planet.

In the game of Go, there are two players (black and white) who alternate moves, placing a single stone of their colour on an empty intersection of a square board with $S \times S$ intersections. Two intersections are adjacent if they are connected by a horizontal or vertical line with no other intersections between them. A group of stones is defined by taking a single stone and adding all other stones of the same colour which can be reached through repeatedly following adjacent stones. A group is captured if it is surrounded by the opponent such that it has no empty adjacent intersections. Note that spaces beyond the edges of the board do not count as empty. A captured group is removed from the board, the intersections it used to occupy become empty, and can be played on again. If a move would cause a group from both players to be captured, only the group of the player who didn’t make the last move gets captured. Note that it is possible to capture multiple groups with the same move.

NB. unlike in most human rule sets, there are no further restrictions: the aliens are fine with ‘suicidal’ moves that cause a player’s own stones to get captured, or a ko pattern in which stones repeatedly capture each other back and forth. In addition, due to their brains being the size of the universe, they prefer arbitrarily sized boards over our usual $19 \times 19$ sized boards.

Figure 1: Example of the top left of a board with moves and captures. The position (A) starts with three black groups and three white groups. Each move is marked in red. In (B), white captures three black stones. In (E) black captures one white stone. In (H) white captures two black stones. In total, six stones were captured.

Input

The first line contains two integers, $S, M$: the size of the board, and the total number of moves played. The board has $S \times S$ intersections.

Next follow $M$ lines describing the moves, each with two integers $0 \leq x,y < S$, the coordinates of the move played.

Output

Output a single line with the total number of captured stones.

Limits

• $0 < S \leq 10^5$

• $0 < M \leq 25\, 000$

2 6
0 1
0 0
1 0
0 0
0 0
1 1

5