C++ :

#include<iostream>
using namespace std;
int n,m,ans(0),a[5005][10],match[5005],x=0,y=0,num[10005];
bool used[5005],can[10005];
void init()
{
	cin>>n>>m;
	fill(can,can+10005,1);
	for (int i=1,b,c;i<=m;i++)
    {
    cin>>b>>c;
    can[(b-1)*n+c]=false;
    }
    for (int i=1;i<=n;i++)
    for (int j=1;j<=n;j++)
    if ((i+j)%2==0&&can[(i-1)*n+j]) num[(i-1)*n+j]=(++y);
    for (int i=1;i<=n;i++)
    for (int j=1;j<=n;j++)
    {
    	if ((i+j)%2==1&&can[(i-1)*n+j])
    	{
		    a[++x][0]=0;
		    if (can[(i-1)*n+j-1]&&j-1>0)
		    a[x][++a[x][0]]=num[(i-1)*n+j-1];
		    if (can[(i-1)*n+j+1]&&j+1<=n)
		    a[x][++a[x][0]]=num[(i-1)*n+j+1];
		    if (can[(i-2)*n+j]&&i-2>=0)
            a[x][++a[x][0]]=num[(i-2)*n+j];
            if (can[(i)*n+j]&&i<n)
            a[x][++a[x][0]]=num[(i)*n+j];
        }
    
}
}
bool cross(int k)
{
	if (!k) return false;
	for (int i=1;i<=a[k][0];i++)
	{
		int j=a[k][i];
		if (!used[j])
		{
			used[j]=true;
			if (!match[j]||cross(match[j]))
            {
             match[j]=k;
             return true;
            }
		}
	}
	return false;
}
void solve()
{
	for (int i=1;i<=x;i++)
	{
		if (cross(i))
		ans++;
		fill(used,used+5005,0);
	}
}
int main()
{
	init();
	solve();
	cout<<ans<<endl;
	return 0;
}