Problem E
Clumsy Cardinals

Everyone knows that in the game chess, a bishop moves diagonally. Boring! Consider a new piece called a cardinal. A cardinal moves diagonally, like a bishop but they are clumsy. If its movement brings a cardinal adjacent to another piece, it trips and falls on the other piece. This results in the other piece being captured and removed from the board. The cardinal that was moving then rests on the captured piece’s square. Note two squares are adjacent if they share a side, meaning they are directly horizontal or vertical from one another. A cardinal can also capture pieces like a bishop if the other piece lies on the same diagonal. A cardinal can only move if the movement results in the capture of another piece.

In this problem, you are given the initial locations of cardinal pieces on an infinite chessboard. Determine the minimum number of cardinals that remain on the board under some sequence of valid moves.

Figure 1: Illustration of a sequence of moves for sample input 3 that reduces the number of cardinals to 3. Step 1: Move the cardinal at $(1, 2)$ to capture the cardinal at $(3, 4)$. Step 2: Move the cardinal at $(1, 0)$ to capture the cardinal at $(7,5)$. That is, the moving cardinal “trips” beside the cardinal at $(7, 5)$ and captures it. Step 3: Move the cardinal that is currently at $(3, 4)$ to capture the cardinal at $(1, 7)$. Step 4: Move the cardinal at $(7, 1)$ to capture the cardinal at $(1, 7)$. Note at this time there is no cardinal at $(3, 4)$ so we move the cardinal past this square without “tripping” onto it. The final squares with cardinals are $(1, 7)$, $(3, 7)$, and $(7, 5)$ and we cannot move any remaining cardinal to capture another cardinal.

Input

The first line of input contains a single integer $N$ ($1 \leq N \leq 10^5$), which is the number of cardinal pieces to consider.

The next line contains $2N$ space-separated integers $r_1, c_1, r_2, c_2, \ldots , r_ N, c_ N$ ($-10^{9} \leq r_ i, c_ i \leq 10^9$). These give the initial cardinal locations, so cardinal $i$ initially lies on square $(r_ i, c_ i)$. Furthermore, $|r_ i-r_ j| \geq 2$ or $|c_ i-c_ j| \geq 2$ (or both) for any $1 \leq i < j \leq N$.

Output

Display the minimum number of cardinals that remain on the board though some sequence of valid moves.

3
-1 0 4 4 7 1

1

4
0 0 4 4 10 12 30 -7

2

7
1 0 1 2 1 7 3 4 3 7 7 1 7 5

3