#include <cstdio>
#include <queue>
#include <cstring>
#define MAXN 2000
#define INF 0x7f7f7f7f
#define QWQ cout << "QWQ" << endl;
using namespace std;
int min(int x, int y) {return ((x < y) ? (x) : (y));}
struct node {
	int id, val;
	int next;
} gra[MAXN * MAXN * 2 + 10];
int n, m, s, t;
int tot = 1, head[MAXN * MAXN + 10], dis[MAXN * MAXN + 10], Now[MAXN * MAXN + 10];
int dx[5] = {0, 0, 0, 1, -1};
int dy[5] = {0, 1, -1, 0, 0};
int ddx[9] = {0, 1, -1, 2, -2, 1, -1, 2, -2};
int ddy[9] = {0, 2, -2, 1, -1, -2, 2, -1, 1};
void link(int x, int y, int z) {
	gra[++tot].id = y, gra[tot].val = z, gra[tot].next = head[x], head[x] = tot;
	gra[++tot].id = x, gra[tot].val = 0, gra[tot].next = head[y], head[y] = tot;
}
bool vis[MAXN + 10][MAXN + 10];
bool check(int x, int y) {return ((x >= 1 && x <= n && y >= 1 && y <= n) && !vis[x][y]);}
int get(int x, int y) {return ((x - 1) * n + y);}
void connect() {
	for(int p = 1; p <= n; p++) {
		for(int i = 1; i <= n; i++) {
			if(vis[p][i]) continue;
			if((p + i) % 2 == 1) link(s, get(p, i), 1);
			else link(get(p, i), t, 1);
		}
	}
	for(int p = 1; p <= n; p++) {
		for(int i = 1; i <= n; i++) {
			if((p + i) % 2 == 0 || vis[p][i]) continue;
			for(int j = 1; j <= 8; j++) {
				int xx = p + ddx[j], yy = i + ddy[j];
				if(check(xx, yy))
					link(get(p, i), get(xx, yy), INF);
			}
		}
	}
}
bool bfs() {
	memset(dis, 0, sizeof(dis));
	queue <int> que;
	que.push(s), dis[s] = 1, Now[s] = head[s];
	while(!que.empty()) {
		int fr = que.front(); que.pop();
		for(int p = head[fr]; p; p = gra[p].next) {
			int v = gra[p].id, w = gra[p].val;
			if(w && !dis[v]) {
				que.push(v);
				Now[v] = head[v];
				dis[v] = dis[fr] + 1;
				if(v == t) return 1;
			}
		}
	}
	return 0;
}
int Dinic(int u, int over) {
	if(u == t) return over;
	int res = over;
	for(int p = Now[u]; p; p = gra[p].next) {
		int v = gra[p].id, w = gra[p].val;
		Now[u] = p;
		if(w && dis[v] == dis[u] + 1) {
			int k = Dinic(v, min(res, w));
			if(!k) dis[v] = 0x7f7f7f7f;
			gra[p].val -= k;
			gra[p ^ 1].val += k;
			res -= k;
		}
	}
	return over - res;
}
signed main() {
	scanf("%d%d", &n, &m), s = n * n + 1, t = n * n + 2; 
	for(int p = 1, x, y; p <= m; p++) {
		scanf("%d%d", &x, &y); 
		vis[x][y] = 1;
	}
	connect();
	int maxn = 0, rest = 0;
	while(bfs()) {
		for(int p = 1; p <= n; p++)
			Now[p] = head[p];
		maxn += Dinic(s, 0x7f7f7f7f);
	}
	printf("%d", n * n - m - maxn);
	//cout << maxn << endl;
}

不知道为啥 TLE 了 3 个点，明明加了当前弧优化的，求助/kk