Submission #1476152

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define boost ios_base::sync_with_stdio(false)
#define pb push_back
#define e1 first
#define e2 second
#define x first
#define y second
#define tysiac 1010
#define milion 1000100
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define OUT(x) { cout << x; return 0; }
#define PRINT(x, y) {printf("%d %d\n", x, y); return;} 
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define scanf(...) scanf(__VA_ARGS__)?:0
typedef long long int ll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef double ld;
typedef pair <int, int> PII;
typedef pair <ll, ll> PLL;
typedef pair <ld, ld> PDD;
typedef pair <PII, PII> PP;
typedef pair <ll, int> PLI;
typedef pair <double, int> PDI;
typedef vector <int> vi;
#define N 100100
vector<int> g[N];
int deg[N],val[N],tv[N];
int id[N],cnt;
bool del[N];
int main(){
	long long ans=0;
	int n,m,x,y;
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		scanf("%d%d",&x,&y);
		g[x].push_back(y);
		g[y].push_back(x);
		deg[x]++;
		deg[y]++;
	}
	queue<int> q;
	for(int i=1;i<=n;i++){
		if(deg[i]==1) q.push(i);
		val[i]=1;
	}
	while(!q.empty()){
		int u=q.front();
		q.pop();
		if(deg[u]!=1){
			continue;
		}
		del[u]=true;
		ans+=abs(val[u]);
		for(int i=0;i<g[u].size();i++){
			int v=g[u][i];
			if(del[v]) continue;
			val[v]-=val[u];
			if(--deg[v]==1) q.push(v);
		}
	}
	for(int i=1;i<=n;i++){
		if(!del[i]){
			while(1){
				del[i]=true;
				id[cnt++]=i;
				int nxt=-1;
				for(int j=0;j<g[i].size();j++){
					if(del[g[i][j]]) continue;
					nxt=g[i][j];
					break;
				}
				if(nxt<0) break;
				i=nxt;
			}
			break;
		}
	}
	if(cnt==1){
		if(val[id[0]]) puts("-1");
		else printf("%lld\n",ans);
	}
	else if(cnt&1){
		long long tmp=0;
		for(int i=0;i<cnt;i++){
			tmp+=val[id[i]];
		}
		if(tmp&1) puts("-1");
		else{
			tmp>>=1;
			for(int i=1;i<cnt;i+=2){
				tmp-=val[id[i]];
			}
			for(int i=0;i<cnt;i++){
				ans+=abs(tmp);
				tmp=val[id[i]]-tmp;
			}
			printf("%lld\n",ans);
		}
	}
	else{
		long long tmp=0;
		for(int i=0;i<cnt;i++){
			if(i&1) tv[i]=-tmp;
			else tv[i]=tmp;
			tmp=val[id[i]]-tmp;
		}
		if(tmp) puts("-1");
		else{
			sort(tv,tv+cnt);
			for(int i=0;i<cnt-1-i;i++){
				ans+=tv[cnt-1-i]-tv[i];
			}
			printf("%lld\n",ans);
		}
	}
	return 0;
}

Submission Info

Judge Result