비숍 배치 2

체스의 비숍은 대각선 방향으로 원하는 만큼 이동할 수 있으며, 이동 경로에 있는 말을 잡을 수 있다. 아래 그림에서 B에 놓인 비숍은 같은 대각선 위의 O 칸에 있는 말을 잡을 수 있다.

<그림 1>

체스판에는 비숍이 지나갈 수 없는 장애물이 놓일 수 있다. 장애물이 대각선 경로 위에 있으면, 비숍은 그 장애물 너머로 이동하거나 공격할 수 없다.

<그림 2>

정사각형 체스판의 크기는 한 변에 있는 칸의 수이다. 체스판의 크기와 장애물의 위치가 주어질 때, 어떤 두 비숍도 서로를 잡을 수 없도록 놓을 수 있는 비숍의 최대 개수를 구하라.

그림 2의 체스판에서는 그림 3처럼 최대 10개의 비숍을 놓을 수 있다.

<그림 3>

첫째 줄에 정사각형 체스판의 크기 N이 주어진다. 둘째 줄에 체스판 위에 놓인 장애물의 개수 M이 주어진다.

N은 100 이하의 자연수이고, M은 음이 아닌 정수이다. 다음 M개 줄에는 장애물이 놓인 칸의 위치가 한 줄에 하나씩 주어진다. 각 위치는 위에서부터 몇 번째 행인지와 왼쪽부터 몇 번째 열인지를 나타내는 두 자연수로 주어진다.

첫째 줄에 체스판 위에 놓을 수 있는 비숍의 최대 개수를 출력한다.