#include<bits/stdc++.h>
using namespace std;
const int N=105;
int match[N*N];
bool vis[N*N],a[N][N];
int head[N*N],nxt[N*N*2],ver[N*N*2],tot=0;
inline void add(int u,int v){
	nxt[++tot]=head[u];
	ver[tot]=v;
	head[u]=tot;
}
bool dfs(int u){//增广路算法 
	for(int i=head[u];i;i=nxt[i]){
		int v=ver[i];
		if(!vis[v]){
			vis[v]=1;
			if(!match[v] || dfs(match[v])){
				match[v]=u;
				return 1;
			}
		}
	}
	return 0;
}
int main(){
	int n,t,ans=0;
	memset(a,0,sizeof(a));
	cin>>n>>t;
	for(int i=1;i<=t;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		a[x][y]=1;
	}
	for(int i=1;i<=n;i++){//横边 
		for(int j=2;j<=n;j++){
			if(!a[i][j] && !a[i][j-1]){
				int x=(i-1)*n+j;
				int y=(i-1)*n+j-1;
				if((i+j)%2) add(x,y);//从黑连向白 
				else add(y,x);
			}
		}
	}
	for(int i=2;i<=n;i++){//竖边 
		for(int j=1;j<=n;j++){
			if(!a[i][j] && !a[i-1][j]){
				int x=(i-1)*n+j;
				int y=(i-2)*n+j;
				if((i+j)%2) add(x,y);//从黑连向白 
				else add(y,x);
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if((i+j)%2){//只扫黑格 
				memset(vis,0,sizeof(vis));
				if(!a[i][j] && dfs((i-1)*n+j)) ans++;
			}
		}
	}
	cout<<ans;
}