#include <bits/stdc++.h>
using namespace std;

const int N=105, M=N*N*4;
int ver[M],nxt[M],head[N*N],tot=1;
int n,t,ans;
bool ban[N][N],v[N*N];
int  match[N*N];
int dt[]={0,1,0,-1,0}; //{dt[i],dt[i+1]}: dir

void add(int x,int y){
    ver[++tot]=y,nxt[tot]=head[x],head[x]=tot;
}

bool dfs(int x){
    for(int i=head[x];i;i=nxt[i]){
        int y=ver[i];
        if(v[y])continue;
        v[y]=true;
        if(!match[y] || dfs(match[y])){
            match[y]=x;
            return true;
        }
    }
    return false;
}

int main(){
    cin>>n>>t;
    for(int i=1;i<=t;i++){
        int x,y;
        cin>>x>>y;
        ban[x][y]=true;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            if( ( (i+j)&1 ) || ban[i][j] ) continue;
            for(int k=0;k<4;k++){
                int x=i+dt[k], y=j+dt[k+1];
                if(x<1 || x>n || y<1 || y>n || ban[x][y])continue;
                add((i-1)*n+j,(x-1)*n+y);
            }
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            if( (i+j)&1 )continue;
            memset(v,0,sizeof v);
            if( dfs( (i-1)*n+j ) ) ans++;
        }
    cout<<ans<<endl;
}