#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F(i,k,n) for (int i=(k);i<=(n);i++)
const int N=4e4+10;
vector<int>e[N];
char mp[210][210];
int c[210][210];
bool k[210][210];
int num[210][210];
int n,sx,sy,idx1,idx2;
struct node{
	int x,y,C;
};
int dx[]={-1,-2,1,2,-1,-2,1,2};
int dy[]={-2,-1,-2,-1,2,1,2,1};
queue<node>q;
int match[N];
int tim[N];
int T,m,a,b;
bool dfs(int u){
	if (tim[u]==T) return 0;
	tim[u]=T;
	F(i,0,(int)e[u].size()-1){
		int v=e[u][i];
		if (!match[v] || dfs(match[v])){
			match[v]=u;
			return 1;
		}
	}
	return 0;
}
bool check(int i,int j){
	return (0<i && i<=n && 0<j && j<=n);
}
void bfs(int sx,int sy){
	q.push({sx,sy,1});
	k[sx][sy]=1;
	c[sx][sy]=1;
	while (q.size()){
		node u=q.front();q.pop();
		F(i,0,7){
			int vx=u.x+dx[i],vy=u.y+dy[i];
			if (!check(vx,vy) || k[vx][vy] || mp[vx][vy]=='1') continue;
			k[vx][vy]=1;
			c[vx][vy]=3-u.C;
			q.push({vx,vy,c[vx][vy]});
		}
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	F(i,1,n) F(j,1,n) mp[i][j]='0';
	F(i,1,m){
		cin>>a>>b;
		mp[a][b]='1';
	}
	F(i,1,n){
		F(j,1,n){
			if (mp[i][j]=='0' && !k[i][j]){
				bfs(i,j);
			}
		}
	}
	F(i,1,n){
		F(j,1,n){
			if (c[i][j]==1){
				idx1++;
				num[i][j]=idx1;
			}
			if (c[i][j]==2){
				idx2++;
				num[i][j]=idx2;
			}
		}
	}
	F(i,1,n){
		F(j,1,n){
			if (c[i][j]==1){
				F(k,0,7){
					int ux=i+dx[k],uy=j+dy[k];
					if (check(ux,uy) && c[ux][uy]==2){
						e[num[i][j]].push_back(num[ux][uy]);
					}
				}
			}
		}
	}
	F(i,1,n){
	//	F(j,1,n) cout<<c[i][j]<<' ';
	//	cout<<'\n';
	}
	int ans=0;
	F(i,1,idx1){
		T++;
		if (dfs(i)) ans++; 
	}
	cout<<idx1+idx2-ans;
	return 0;
}