#include<bits/stdc++.h>
using namespace std;
const int qwq = 255 + 10;
const int inf = 0x3f3f3f3f;
int n,m,a[qwq][qwq],id;
int head[qwq],to[qwq],ne[qwq],w[qwq];
int vis[qwq],dep[qwq],pre[qwq];
int dx[8]= {1,1,-1,-1,2,2,-2,-2};
int dy[8]= {2,-2,2,-2,1,-1,1,-1};
int s,t,ans;
void add(int x,int y) {
	++id;
	to[++id] = y,ne[id] = head[x], head[x] = id;
}
int point(int x,int y) {
	return (x-1)*n+y;
}
bool bfs() {
	memset(dep,0,sizeof(dep));
	queue<int> q;
	q.push(s);
	vis[s] = 1;
	dep[s] = 1;
	while(!q.empty()) {
		int t = q.front();
		q.pop();
		for(int i = head[t]; i ; i = ne[i]) {
			int v = to[i];
			if(!w[i] || dep[v])
				continue;
			dep[v] = dep[t] + 1;
			q.push(v);
		}
	}
	return dep[t];

}
int dfs(int u,int fl) {
	if(u == t)
		return fl;
	int ss = 0;
	for(int i = head[u] ; i ; i = ne[i]) {
		if(ss == fl)
			return fl;
		int v = to[i];
		if(dep[v] != dep[u] + 1 || !w[i])
			continue;
		int k = dfs(v,min(w[i] , fl - ss));
		if(k > 0) {
			ss += k;
			w[i] -= k,w[i ^ 1] += k;
		}
	}
	if(!ss)
		dep[u] = 0;
	return ss;
}
int dinic() {
	int cnt = 0;
	while(bfs()) {
		int x = 1;
		while(x) {
			x = dfs(s,inf);
			cnt += x;
		}
	}
	return cnt;
}
int main() {
	cin>>n>>m;
	for(int i = 1; i <= m; i++) {
		int x,y;
		cin>>x>>y;
		a[x][y] = 1;
		add(x,y),add(y,x);
	}
	s = n * n + 1,t = s + 1;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			if(a[i][j])
				continue;
			if((i + j) & 1)
				add(s , point(i , j));
			else
				add(point(i , j) , t);
			if((i + j) % 2 == 0)
				continue;
			for(int k = 0; k < 8; k++) {
				int x = dx[i] + i;
				int y = dy[i] + j;
				if(x < 1 || y < 1 || x > n || y > n)
					continue;
				if(a[x][y])
					continue;
				add(point(i , j), point(x , y));
			}
		}
	}
	cout<<n * n - m - dinic()<<endl;
	return 0;
}