서로 공격하지 않는 나이트

$n \times n$ 크기의 체스판에서 일부 칸이 제거되어 있다. 남아 있는 칸 위에 어떤 두 나이트도 서로를 공격하지 않도록 놓을 수 있는 체스 나이트의 최대 개수를 구하여라.

그림 1: 칸 S에 놓인 나이트는 x로 표시된 칸들을 공격한다.

다음을 수행하는 프로그램을 작성하여라.

• 제거된 칸이 표시된 체스판의 정보를 표준 입력에서 읽어 들인다.
• 이 체스판 위에 서로 공격하지 않도록 놓을 수 있는 나이트의 최대 개수를 구한다.
• 그 결과를 표준 출력에 쓴다.

첫째 줄에 두 정수 $n$과 $m$이 주어진다. 이때 $1 \le n \le 200$, $0 \le m \le n^2$이다. $n$은 체스판의 크기이고, $m$은 제거된 칸의 개수이다.

이어지는 $m$개의 줄에는 각각 제거된 칸의 좌표인 두 자연수 $x$와 $y$가 공백 하나로 구분되어 주어진다 ($1 \le x, y \le n$). 체스판의 왼쪽 위 모서리 좌표는 $(1, 1)$이고, 오른쪽 아래 모서리 좌표는 $(n, n)$이다. 같은 칸이 두 번 이상 주어지지 않는다.

남아 있는 칸에 서로 공격하지 않도록 놓을 수 있는 나이트의 최대 개수를 나타내는 정수 하나를 한 줄에 출력한다.