C++ :

//AUTHOR::STDAFX
//ALGORITHM::Hungary

#define MAXN 110UL
#define MAXQ 20000UL

#include <cstdio>
#include <cstring>

using namespace std;

void BFS(int,int);
inline int cal(int);
inline int calpos(int,int);
bool dfs(int);

struct Edge{
	int v,nx;
};

struct Point{
	int x,y;
};

struct queue{
	int head,tail;
	Point data[MAXQ];
	inline void clr(){
		head=0;tail=-1;
		return;
	}
	inline void push(Point temp){
		data[++tail]=temp;
		return;
	}
	inline bool empty(){
		return tail<head;
	}
	inline void pop(){
		head++;
		return;
	}
	inline Point front(){
		return data[head];
	}
};

int n,m,color[MAXN][MAXN],tempx,tempy,new_color,newx,newy,x,y,headlist[MAXQ],edge_cs,tempid,newid,ans,link[MAXQ];
int cx[6]={0,1,-1,0,0};
int cy[6]={0,0,0,-1,1};

bool Map[MAXN][MAXN];
bool used[MAXQ];

Point temp;

Edge edge[MAXQ<<1];

queue que;

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		Map[x][y]=1;
	}
	//BFS
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(!Map[i][j]&&!color[i][j]){
				BFS(i,j);
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(color[i][j]==2) continue;
			for(int k=1;k<=4;k++){
				newx=i+cx[k];newy=j+cy[k];
				if(newx<1||newx>n) continue;
				if(newy<1||newy>n) continue;
				if(Map[newx][newy]) continue;
				if(color[newx][newy]==1) continue;
				tempid=calpos(i,j);newid=calpos(newx,newy);
				edge[++edge_cs].v=newid;
				edge[edge_cs].nx=headlist[tempid];
				headlist[tempid]=edge_cs;
			}
		}
	}
	//Hungary
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(!Map[i][j]&&color[i][j]==1){
				memset(used,0,sizeof(used));
				if(dfs(calpos(i,j))){
					ans++;
				}
			}
		}
	}
	printf("%d",ans);
	return 0;
}

inline int cal(int temp){
	if(temp==1){
		return 2;
	}
	return 1;
}

inline int calpos(int x,int y){
	return n*(x-1)+y;
}

bool dfs(int u){
	for(int i=headlist[u];i!=0;i=edge[i].nx){
		if(!used[edge[i].v]){
			used[edge[i].v]=1;
			if(link[edge[i].v]==0||dfs(link[edge[i].v])){
				link[edge[i].v]=u;
				return true;
			}
		}
	}
	return false;
}

void BFS(int stx,int sty){
	color[stx][sty]=1;
	que.clr();
	temp.x=stx;temp.y=sty;
	que.push(temp);
	while(!que.empty()){
		tempx=que.front().x;tempy=que.front().y;
		new_color=cal(color[tempx][tempy]);
		que.pop();
		for(int i=1;i<=4;i++){
			newx=tempx+cx[i];newy=tempy+cy[i];
			if(newx<1||newx>n) continue;
			if(newy<1||newy>n) continue;
			if(color[newx][newy]||Map[newx][newy]) continue;
			color[newx][newy]=new_color;
			temp.x=newx;temp.y=newy;
			que.push(temp);
		}
	}
	return;
}