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

#include<cstdio>

using namespace std;

bool vis[100010],p;
int n,m,du[100010],Ans,first[100010],temp,tot,_size;

struct Edge{
	int v,next;
}edge[1000010];

void Add(int u,int v)
{
	edge[++tot].v=v;
	edge[tot].next=first[u];
	first[u]=tot;
}

void dfs(int ver)
{
	vis[ver]=true;_size++;
	if(du[ver]&1)temp++;
	for(int i=first[ver];i;i=edge[i].next)
		if(!vis[edge[i].v])dfs(edge[i].v);
}

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,u,v;i<=m;i++){
		scanf("%d%d",&u,&v);
		du[u]++;du[v]++;
		Add(u,v);Add(v,u);
	}
	for(int i=1;i<=n;i++)
		if(!vis[i]){
			temp=0;_size=0;dfs(i);
			if(_size==1)continue;
			if(!temp){Ans++;continue;}
			if(!p)Ans+=(temp>>1)-1,p=true;
			else Ans+=(temp>>1);
		}
	printf("%d",Ans);
}