program flow24;
const maxn=500000;
type edge=record
v,pre:longint;
end;
var e:array[0..maxn]of edge;
last,match:array[0..maxn]of longint;
v:array[0..maxn]of boolean;
n,m,ans,tot:longint;
g:array[0..210,0..210]of longint;
function cal(i,j:longint):longint;
begin
exit((i-1)*n+j);
end;
procedure addedge(u,v:longint);
begin
inc(tot);
e[tot].v:=v;
e[tot].pre:=last[u];
last[u]:=tot;
inc(tot);
e[tot].v:=u;
e[tot].pre:=last[v];
last[v]:=tot;
end;
function dfs(u:longint):boolean;
var tmp:longint;
begin
tmp:=last[u];
while tmp<>0 do
begin
if not v[e[tmp].v] then
begin
v[e[tmp].v]:=true;
if (match[e[tmp].v]=0)or(dfs(match[e[tmp].v])) then
begin
match[e[tmp].v]:=u;
exit(true);
end;
end;
tmp:=e[tmp].pre;
end;
exit(false);
end;
procedure init;
var i,j,k:longint;
begin
read(n,m);
fillchar(g,sizeof(g),0);
for i:=1 to m do
begin
read(j,k);
g[j][k]:=1;
end;
tot:=0;
fillchar(last,sizeof(last),0);
fillchar(match,sizeof(match),0);
for i:=1 to n do
for j:=1 to n do
if ((i+j)and 1=0)and(g[i][j]=0) then
begin
if (i-1>0)and(j-2>0)and(g[i-1][j-2]=0) then
addedge(cal(i,j),cal(i-1,j-2));
if (i-1>0)and(j+2<=n)and(g[i-1][j+2]=0) then
addedge(cal(i,j),cal(i-1,j+2));
if (i-2>0)and(j-1>0)and(g[i-2][j-1]=0) then
addedge(cal(i,j),cal(i-2,j-1));
if (i-2>0)and(j+1<=n)and(g[i-2][j+1]=0) then
addedge(cal(i,j),cal(i-2,j+1));
if (i+1<=n)and(j-2>0)and(g[i+1][j-2]=0) then
addedge(cal(i,j),cal(i+1,j-2));
if (i+1<=n)and(j+2<=n)and(g[i+1][j+2]=0) then
addedge(cal(i,j),cal(i+1,j+2));
if (i+2<=n)and(j-1>0)and(g[i+2][j-1]=0) then
addedge(cal(i,j),cal(i+2,j-1));
if (i+2<=n)and(j+1<=n)and(g[i+2][j+1]=0) then
addedge(cal(i,j),cal(i+2,j+1));
end;
ans:=0;
for i:=1 to n do
for j:=1 to n do
if ((i+j)and 1=0)and(g[i][j]=0) then
begin
fillchar(v,sizeof(v),false);
v[cal(i,j)]:=true;
if dfs(cal(i,j)) then inc(ans);
end;
write(n*n-m-ans);
end;
begin
//assign(input,'f.in');reset(input);
init;
//close(input);
end.
评论