C++ :

#include <iostream>

#include <cstdio>

#include <cstring>

#define N 105

#define M 1000005

using namespace std;

 

struct E {int next, to;} e[M];

int n, m, num, ans;

int h[N * N], mat[N * N];

int dx[5] = {0, -1, 1, 0, 0};

int dy[5] = {0, 0, 0, -1, 1};

bool vis[N * N];

bool tag[N][N];

 

void add(int u, int v)

{

    e[++num].next = h[u];

    e[num].to = v;

    h[u] = num;

}

 

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

 

bool dfs(int x)

{

    for(int i = h[x]; i != 0; i = e[i].next)

        if(!vis[e[i].to])

        {

            vis[e[i].to] = 1;

            if(!mat[e[i].to] || dfs(mat[e[i].to]))

            {

                mat[e[i].to] = x;

                return 1;

            }

        }

    return 0;

}

 

int main()

{

    cin >> n >> m;

    for(int i = 1; i <= m; i++)

    {

        int x, y;

        cin >> x >> y;

        tag[x][y] = 1;

    }

    for(int i = 1; i <= n; i++)

        for(int j = 1; j <= n; j++)

            for(int k = 1; k <= 4; k++)

            {

                int x = i, y = j;

                int xx = x + dx[k], yy = y + dy[k];

                if(xx < 1 || xx > n || yy < 1 || yy > n) continue;

                if(tag[x][y] || tag[xx][yy]) continue;

                add(cal(x, y), cal(xx, yy));

                add(cal(xx, yy), cal(x, y));

            }

    for(int i = 1; i <= n; i++)

        for(int j = 1; j <= n; j++)

            if((i + j) % 2)

            {

                memset(vis, 0, sizeof(vis));

                if(dfs(cal(i, j))) ans++;

            }

    cout << ans;

    return 0;

}