提出 #33189079

---

ソースコード 拡げる

#include<cstdio>
#include<cctype>
#include<algorithm>

#define maxn 101101

template<class T>

inline T read(){
	T r=0,f=0;
	char c;
	while(!isdigit(c=getchar()))f|=(c=='-');
	while(isdigit(c))r=(r<<1)+(r<<3)+(c^48),c=getchar();
	return f?-r:r;
}

struct E{
	int v,nxt;
	E() {}
	E(int v,int nxt):v(v),nxt(nxt) {}
}e[maxn<<1];

int n,m,rt=1,ed,s_e,head[maxn],f[maxn];

int fa[maxn],sum[maxn];

int find(int x){
	return f[x]^x?f[x]=find(f[x]):x;
}

inline void a_e(int u,int v){
	e[++s_e]=E(v,head[u]);
	head[u]=s_e;
}

void dfs(int u,int val){
	sum[u]=val;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(v==fa[u])continue;
		fa[v]=u,dfs(v,-val),sum[u]+=sum[v];
	}
}

#define GG return puts("-1"),0

int main(){
	n=read<int>();
	m=read<int>();
	if(n&1)GG;
	for(int i=1;i<=n;i++)f[i]=i;
	for(int i=1;i<=m;i++){
		int u=read<int>();
		int v=read<int>();
		int x=find(u),y=find(v);
		if(x==y){
			rt=u,ed=v;
			continue;
		}
		f[y]=x,a_e(u,v),a_e(v,u);
	}
	dfs(rt,1);
	if(n==m){
		static int len,a[maxn];
		for(int u=ed;u;u=fa[u])a[++len]=sum[u];
		if(len&1){
			if(sum[rt]&1)GG;
			for(int u=ed;u;u=fa[u])
				sum[u]-=sum[rt]>>1;
		}
		else {
			if(sum[rt])GG;
			std::sort(a+1,a+1+len);
			for(int u=ed;u;u=fa[u])
				sum[u]-=a[len>>1];
		}
	}
	else if(sum[rt])GG;
	long long ans=0;
	for(int i=1;i<=n;i++)
		ans+=abs(sum[i]);
	printf("%lld\n",ans);
	return 0;
}

提出情報

ジャッジ結果