记录编号	200054	评测结果	AAAAAAAAAA
题目名称	游历校园	最终得分	100
用户昵称	Satoshi	是否通过	通过
代码语言	C++	运行时间	0.524 s
提交时间	2015-10-27 20:54:46	内存使用	1.91 MiB

#define MAXN 100010UL

#include <cstdio>

int n,m,odd[MAXN],father[MAXN],block[MAXN],Ans,size[MAXN],cnt;
bool ex[MAXN];

inline int getf(int p){
	if(father[p]!=p) father[p]=getf(father[p]);
	return father[p];
}

int main(){
	freopen("sent.in","r",stdin);
	freopen("sent.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) father[i]=i;
	for(int i=1,a,b;i<=m;i++){
		scanf("%d%d",&a,&b);
		odd[a]^=1,odd[b]^=1;
		a=getf(a),b=getf(b);
		if(a!=b) father[a]=b;
	}
	for(int i=1;i<=n;i++){
		int k=getf(i);
		if(odd[i]) block[k]++;
		size[k]++;
	}
	for(int i=1;i<=n;i++){
		if(i!=father[i]) continue;
		if(size[i]==1) continue;
		Ans++;
		if(block[i]<=2) continue;
		Ans+=(block[i]>>1)-1;
	}
	printf("%d",Ans-1);
	return 0;
}