Non-Attacking Knights

You are given an $n \times n$ chessboard from which some squares have been removed. Determine the maximum number of chess knights that can be placed on the remaining squares so that no two knights attack each other.

Figure 1: a knight placed on square S attacks the squares marked with x.

Write a program that:

• reads the description of the board together with its removed squares from standard input,
• computes the maximum number of mutually non-attacking knights that can be placed on the board,
• writes the result to standard output.

The first line contains two integers $n$ and $m$, where $1 \le n \le 200$ and $0 \le m \le n^2$. Here $n$ is the size of the board and $m$ is the number of removed squares.

Each of the next $m$ lines contains a pair of integers $x$ and $y$ ($1 \le x, y \le n$) separated by a single space, giving the coordinates of a removed square. The top-left corner of the board has coordinates $(1, 1)$ and the bottom-right corner has coordinates $(n, n)$. No square is listed more than once.

Print exactly one line containing a single integer: the maximum number of mutually non-attacking knights that can be placed on the given board.