#include<bits/stdc++.h>
#define N 40010
#define M 640010
using namespace std;
int d[N],tail=1,dis[N];
struct bbbb{
    int ne,to;
    long long ll;
}b[M];
void jb(int x,int y,long long z){
//  cout<<"["<<x<<" "<<y<<" "<<z<<"]\n";
    tail++;
    b[tail].ne=d[x];
    b[tail].to=y;
    b[tail].ll=z;
    d[x]=tail;
    return;
}
queue<int>q;
bool bfs(int s,int t){
    memset(dis,-1,sizeof dis);
    dis[s]=0;q.push(s);
    while(q.empty()==false){
        int x=q.front();q.pop();
        for(int i=d[x];i;i=b[i].ne){
            int y=b[i].to;
            if(b[i].ll>0&&dis[y]==-1){
                dis[y]=dis[x]+1;
                q.push(y);
            }
        }
    }
    if(dis[t]==-1)return false;
    return true;
}
long long dinic(int x,long long liu,int t){
    if(x==t)return liu;
    long long yyy=0;
    for(int i=d[x];i;i=b[i].ne){
        int y=b[i].to;
        if(b[i].ll>0&&dis[y]>dis[x]){
            long long yy=dinic(y,min(liu-yyy,b[i].ll),t);
            yyy+=yy;
            b[i].ll-=yy;
            b[i^1].ll+=yy;
        }
    }
    return yyy;
}
long long work(int s,int t){
    long long llll=0;
    while(bfs(s,t)){
        llll+=dinic(s,1e18,t);
    }
    return llll;
}
///////////////////////////////////////////////////////////////////////////////
int n,m,x_[8]={1,-1,1,-1,2,-2,2,-2},y_[8]={2,-2,-2,2,1,-1,-1,1},ma[210][210];
int hh(int x,int y){
    return n*(x-1)+y;
}
long long qwq;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        ma[x][y]=1;
    }
    qwq=n*n-m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(ma[i][j]==1)continue;
            if((i-j)%2==0){
//              cout<<"*";
                jb(n*n+1,hh(i,j),1);
                jb(hh(i,j),n*n+1,0);
                for(int k=0;k<8;k++){
                    int xx=i+x_[k],yy=j+y_[k];
                    if(xx>0&&xx<=n&&yy>0&&yy<=n&&ma[xx][yy]==0){
//                      cout<<"!";
                        jb(hh(i,j),hh(xx,yy),1e18);
                        jb(hh(xx,yy),hh(i,j),0);
                    }
                }
            }
            else{
//              cout<<"?";
                jb(hh(i,j),n*n+2,1);
                jb(n*n+2,hh(i,j),0);                                
            }
        }
    }
    printf("%lld",qwq-work(n*n+1,n*n+2));
    return 0;
}

3#11 TLE

QAQ求助