TLE #11

#include<bits/stdc++.h>
using namespace std;
const int N=501;
int n,m;
int a[N][N],hao[N][N],hb[N][N],my[N*N],tot,sum,ans,vis[N*N],Time;
int ls,z[N*N];
int dx[8]={1,1,-1,-1,2,2,-2,-2},dy[8]={2,-2,2,-2,1,-1,1,-1};
struct bian{
	int zhong,zhi;
}s[N*N];
bool dfs(int x)
{
	for(int i=z[x];i;i=s[i].zhi)
	{
		int y=s[i].zhong;
		if(vis[y]==Time) continue;
		vis[y]=Time;
		if(!my[y]||dfs(my[y]))
		{
			my[y]=x;
			return 1; 
		}
	}
	return 0;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		if(!a[x][y]) sum++;
		a[x][y]=1;
	}
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=n;j++)
		hb[i][j]=(i+j)%2,tot++,hao[i][j]=tot;
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=n;j++)
	  {
		if(a[i][j]||!hb[i][j]) continue;
		for(int k=0;k<8;k++)
		{
			int X=i+dx[k],Y=j+dy[k];
			if(X<1||X>n||Y<1||Y>n||a[X][Y]) continue;
			s[++ls]=(bian){hao[X][Y],z[hao[i][j]]},z[hao[i][j]]=ls;
		}
	  }
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=n;j++)
	  {
		if(a[i][j]||!hb[i][j]) continue;
		Time++;
		if(dfs(hao[i][j])) ans++;
	  }
	printf("%d",n*n-sum-ans);
	return 0;
}