2742: 骑士共存问题

一张大小为n*n的国际象棋棋盘，上面有一些格子被拿走了。你的任务是确定在这个棋盘上放置尽可能多的马并使他们不互相攻击。

第一行包含2个整数n和m，用单个的空格分开，1<=n<=200 , 0<=m<n²；n 是国际象棋棋盘的大小，m是被拿走的格子数。下面m行每行包含 2 个整数：x和y，用单个的空格分开，1<=x,y<=n，这些是被拿走的格子的坐标。棋盘的左上角的坐标是(1,1)，右下角是(n,n)。拿走的格子没有重复的。

一个整数(仅仅在文件的第一行)。它应该是能放在国际象棋棋盘上的互不攻击对方的马的最大的数量。

3 2
1 1
3 3

5