1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define ll long long
using namespace std;
namespace Ehnaev{
inline ll read() {
ll ret=0,f=1;char ch=getchar();
while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
return ret*f;
}
inline void write(ll x) {
static char buf[22];static ll len=-1;
if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
while(len>=0) putchar(buf[len--]);
}
}using Ehnaev::read;using Ehnaev::write;
const ll N=1e6,inf=(1ll<<31)-1;
ll n,m,tot,s,t;
ll ver[N+5],nxt[N+5],head[N+5],ct[N+5];
ll d[N+5],now[N+5],flg[N+5];
ll dx[]={0,0,1,-1},dy[]={1,-1,0,0};
queue<ll> q;
inline bool Bfs() {
memset(d,0,sizeof(d));while(!q.empty()) q.pop();
d[s]=1;q.push(s);now[s]=head[s];
while(!q.empty()) {
ll h=q.front();q.pop();
for(ll i=head[h];i;i=nxt[i]) {
if(!ct[i]||d[ver[i]]) continue;
d[ver[i]]=d[h]+1;q.push(ver[i]);now[ver[i]]=head[ver[i]];
if(ver[i]==t) return 1;
}
}
return 0;
}
inline ll Dinic(ll p,ll flw) {
if(p==t) return flw;ll rst=flw,k,i;
for(i=now[p];i&&rst;i=nxt[i]) {
if(!ct[i]||d[ver[i]]!=d[p]+1) continue;
k=Dinic(ver[i],min(rst,ct[i]));
if(!k) d[ver[i]]=0;
ct[i]-=k;ct[i^1]+=k;rst-=k;
if(rst==0) return flw-rst;
}
now[p]=i;return flw-rst;
}
inline ll Pos(ll x,ll y) {return (x-1)*n+y;}
inline void Addedge(ll u,ll v,ll w) {
ver[++tot]=v;nxt[tot]=head[u];ct[tot]=w;head[u]=tot;
ver[++tot]=u;nxt[tot]=head[v];ct[tot]=0;head[v]=tot;
}
inline void Func_Add(ll x,ll y) {
ll tmp1=Pos(x,y);
for(ll i=0;i<4;i++) {
ll xx=x+dx[i],yy=y+dy[i];ll tmp2=Pos(xx,yy);
if(xx<1||xx>n||yy<1||yy>n||flg[tmp2]) continue;
Addedge(tmp1,tmp2,1);
}
}
inline bool Check(ll x) {
if(n&1) return (x&1);
else {
if(((x+n-1)/n)&1) return (((x-1)%n+1)&1);
else return !(((x-1)%n+1)&1);
}
}
int main() {
n=read();m=read();s=n*n+1;t=n*n+2;
for(ll i=1;i<=m;i++) {
ll x,y;x=read();y=read();
ll tmp=Pos(x,y);flg[tmp]=1;
}
tot=1;
for(ll i=1;i<=n;i++) {
for(ll j=1;j<=n;j++) {
ll tmp=Pos(i,j);if(Check(tmp)&&!flg[tmp]) Func_Add(i,j);
}
}
for(ll i=1;i<=n*n;i++) {
if(Check(i)&&!flg[i]) Addedge(s,i,1);
else if(!flg[i]) Addedge(i,t,1);
}
ll maxflow=0,flow=0;
while(Bfs()) {while(flow=Dinic(s,inf)) maxflow+=flow;}
write(maxflow);
return 0;
}
|