记录编号	72330	评测结果	AAAAAAAAAA
题目名称	游历校园	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.556 s
提交时间	2013-10-16 19:21:11	内存使用	1.66 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
const int SIZEN=100001;
int ufs[SIZEN]={0};
int deg[SIZEN]={0};
int size[SIZEN]={0};
int blockn=0;
int n,m;
int odd_point[SIZEN]={0};
int grand(int x){
	if(ufs[x]==0) return x;
	int ans=grand(ufs[x]);
	ufs[x]=ans;
	return ans;
}
void merge(int x,int y){//将根为x,y的两棵树合并
	ufs[x]=y;
	size[y]+=size[x];
	size[x]=0;
}
int stroke(int x){
	if(x<=2) return 0;
	else return x/2-1;
}
void answer(void){
	int i;
	for(i=1;i<=n;i++) odd_point[grand(i)]+=(deg[i]&1);
	int ans=0;
	for(i=1;i<=n;i++){
		if(size[i]>1) ans+=stroke(odd_point[i]),ans++;
	}
	printf("%d\n",ans-1);
}
void work(void){
	scanf("%d%d",&n,&m);
	blockn=n;
	int i;
	for(i=1;i<=n;i++) size[i]=1;
	int a,b;
	int ag,bg;
	for(i=1;i<=m;i++){
		scanf("%d%d",&a,&b);
		deg[a]++,deg[b]++;
		ag=grand(a),bg=grand(b);
		if(ag!=bg){
			blockn--;
			merge(ag,bg);
		}
	}
}
int main(){
	freopen("sent.in","r",stdin);
	freopen("sent.out","w",stdout);
	work();
	answer();
	return 0;
}