记录编号	460382	评测结果	AAAAAAAAAA
题目名称	游历校园	最终得分	100
用户昵称	하루Kiev	是否通过	通过
代码语言	C++	运行时间	0.797 s
提交时间	2017-10-16 21:36:35	内存使用	35.60 MiB

# include "iostream"
# include "algorithm"
# include "string.h"
# include "math.h"
# include "stdio.h"
# define maxn 200005
# define int long long
using namespace std;
bool vis[maxn],flag;
int n,m,ai,bi,ru[maxn],zz,st[maxn],ans,cnt,curs;
int size[maxn];
struct node{int to,next;}e[maxn*10];
void add(int x,int y){
	 e[++zz].to=y;
	 e[zz].next=st[x];
	 st[x]=zz;
}
void dfs(int x){
	 size[curs]++;vis[x]=1;
	 if(ru[x]&1) cnt++;
	 for(int i=st[x];i;i=e[i].next){
	 	 int t=e[i].to;
	 	 if(!vis[t]) dfs(t);
	 }
}
signed main(){
	freopen("sent.in","r",stdin);
	freopen("sent.out","w",stdout);
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=m;i++){
    	scanf("%lld%lld",&ai,&bi);
    	ru[ai]++;ru[bi]++;
    	add(ai,bi);add(bi,ai);
    }
    for(int i=1;i<=n;i++){
    	if(!vis[i]){
    		++curs;
    		cnt=0;
    		dfs(i);
    		if(cnt>2){
    			int plus=cnt/2-1;
    			ans+=plus;
    			if(flag) ans++;
    		}else if(size[curs]>1) ans++;
    		flag=1;
    	}
    }
    if(ans) printf("%lld",ans);
    else puts("-1");
}