dinic 90pts 求卡常

#include<bits/stdc++.h>
#define int long long
#define N 80005
#define M 320005
#define _ make_pair
using namespace std;
struct ljb{
    int en,v[2*M],w[2*M],fst[N],nxt[2*M];
    inline void add(int x,int y,int z)
    {
    //  cout<<x<<"--("<<z<<")-->"<<y<<endl;
        en++;
        v[en]=y;
        w[en]=z;
        nxt[en]=fst[x];
        fst[x]=en;
    }
}; 
ljb g;
int n,m,s=1,t,ans,dis[N],dqh[N];
bool ban[405][405];
queue<pair<int,int> > qu;
inline int hsh(int x,int y){return x*n-n+y+1;}
inline void in(int x,int y,int z)
{g.add(x,y,z);g.add(y,x,0);}
inline void in2(int x,int y,int dx,int dy)
{
    if(x+dx<=0||x+dx>n||y+dy<=0||y+dy>n||ban[x+dx][y+dy]) return;
    in(hsh(x,y),hsh(x+dx,y+dy),1);
}
inline int cp(int x){return x&1?x+1:x-1;}
inline bool bfs()
{
    memset(dis,63,sizeof(dis));
    for(int i=1;i<=t;i++) dqh[i]=g.fst[i];
    while(!qu.empty()) qu.pop();
    qu.push(_(s,0));
    while(!qu.empty())
    {
        int now=qu.front().first,d=qu.front().second;
        qu.pop();
        if(dis[now]<1e18) continue;
        dis[now]=d;
        for(int i=g.fst[now];i;i=g.nxt[i])
        {
            int s=g.v[i],w=g.w[i];
        //  cout<<now<<"--"<<w<<"->"<<s<<endl;
            if(w>0) qu.push(_(s,d+1));
        }
    }
    return dis[t]<1e18;
}
inline int dfs(int x,int y)
{
    if(x==t) return y;
    int sy=y;
    for(int i=dqh[x];i;i=g.nxt[i])
    {
        int s=g.v[i],t=g.w[i];
        if(dis[s]<=dis[x]||t==0) continue;
        dqh[x]=i;
        int f=dfs(s,min(sy,t));
        g.w[i]-=f;
        g.w[cp(i)]+=f;
        sy-=f;
        if(sy<=0) break;
    }
    return y-sy;
}
signed main()
{
    cin>>n>>m;t=n*n+2;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%lld%lld",&x,&y);
        ban[x][y]=1;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(ban[i][j]==0)
            {
                if(((i+j)&1)==0)
                {
                    in(1,hsh(i,j),1);
                    in2(i,j,1,2);
                    in2(i,j,-1,2);
                    in2(i,j,1,-2);
                    in2(i,j,-1,-2);
                    in2(i,j,2,1);
                    in2(i,j,-2,1);
                    in2(i,j,2,-1);
                    in2(i,j,-2,-1);
                }
                else in(hsh(i,j),t,1);
            }
    while(bfs()) ans+=dfs(s,1e18);
    cout<<n*n-m-ans;
    return 0;
}