记录编号	199623	评测结果	AAAAAAAAAA
题目名称	游历校园	最终得分	100
用户昵称	0	是否通过	通过
代码语言	C++	运行时间	0.870 s
提交时间	2015-10-27 06:21:26	内存使用	12.61 MiB

#include<cstdio>
#include<cstring>
#include<vector>

#define maxn 100010
#define maxm 500010

using namespace std;

int n,m,tot=0,b[maxn],s,t,Ans,d[maxn],siz;
bool vis[maxn];
vector<int> A;

class  at{
	public :
		int x,y,last;
}a[maxm<<1];

void add(int x,int y)
{
	tot++;
	a[tot].x=x;
	a[tot].y=y;
	a[tot].last=b[x];
	b[x]=tot;
}

void dfs(int x)
{
	vis[x]=1;A.push_back(x);siz++;
	for(int i=b[x];i;i=a[i].last){
		if(!vis[a[i].y]){
			dfs(a[i].y);
		}
	}
}

int main()
{
	freopen("sent.in","r",stdin);
	freopen("sent.out","w",stdout);
	scanf("%d%d",&n,&m);
	if(m==0){printf("-1");return 0;}
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		d[x]++;d[y]++;
		add(x,y);add(y,x);
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			siz=0;
			A.clear();
			s=0;
			dfs(i);
			if(i!=1&&siz!=1) Ans++;
			for(int j=0;j<A.size();j++){
				if(d[A[j]]&1){
					s++;
				}
			}
			if(s>2) Ans+=(s/2)-1;
		}
	}
	printf("%d",Ans);
	/*for(int i=1;i<=n;i++){
		memset(used,0,sizeof(used));
		t=s=0;
		dfs(i);
		if(t<Ans){
			Ans=t; 
		}
	}
	printf("%d",Ans);*/
	return 0;
}