考虑一个格子$(i,j)$:

• $i+j$为偶数:不妨记这样的格子为白格子.
• $i+j$为奇数:不妨记这样的格子为黑格子.

如果这个白格子没有被禁止,那么就让它向周围没有被禁止的黑格子连有向边,表示 如果选择这条边(在这两个格子上放骨牌)会对答案有1的贡献.显然白格子周围都是黑格子,所以白格子之间不会有边.那么这就是一个二分图最大匹配的模型,跑一下就好了.

最多$O(n^2)$个点,$O(n^2)$条边,所以时间复杂度$O(n^4)$

/**********/省略快读
#define MAXN 20011
struct Edge
{
    ll v,nxt;
}e[MAXN<<2|1];
ll cnt=0,last[MAXN];
void adde(ll u,ll v)
{
    ++cnt;
    e[cnt].v=v;
    e[cnt].nxt=last[u],last[u]=cnt;
}

ll p[MAXN];
bool vis[MAXN];
bool dfs(ll u)//二分图最大匹配
{
    for(ll i=last[u];i;i=e[i].nxt)
    {
        ll v=e[i].v;
        if(!vis[v])
        {
            vis[v]=1;
            if(!p[v]||dfs(p[v]))
            {
                p[v]=u;
                return 1;
            }
        }
    }
}
bool a[111][111];
const ll mx[4]={0,1,0,-1},my[4]={1,0,-1,0};
int main()
{
    ll n=read(),t=read();
    for(ll i=1;i<=t;++i)
    {
        ll x=read(),y=read();
        a[x][y]=1;
    }
    for(ll i=1;i<=n;++i)
        for(ll j=1;j<=n;++j)
        {
            if(((i+j)&1)||a[i][j])continue;//不是白色格子,或者被禁止了,就跳过
            for(ll op=0;op<4;++op)
            {
                ll x=i+mx[op],y=j+my[op];
                if(x>0&&x<=n&&y>0&&y<=n&&!a[x][y])adde((i-1)*n+j,(x-1)*n+y);//加边
            }
        }
    ll ans=0;
    for(ll i=1;i<=n;++i)
        for(ll j=1;j<=n;++j)
        {
            if((i+j)&1)continue;
            memset(vis,0,sizeof vis);
            if(dfs((i-1)*n+j))++ans;
        }
    printf("%lld",ans);
    return 0;
}