记录编号	34989	评测结果	AAAAAAAAAA
题目名称	游历校园	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	1.397 s
提交时间	2012-02-13 19:34:51	内存使用	1.79 MiB

#include <cstdio>
#include <cstdlib>
#define readfile(str) freopen(str,"r",stdin)
#define writefile(str) freopen(str,"w",stdout)
using namespace std;

const int MAXN=100001;
int N,M;
int UFS[MAXN];
int Deg[MAXN];
int Num[MAXN];
int SingularPoint[MAXN];

int GetPnt(int n)
{
	if(UFS[n]!=n)
		UFS[n]=GetPnt(UFS[n]);
	return UFS[n];
}

void init()
{
	scanf("%d\n%d\n",&N,&M);
	
	for(int i=1;i<=N;i++)
		UFS[i]=i;
	
	int a,b,ta,tb;
	for(int i=1;i<=M;i++)
	{
		scanf("%d %d\n",&a,&b);
		if(a==b)
			continue;
		ta=GetPnt(a);
		tb=GetPnt(b);
		if(ta!=tb)
			UFS[ta]=b;
		Deg[a]++,Deg[b]++;
	}
}

void solve()
{
	for(int i=1;i<=N;i++)
	{
		int tmp=GetPnt(i);
		Num[tmp]++;
		if(Deg[i]&1)
			SingularPoint[tmp]++;
	}
	
	int Top=0,Ans=0;
	for(int i=1;i<=N;i++)
	{
		if(Num[i]<2)
			continue;
		Top++;
		if(SingularPoint[i]<=2)
			continue;
		Ans+=(SingularPoint[i]-2)>>1;
	}
	Ans+=Top-1;
	printf("%d\n",Ans);
}

int main()
{
	readfile("sent.in"),writefile("sent.out");
	init();
	solve();
	return 0;
}