Submission #1692934

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef double db;
typedef long long ll;
#define w1 first
#define w2 second
#define ls (x<<1)
#define rs (x<<1|1)
#define pb push_back
#define mid ((l+r)>>1)
#define SZ(x) ((x).size())
#define All(x) (x).begin(),(x).end()
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define rep2(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define per(i,a,b) for(int (i)=(a);(i)>=(b);(i)--)
#define Rep(p,x) for(int (p)=head[(x)];(p);(p)=nxt[(p)])
template<class T>void read(T&num){
	num=0;T f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();
	num*=f;
}
int power(int x,int k,int p){int res=1;for(;k;k>>=1,x=1ll*x*x%p)if(k&1)res=1ll*res*x%p;return res;}
const int maxn=1e5+5;
int n,m,tot,sumb,rt,pnt;
int head[maxn],des[maxn<<1],nxt[maxn<<1];
int cntb[maxn],sz[maxn],vis[maxn],dep[maxn],fa[maxn];
void adde(int x,int y){
	des[++tot]=y;nxt[tot]=head[x];head[x]=tot;
}
void dfs(int x){
	vis[x]=1;
	cntb[x]=dep[x]&1;
	sz[x]=1;
	Rep(p,x)if(des[p]!=fa[x]){
		if(des[p]==rt)pnt=x;
		else if(!vis[des[p]]){
			dep[des[p]]=dep[x]+1;
			fa[des[p]]=x;
			dfs(des[p]);
			cntb[x]+=cntb[des[p]];
			sz[x]+=sz[des[p]];
		}
	}
}
void dfs1(int x,int fa){
	vis[x]=1;
	Rep(p,x)if(des[p]!=fa){
		if(vis[des[p]])rt=des[p];
		else dfs1(des[p],x);
	}
}
int main(){
	read(n);read(m);
	if(n&1)return puts("-1"),0;
	rep(i,1,m){
		int x,y;read(x);read(y);
		adde(x,y);adde(y,x);
	}
	if(m==n-1){
		dep[1]=1;
		dfs(1);
		if(cntb[1]*2!=n)puts("-1");
		else{
			ll ans=0;
			rep(i,2,n)ans+=abs(sz[i]-cntb[i]-cntb[i]);
			cout<<ans<<endl;
		}
	}else{
		dfs1(1,0);
		rep(i,1,n)vis[i]=0;
		dep[rt]=1;
		dfs(rt);
		if(!(dep[pnt]&1)){
			if(cntb[rt]*2!=n)puts("-1");
			else{
				ll ans=0;
				vector<int>q;
				q.pb(0);
				rep(i,1,n)vis[i]=0;
				for(int i=pnt;i!=rt;i=fa[i])vis[i]=1,q.pb(2*cntb[i]-sz[i]);
				rep(i,1,n)if(i!=rt&&!vis[i])ans+=abs(sz[i]-2*cntb[i]);
				sort(All(q));
				int tmp=q[SZ(q)/2];
				rep2(i,0,SZ(q))ans+=abs(tmp-q[i]);
				cout<<ans<<endl;
			}
		}else{
			int k=n-2*cntb[rt];
			if(k&1)puts("-1");
			else{
				ll ans=0;
				k>>=1;
				rep(i,1,n)vis[i]=0;
				for(int i=pnt;i!=rt;i=fa[i])vis[i]=1,ans+=abs(sz[i]-2*cntb[i]-k);
				rep(i,1,n)if(i!=rt&&!vis[i])ans+=abs(sz[i]-2*cntb[i]);
				cout<<ans+abs(k)<<endl;
			}
		}
	}
	return 0;
}

Submission Info

Judge Result