记录编号	156370	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 骑士共存	最终得分	100
用户昵称	ztx	是否通过	通过
代码语言	C++	运行时间	0.457 s
提交时间	2015-04-04 14:46:37	内存使用	15.56 MiB

/****************************************\
* Author : ztx
* Title  : [cogs] 746. [网络流24题] 骑士共存
* ALG    : 二分图最大独立集 --> 点数-最大匹配 --> 点数-最大流
* CMT    :
* Time   :
\****************************************/

#include <cstdio>
#define Rep(i,l,r) for(i=(l);i<=(r);i++)
#define Rev(i,r,l) for(i=(r);i>=(l);i--)
int CH , NEG ;
typedef long long ll ;
template <typename TP>
inline void read(TP& ret) {
    ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
    if (CH == '-') NEG = true , CH = getchar() ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
    if (NEG) ret = -ret ;
}
template <typename TP>
inline void reads(TP& ret) {
	while (ret=getchar() , ret<'!') ;
	while (CH=getchar() , CH>'!') ;
}

#define  maxn  210LL
#define  maxN  40010LL
#define  maxM  640010LL
#define  infi  0x7f7f7f7fLL

struct FST { int to , next , flow ; } e[maxM<<1] ;
int star[maxN] = {0} , tote = 1 ;
inline void AddEdge(int u , int v , int cap) {
if (u<=0 || v<=0) return ;
	e[++tote].to = v ; e[tote].flow = cap ; e[tote].next = star[u] ; star[u] = tote ;
	e[++tote].to = u ; e[tote].flow = 0 ; e[tote].next = star[v] ; star[v] = tote ;
}

#define min(x,y)  ((x)<(y)?(x):(y))
int N , S , T ;
int h[maxN] = {0} , vh[maxN] = {0} ;

int dfs(int u , int flowu) {
int p , tmp = h[u]+1 ;
int flow = 0 , flowv ;
	if (u == T) return flowu ;
	for (p = star[u] ; p ; p = e[p].next) {
		if (e[p].flow && (h[e[p].to]+1==h[u])) {
			flowv = dfs(e[p].to , min(flowu-flow , e[p].flow)) ;
			flow += flowv ; e[p].flow -= flowv ; e[p^1].flow += flowv ;
			if (flow==flowu || h[S]==N) return flow ;
		}
	}
	for (p = star[u] ; p ; p = e[p].next)
		if (e[p].flow) tmp = min(tmp , h[e[p].to]) ;
	if (--vh[h[u]] == 0) h[S] = N ;
	else ++ vh[h[u]=tmp+1] ;
	return flow ;
}

int SAP() {
	int ret = 0 ;
	vh[S] = N ;
	while (h[S] < N) ret += dfs(S , infi) ;
	return ret ;
}

inline int Abs(int x) { return x < 0 ? -x : x ; }

int id[maxn][maxn] = {0} ;

const int dx[8] = {1,1,-1,-1,2,2,-2,-2} ;
const int dy[8] = {2,-2,2,-2,-1,1,-1,1} ;

int main() {
int ans , n , m , i , j , x , y , k ;
	#define READ
	#ifdef  READ
		freopen("knight.in" ,"r",stdin ) ;
		freopen("knight.out","w",stdout) ;
	#endif
	read(n) , read(m) ;
	Rep (i,1,m) {
		read(x) , read(y) ;
		id[x][y] = -1 ;
	}
	ans = 0 ;
	S = n*n+1 , T = N = S+1 ;
	Rep (i,1,n) Rep (j,1,n) {
		if (id[i][j]) continue ;
		id[i][j] = ++ans ;
		if ((i+j)&1) AddEdge(id[i][j],T,1) ;
		else AddEdge(S,id[i][j],1) ;
	}
	Rep (i,1,n) Rep (j,1,n) {
		if (id[i][j]<0) continue ;
		if ((i+j)&1) continue ;
		Rep (k,0,7) {
			x = i+dx[k] , y = j+dy[k] ;
			if (x<1 || y<1 || x>n || y>n) continue ;
			AddEdge(id[i][j],id[x][y],1) ;
		}
	}
	ans -= SAP() ;
	printf("%d\n", ans) ;
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}