#include<iostream>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<queue>
#define E puts("E?")
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
using namespace std;
int read(){
    int w=0,s=1;
    char c=getchar();
    while(!isdigit(c)){
        s=(c=='-')?-1:1;
        c=getchar();
        }
    while(isdigit(c)){
        w=(w<<3)+(w<<1)+c-'0';
        c=getchar();
        }   
    return w*s; 
    }
const int N=505,inf=((1<<30)-1)<<1;
struct Edge{
    int nxt,to,flow,ops;
    };
Edge edge[N*N<<1];
int pre[N],cnt;
void add_for(int u,int v,int w){
    edge[++cnt].nxt=pre[u];
    edge[cnt].to=v;
    edge[cnt].flow=w;
    edge[cnt].ops=(cnt&1)?cnt+1:cnt-1;
    pre[u]=cnt;
    }
void add(int u,int v,int w){
    add_for(u,v,w);
    add_for(v,u,0);
    }   
int n,m,st,ed,ans,tot=0,num=0;
int dep[N];
queue<int>que;
bool BFS(){
    while(!que.empty()){
        que.pop();
        }
    memset(dep,0,sizeof(dep));
    dep[st]=1;
    que.push(st);
    while(!que.empty()){
        int u=que.front();
        que.pop();
        for(int i=pre[u];i>0;i=edge[i].nxt){
            int v=edge[i].to,f=edge[i].flow;
            if(f&&!dep[v]){
                dep[v]=dep[u]+1;
                que.push(v);
                }
            }
        }
    return (dep[ed]==0)?0:1;    
    }
int DFS(int u,int dis){
    if(u==ed){
        return dis;
        }
    int now=dis;
    for(int i=pre[u];i>0;i=edge[i].nxt){
        int v=edge[i].to;
        if(dep[v]==dep[u]+1&&edge[i].flow&&now){
            int flow=DFS(v,min(now,edge[i].flow));
            if(flow){
                edge[i].flow-=flow;
                int j=edge[i].ops;
                edge[j].flow+=flow;
                now-=flow;
                }
            }
        }
    return dis-now; 
    }   
int Dinic(){
    int ans=0;
    while(BFS()){
        int flow;
        while(flow=DFS(st,inf)){
            ans+=flow;
            }
        }
    return ans; 
    }   
int a[N][N];    
int fx[8][2]={{2,1},{-2,1},{2,-1},{-2,-1},{1,2},{-1,2},{1,-2},{-1,-2}};
int main(){
    n=read();
    m=read();
    int u,v;
    tot=n*n-m;
    st=0;
    ed=n*n+1-m;
    for(int i=1;i<=m;i++){
        u=read();
        v=read();
        a[u][v]=-1;
        }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){  
            if(a[i][j]==-1){
                continue;
                }
            a[i][j]=++num;
            if((i+j)&1){
                add(st,num,1);
                }
            else{
                add(num,ed,1);
                }   
            }
        }   
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int u=a[i][j];
            if(u==-1){
                continue;
                }
            if((i+j)&1){
                for(int k=0;k<8;k++){
                    int x=i+fx[k][0],y=j+fx[k][1];
                    if(x<1||x>n||y<1||y>n){
                        continue;
                        }
                    int v=a[x][y];
                    if(v==-1){
                        continue;
                        }
                    add(u,v,inf);   
                    }
                }
            }
        }
    ans=Dinic();
    printf("%d",tot-ans);
    return 0;
    }

RT,感觉网络流没写错