#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
bool bo[110][110];
int match[N],chw[N],tsp;
// 每个格子(x,y)，编号为(x-1)*n+y；且x+y是偶数则格子为公牛，否则为母牛 
vector<int>G[N];
bool findmuniu(int x)
{
    for(int y:G[x])
        if(chw[y]!=tsp)
		{
            chw[y]=tsp;
            if(match[y]==0||findmuniu(match[y]))
			{
                match[y]=x;
                return 1;
            }
        }
    return 0;
}
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int main()
{
    int n,m;scanf("%d%d",&n,&m);
    memset(bo,0,sizeof(bo));
    for(int i=1,x,y;i<=m;i++)scanf("%d%d",&x,&y),bo[x][y]=1;
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(!bo[i][j]&&(i+j)%2==0)
        for(int k=0;k<=3;k++)
		{
            int x=dx[k]+i,y=dy[k]+j;
            if(x>0&&x<=n&&y>0&&y<=n&&!bo[x][y])G[(i-1)*n+j].emplace_back((x-1)*n+y);
        }

    int ans=0;tsp=0;
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(!bo[i][j]&&(i+j)%2==0)
	{
        tsp++;
        if(findmuniu((i-1)*n+j)) ans++;
    }
    printf("%d",ans);
    return 0;
}