记录编号	158692	评测结果	AAAAAAAAAA
题目名称	血帆海盗	最终得分	100
用户昵称	ztx	是否通过	通过
代码语言	C++	运行时间	1.035 s
提交时间	2015-04-16 20:44:07	内存使用	9.92 MiB

/*
by ztx
2015-04-16
*/
#include <cstdio>

int CH;
inline int read(int& ret) {
	ret=0;while (CH=getchar(),CH<'!');
	while (ret=ret*10+CH-'0',CH=getchar(),CH>'!');
}

#define  maxN  100010LL
#define  maxM  300010LL
struct FST { int to,next,flow; } e[maxM<<1] ;
int star[maxN] = {0} , tote = 1 ;
void AddEdge(int u,int v,int w) {
	e[++tote].to=v;e[tote].flow=w;e[tote].next=star[u];star[u]=tote;
	e[++tote].to=u;e[tote].flow=0;e[tote].next=star[v];star[v]=tote;
}
int S , T , N ;
int h[maxN] = {0} , vh[maxN] = {0} ;
#define  infi  0x7f7f7f7fLL
#define  min(x,y) ((x)<(y)?(x):(y))
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[u]==h[e[p].to]+1) {
			flowv = dfs(e[p].to,min(e[p].flow,flowu-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 && h[e[p].to]<tmp) tmp=h[e[p].to] ;
	if (--vh[h[u]] == 0) h[S] = N ;
	else ++vh[h[u]=tmp+1] ;
	return flow ;
}
inline int SAP() {
	int ret=0 ; vh[0]=N ;
	while (h[S] < N) ret += dfs(S,infi) ;
	return ret ;
}

int top,idx,cntblc;
int DFN[maxN] = {0} , LOW[maxN] , belong[maxN] , sta[maxN] ;
bool insta[maxN] = {0} ;

int dfs(int u) {
	int v,p;DFN[u]=LOW[u]=++idx;
	sta[++top]=u;insta[u]=true;
	for (p=star[u];p;p=e[p].next) {
		if (!e[p].flow) continue ;
	    if (v=e[p].to,!DFN[v]) {
			dfs(v) ; if (LOW[u]>LOW[v]) LOW[u]=LOW[v] ;
		} else if (insta[v] && LOW[u]>LOW[v]) LOW[u]=LOW[v] ;
	}
	if (DFN[u] == LOW[u]) for (cntblc++,v=-1;u!=v;) {
		insta[v=sta[top--]] = false ;
		belong[v] = cntblc ;
	}
}
void Tarjan() {
	idx=top=cntblc=0;
	for (int i=1;i<=N;i++) if (!DFN[i]) dfs(i) ;
}

int main() {
freopen("bloodsail.in","r",stdin);
freopen("bloodsail.out","w",stdout);
int n , m , u , v , i , p , ans=0 ;
	read(n),read(m);
	S = n+1 , T = N = S+1 ;
	for (i=1;i<=m;i++) {
		read(u) , read(v) ;
		AddEdge(u,v,1) ;
	}
	for (i=1;i<=n/2;i++) AddEdge(S,i,1) ;
	for (i=n/2,i++;i<=n;i++)AddEdge(i,T,1) ;
	ans=SAP();
	Tarjan() ;
//for (u=1;u<=N;u++) printf("belong[%d] = %d\n",u,belong[u]);
	for (u=1;u<=n/2;u++) {
		for (p=star[u];p;p=e[p].next) {
			if (e[p].to==S || e[p].flow) continue ;
			if (belong[u]==belong[e[p].to]) {
				ans -- ;
			}
		}
	}
	printf("%d\n", ans) ;
	getchar(),getchar();
	return 0 ;
}