stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<cstdio>

#include<cstring>

#include<vector>

#include<algorithm>

using namespace std;

const long long MAXN=100005;



long long N,M;

vector<long long> adj[MAXN];

long long dep[MAXN],sum[MAXN],k[MAXN];

bool vis[MAXN];

long long cU,cV,clen;

vector<long long> num;



void dfs(long long u,long long fa=0)

{

	vis[u]=true;

	for(auto v:adj[u])

	{

		if(v==fa)

			continue;

		if(vis[v])

		{

			cU=u;

			cV=v;

			clen=dep[u]-dep[v]+1;

			continue;

		}

		dep[v]=dep[u]+1;

		dfs(v,u);

	}

}

void Calc(long long u,long long fa=0)

{

	vis[u]=true;

	for(auto v:adj[u])

	{

		if(v==fa||vis[v])

			continue;

		Calc(v,u);

		sum[u]+=sum[v];

		k[u]+=k[v];

	}

}



int main()

{

	scanf("%lld%lld",&N,&M);

	for(long long i=1;i<=M;i++)

	{

		long long a,b;

		scanf("%lld%lld",&a,&b);

		adj[a].push_back(b);

		adj[b].push_back(a);

	}

	dep[1]=0;

	dfs(1);

	long long val=0;

	long long ans=0;

	for(long long i=1;i<=N;i++)

	{

		sum[i]=(dep[i]&1)?1:-1;

		val+=sum[i];

	}

	if(M==N-1)

	{

		if(val!=0)

		{

			puts("-1");

			return 0;

		}

	}

	else

	{

		if(clen&1)

		{

			if(val&1)

			{

				puts("-1");

				return 0;

			}

			else

			{

				ans+=(abs(val)/2);

				sum[cU]-=val/2;

				sum[cV]-=val/2;

			}

		}

		else

		{

			if(val!=0)

			{

				puts("-1");

				return 0;

			}

			else

			{

				k[cU]=1;

				k[cV]=-1;

			}

		}

	}

	memset(vis,0,sizeof vis);

	Calc(1);

	for(long long i=1;i<=N;i++)

	{

		if(k[i]==0)

			ans+=abs(sum[i]);

		else

		{

			if(k[i]==1)

				sum[i]=-sum[i];

			num.push_back(sum[i]);

		}

	}

	num.push_back(0);

	sort(num.begin(),num.end());

	long long x=num[(num.size()-1)/2];

	for(auto s:num)

		ans+=1LL*abs(s-x);

	printf("%lld\n",ans);

	

	fclose(stdin);

	fclose(stdout);

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.9299136977543347x):
#include<bits/stdc++.h>

using namespace std;

struct edge{int to,nxt;}e[200005];

int n,m,et,rx,rt,head[100005],fa[100005],a[100005],tot,b[100005],r;

inline void adde(int x,int y) {e[++tot]=(edge){y,head[x]},head[x]=tot;}

inline int getf(int x) {return fa[x]==x?x:fa[x]=getf(fa[x]);}

inline void dfs(int x,int fl,int f=0)

{

	a[x]=fl,fa[x]=f;

	for(int i=head[x];i;i=e[i].nxt) if(e[i].to!=f) dfs(e[i].to,-fl,x),a[x]+=a[e[i].to];

}

int main()

{

	scanf("%d%d",&n,&m),et=0,rt=1,memset(head,0,sizeof(head));

	for(int i=1;i<=n;i++) fa[i]=i;

	for(int i=1,x,y;i<=m;i++) {scanf("%d%d",&x,&y);if(getf(x)!=getf(y)) adde(x,y),adde(y,x),fa[getf(x)]=getf(y);else rt=x,rx=y;}

	memset(a,0,sizeof(a)),fa[rt]=0,dfs(rt,1),tot=0,r=0;

	if(n!=m) {if(a[rt]) return puts("-1"),0;}

	else

	{

		for(int x=rx;x;x=fa[x]) b[++tot]=a[x];

		if(tot&1)

		{

			if(a[rt]&1) return puts("-1"),0;

			for(int x=rx;x;x=fa[x]) a[x]-=(a[rt]>>1);

		}

		else

		{

			if(a[rt]) return puts("-1"),0;

			sort(b+1,b+tot+1);

			for(int x=rx;x;x=fa[x]) a[x]-=b[tot>>1];

		}

	}

	for(int i=1;i<=n;i++) r+=abs(a[i]);

	return printf("%d\n",r),0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

vector<int> G[N];

int delv, delu;

int n, m, x, y, d[N], fa[N], dp[N], q[N];

void dfs(int x, int fx) {

    d[x] = d[fx] + 1;

    fa[x] = fx;

    dp[x] = d[x] % 2 ? 1 : -1;

    for (int y : G[x]) {

        if (y == fx) continue;

        if (d[y]) {

            delv = y;

            delu = x;

            continue;

        }

        dfs(y, x);

        dp[x] += dp[y];

    }

}

void SolveTree() {

    if (dp[1]) {

        puts("-1");

        return;

    }

    int ans = 0;

    for (int i = 1; i <= n; i++) ans += abs(dp[i]);

    printf("%d\n", ans);

}

void SolveOdd() {

    if (dp[1] % 2) {

        puts("-1");

        return;

    }

    int ans = 0, t = -dp[1] / 2;

    ans = abs(t);

    for (; delu; delu = fa[delu]) dp[delu] += t;

    for (; delv; delv = fa[delv]) dp[delv] += t;

    for (int i = 1; i <= n; i++) ans += abs(dp[i]);

    printf("%d\n", ans);

}

void SolveEven() {

    if (dp[1]) {

        puts("-1");

        return;

    }

    int ans, top = 0, mid;

    for (; delv != delu; delv = fa[delv]) {

        q[++top] = dp[delv];

        d[delv] = 0;

    }

    sort(q + 1, q + top + 1);

    mid = q[(top + 1) / 2];

    ans = abs(mid);

    for (int i = 1; i <= n; i++)

        if (d[i]) ans += abs(dp[i]);

    for (int i = 1; i <= top; i++) ans += abs(q[i] - mid);

    printf("%d\n", ans);

}

int main() {

    scanf("%d%d", &n, &m);

    for (int i = 1; i <= m; i++) {

        scanf("%d%d", &x, &y);

        G[x].push_back(y);

        G[y].push_back(x);

    }

    dfs(1, 0);

    if (m == n - 1)

        SolveTree();

    else if ((d[delv] - d[delu]) % 2)

        SolveEven();

    else

        SolveOdd(); 

}

// Faster C++ solution for the same problem (measured speedup: 1.9688520197964487x):
#include<bits/stdc++.h>

using namespace std;

struct edge{int to,nxt;}e[200005];

int n,m,et,rx,rt,head[100005],fa[100005],a[100005],tot,b[100005],r;

inline void adde(int x,int y) {e[++tot]=(edge){y,head[x]},head[x]=tot;}

inline int getf(int x) {return fa[x]==x?x:fa[x]=getf(fa[x]);}

inline void dfs(int x,int fl,int f=0)

{

	a[x]=fl,fa[x]=f;

	for(int i=head[x];i;i=e[i].nxt) if(e[i].to!=f) dfs(e[i].to,-fl,x),a[x]+=a[e[i].to];

}

int main()

{

	scanf("%d%d",&n,&m),et=0,rt=1,memset(head,0,sizeof(head));

	for(int i=1;i<=n;i++) fa[i]=i;

	for(int i=1,x,y;i<=m;i++) {scanf("%d%d",&x,&y);if(getf(x)!=getf(y)) adde(x,y),adde(y,x),fa[getf(x)]=getf(y);else rt=x,rx=y;}

	memset(a,0,sizeof(a)),fa[rt]=0,dfs(rt,1),tot=0,r=0;

	if(n!=m) {if(a[rt]) return puts("-1"),0;}

	else

	{

		for(int x=rx;x;x=fa[x]) b[++tot]=a[x];

		if(tot&1)

		{

			if(a[rt]&1) return puts("-1"),0;

			for(int x=rx;x;x=fa[x]) a[x]-=(a[rt]>>1);

		}

		else

		{

			if(a[rt]) return puts("-1"),0;

			sort(b+1,b+tot+1);

			for(int x=rx;x;x=fa[x]) a[x]-=b[tot>>1];

		}

	}

	for(int i=1;i<=n;i++) r+=abs(a[i]);

	return printf("%d\n",r),0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define REP(i,a,b) for(int i=(a),_ed=(b);i<=_ed;++i)

#define DREP(i,a,b) for(int i=(a),_ed=(b);i>=_ed;--i)

#define pb(x) push_back((x))

typedef long long ll;

inline int read(){

    register int x=0,f=1;register char ch=getchar();

    while(!isdigit(ch)){if(ch=='-')f=0;ch=getchar();}

    while(isdigit(ch)){x=x*10+(ch^'0');ch=getchar();}

    return f?x:-x;

}



const int N=1e5+5;

int n,m,dep[N],s,t,flg,S[N],k[N],stk[N],tp;

ll ans;

vector<int> E[N];



inline void Dfs(int u,int pa){

    for(int v:E[u]){

	if(v==pa)continue;

	if(dep[v]){flg=(dep[u]==dep[v]);s=u,t=v;continue;}

	dep[v]=dep[u]*-1;Dfs(v,u);

    }

}

inline void Cal(int u,int pa){

    for(int v:E[u]){

	if(v==pa||(u==s&&v==t)||(v==s&&u==t))continue;

	Cal(v,u);

	S[u]+=S[v];k[u]+=k[v];

    }

}



int main(){

    //freopen("in.in","r",stdin);

    n=read(),m=read();

    REP(i,1,m){int u=read(),v=read();E[u].pb(v),E[v].pb(u);}

    dep[1]=1;Dfs(1,0);

    int sum=0;

    REP(i,1,n)sum+=(S[i]=dep[i]);

    if(m==n-1){if(sum)return puts("-1"),0;}

    else if((flg&&(sum&1))||(!flg&&sum))return puts("-1"),0;

    if(m==n){

	if(flg){

	    S[s]-=sum/2,S[t]-=sum/2;

	    ans+=abs(sum/2);

	}

	else k[s]=1,k[t]=-1;

    }

    Cal(1,0);

    REP(i,1,n)

	if(!k[i])ans+=abs(S[i]);

	else if(~k[i])stk[++tp]=-S[i];

	else stk[++tp]=S[i];

    stk[++tp]=0;

    sort(stk+1,stk+tp+1);

    int x=stk[(tp+1)>>1];

    REP(i,1,tp)ans+=abs(stk[i]-x);

    printf("%lld\n",ans);

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.9672051993460207x):
#include<bits/stdc++.h>

using namespace std;

struct edge{int to,nxt;}e[200005];

int n,m,et,rx,rt,head[100005],fa[100005],a[100005],tot,b[100005],r;

inline void adde(int x,int y) {e[++tot]=(edge){y,head[x]},head[x]=tot;}

inline int getf(int x) {return fa[x]==x?x:fa[x]=getf(fa[x]);}

inline void dfs(int x,int fl,int f=0)

{

	a[x]=fl,fa[x]=f;

	for(int i=head[x];i;i=e[i].nxt) if(e[i].to!=f) dfs(e[i].to,-fl,x),a[x]+=a[e[i].to];

}

int main()

{

	scanf("%d%d",&n,&m),et=0,rt=1,memset(head,0,sizeof(head));

	for(int i=1;i<=n;i++) fa[i]=i;

	for(int i=1,x,y;i<=m;i++) {scanf("%d%d",&x,&y);if(getf(x)!=getf(y)) adde(x,y),adde(y,x),fa[getf(x)]=getf(y);else rt=x,rx=y;}

	memset(a,0,sizeof(a)),fa[rt]=0,dfs(rt,1),tot=0,r=0;

	if(n!=m) {if(a[rt]) return puts("-1"),0;}

	else

	{

		for(int x=rx;x;x=fa[x]) b[++tot]=a[x];

		if(tot&1)

		{

			if(a[rt]&1) return puts("-1"),0;

			for(int x=rx;x;x=fa[x]) a[x]-=(a[rt]>>1);

		}

		else

		{

			if(a[rt]) return puts("-1"),0;

			sort(b+1,b+tot+1);

			for(int x=rx;x;x=fa[x]) a[x]-=b[tot>>1];

		}

	}

	for(int i=1;i<=n;i++) r+=abs(a[i]);

	return printf("%d\n",r),0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define int long long

using namespace std;



int n,m,head[100005],nxt[200005],pnt[200005],E = 0,sz[100005],s,t,ans = 0,k[100005];

bool odd = 0;

std::vector<int> v;



void add_edge(int u,int v)

{

	pnt[E] = v;

	nxt[E] = head[u];

	head[u] = E++;

}



void dfs1(int u,int fa)

{

	for (int i = head[u]; i != -1; i = nxt[i])

	{

		int v = pnt[i];

		if (v == fa) continue;

		if (sz[v])

		{

			if (sz[v] == sz[u]) odd = 1;

			s = u;

			t = v;

		}

		else

		{

			sz[v] = -sz[u];

			dfs1(v,u);

		}

	}

}



void dfs2(int u,int fa)

{

	for (int i = head[u]; i != -1; i = nxt[i])

	{

		int v = pnt[i];

		if (v == fa) continue;

		if (v == s && u == t) continue;

		if (v == t && u == s) continue;

		dfs2(v,u);

		sz[u] += sz[v];

		k[u] += k[v];

	}

}



signed main()

{

	memset(head,-1,sizeof(head));

	memset(sz,0,sizeof(sz));

	scanf("%lld%lld",&n,&m);

	for (int i = 1; i <= m; i++)

	{

		int u,v;

		scanf("%lld%lld",&u,&v);

		add_edge(u,v);

		add_edge(v,u);

	}

	sz[1] = 1;

	dfs1(1,0);

	int sum = 0;

	for (int i = 1; i <= n; i++)

	{

		sum += sz[i];

	}

	if (m == n - 1)

	{

		if (sum)

		{

			puts("-1");

			return 0;

		}

	}

	else

	{

		if (odd)

		{

			if (sum & 1)

			{

				puts("-1");

				return 0;

			}

			ans += abs(sum >> 1);

			sz[s] -= sum >> 1;

			sz[t] -= sum >> 1;

		}

		else

		{

			if (sum)

			{

				puts("-1");

				return 0;

			}

			k[s] = 1;

			k[t] = -1;

		}

	}

	dfs2(1,0);

	for (int i = 1; i <= n; i++)

	{

		if (k[i]) v.push_back(k[i] * sz[i]);

		else ans += abs(sz[i]);

	}

	v.push_back(0);

	sort(v.begin(),v.end());

	int len = v.size();

	int mid = v[(len + 1) >> 1];

	for (int i = 0; i < len; i++)

	{

		ans += abs(v[i] - mid);	

	}

	printf("%lld\n",ans);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.4530051460740867x):
#include<bits/stdc++.h>

using namespace std;

struct edge{int to,nxt;}e[200005];

int n,m,et,rx,rt,head[100005],fa[100005],a[100005],tot,b[100005],r;

inline void adde(int x,int y) {e[++tot]=(edge){y,head[x]},head[x]=tot;}

inline int getf(int x) {return fa[x]==x?x:fa[x]=getf(fa[x]);}

inline void dfs(int x,int fl,int f=0)

{

	a[x]=fl,fa[x]=f;

	for(int i=head[x];i;i=e[i].nxt) if(e[i].to!=f) dfs(e[i].to,-fl,x),a[x]+=a[e[i].to];

}

int main()

{

	scanf("%d%d",&n,&m),et=0,rt=1,memset(head,0,sizeof(head));

	for(int i=1;i<=n;i++) fa[i]=i;

	for(int i=1,x,y;i<=m;i++) {scanf("%d%d",&x,&y);if(getf(x)!=getf(y)) adde(x,y),adde(y,x),fa[getf(x)]=getf(y);else rt=x,rx=y;}

	memset(a,0,sizeof(a)),fa[rt]=0,dfs(rt,1),tot=0,r=0;

	if(n!=m) {if(a[rt]) return puts("-1"),0;}

	else

	{

		for(int x=rx;x;x=fa[x]) b[++tot]=a[x];

		if(tot&1)

		{

			if(a[rt]&1) return puts("-1"),0;

			for(int x=rx;x;x=fa[x]) a[x]-=(a[rt]>>1);

		}

		else

		{

			if(a[rt]) return puts("-1"),0;

			sort(b+1,b+tot+1);

			for(int x=rx;x;x=fa[x]) a[x]-=b[tot>>1];

		}

	}

	for(int i=1;i<=n;i++) r+=abs(a[i]);

	return printf("%d\n",r),0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define REP(i,a,b) for(int i=(a),_ed=(b);i<=_ed;++i)

#define DREP(i,a,b) for(int i=(a),_ed=(b);i>=_ed;--i)

#define pb(x) push_back((x))

typedef long long ll;

inline int read(){

    register int x=0,f=1;register char ch=getchar();

    while(!isdigit(ch)){if(ch=='-')f=0;ch=getchar();}

    while(isdigit(ch)){x=x*10+(ch^'0');ch=getchar();}

    return f?x:-x;

}



const int N=1e5+5;

int n,m,dep[N],s,t,flg,S[N],k[N],stk[N],tp;

ll ans;

vector<int> E[N];



inline void Dfs(int u,int pa){

    for(int v:E[u]){

	if(v==pa)continue;

	if(dep[v]){flg=(dep[u]==dep[v]);s=u,t=v;continue;}

	dep[v]=dep[u]*-1;Dfs(v,u);

    }

}

inline void Cal(int u,int pa){

    for(int v:E[u]){

	if(v==pa||(u==s&&v==t)||(v==s&&u==t))continue;

	Cal(v,u);

	S[u]+=S[v];k[u]+=k[v];

    }

}



int main(){

    //freopen("in.in","r",stdin);

    n=read(),m=read();

    REP(i,1,m){int u=read(),v=read();E[u].pb(v),E[v].pb(u);}

    dep[1]=1;Dfs(1,0);

    int sum=0;

    REP(i,1,n)sum+=(S[i]=dep[i]);

    if(m==n-1){if(sum)return puts("-1"),0;}

    else if((flg&&(sum&1))||(!flg&&sum))return puts("-1"),0;

    if(m==n){

	if(flg){

	    S[s]-=sum/2,S[t]-=sum/2;

	    ans+=abs(sum/2);

	}

	else k[s]=1,k[t]=-1;

    }

    Cal(1,0);

    REP(i,1,n)

	if(!k[i])ans+=abs(S[i]);

	else if(~k[i])stk[++tp]=-S[i];

	else stk[++tp]=S[i];

    stk[++tp]=0;

    sort(stk+1,stk+tp+1);

    int x=stk[(tp+1)>>1];

    REP(i,1,tp)ans+=abs(stk[i]-x);

    printf("%lld\n",ans);

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 3.539091801637167x):
#include<bits/stdc++.h>

#define re register

#define inc(i,j,k) for(re int i=j;i<=k;i++)

using namespace std;

const int N=1e5+5;

int a[N],fa[N],head[N],cnt,b[N],p;

int getfa(int x){return fa[x]==x?x:fa[x]=getfa(fa[x]);}

struct egde{

	int to,nxt;

}e[N<<1];

void add(int a,int b){

	e[++cnt].to=b;

	e[cnt].nxt=head[a];

	head[a]=cnt;

}

void dfs(int u,int type){

	a[u]=type;

	for(re int i=head[u];i;i=e[i].nxt){

		int v=e[i].to;

		if(v==fa[u]) continue;

		fa[v]=u;

		dfs(v,-type);

		a[u]+=a[v];

	}

}

int main(){

	int n,m,rt=1,rs=1,ans=0;

	scanf("%d%d",&n,&m);

	inc(i,1,n) fa[i]=i;

	inc(i,1,m){

		int x,y;

		scanf("%d%d",&x,&y);

		if(getfa(x)!=getfa(y)) fa[fa[x]]=fa[y];

		else{rt=x,rs=y;continue;}

		add(x,y),add(y,x);

	}

	fa[rt]=0,dfs(rt,1);

	if(n==m){

		for(re int i=rs;i;i=fa[i]) b[++p]=a[i];

		if(p&1){

			if(a[rt]&1) return puts("-1"),0;

			for(re int i=rs;i;i=fa[i]) a[i]-=a[rt]>>1;

		}

		else{

			if(a[rt]) return puts("-1"),0;

			sort(b+1,b+p+1);

			for(re int i=rs;i;i=fa[i]) a[i]-=b[p>>1]; 

		}

	}

	else if(a[rt]) return puts("-1"),0;

	inc(i,1,n) ans+=abs(a[i]);

	printf("%d",ans);

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define REP(i,a,b) for(int i=(a),_ed=(b);i<=_ed;++i)

#define DREP(i,a,b) for(int i=(a),_ed=(b);i>=_ed;--i)

#define pb(x) push_back((x))

typedef long long ll;

inline int read(){

    register int x=0,f=1;register char ch=getchar();

    while(!isdigit(ch)){if(ch=='-')f=0;ch=getchar();}

    while(isdigit(ch)){x=x*10+(ch^'0');ch=getchar();}

    return f?x:-x;

}



const int N=1e5+5;

int n,m,dep[N],s,t,flg,S[N],k[N],stk[N],tp;

ll ans;

vector<int> E[N];



inline void Dfs(int u,int pa){

    for(int v:E[u]){

	if(v==pa)continue;

	if(dep[v]){flg=(dep[u]==dep[v]);s=u,t=v;continue;}

	dep[v]=dep[u]*-1;Dfs(v,u);

    }

}

inline void Cal(int u,int pa){

    for(int v:E[u]){

	if(v==pa||(u==s&&v==t)||(v==s&&u==t))continue;

	Cal(v,u);

	S[u]+=S[v];k[u]+=k[v];

    }

}



int main(){

    //freopen("in.in","r",stdin);

    n=read(),m=read();

    REP(i,1,m){int u=read(),v=read();E[u].pb(v),E[v].pb(u);}

    dep[1]=1;Dfs(1,0);

    int sum=0;

    REP(i,1,n)sum+=(S[i]=dep[i]);

    if(m==n-1){if(sum)return puts("-1"),0;}

    else if((flg&&(sum&1))||(!flg&&sum))return puts("-1"),0;

    if(m==n){

	if(flg){

	    S[s]-=sum/2,S[t]-=sum/2;

	    ans+=abs(sum/2);

	}

	else k[s]=1,k[t]=-1;

    }

    Cal(1,0);

    REP(i,1,n)

	if(!k[i])ans+=abs(S[i]);

	else if(~k[i])stk[++tp]=-S[i];

	else stk[++tp]=S[i];

    stk[++tp]=0;

    sort(stk+1,stk+tp+1);

    int x=stk[(tp+1)>>1];

    REP(i,1,tp)ans+=abs(stk[i]-x);

    printf("%lld\n",ans);

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 3.5764507708469946x):
#include<bits/stdc++.h>

#define R register int

#define G if(++ip==ie)if(fread(ip=buf,1,SZ,stdin))

using namespace std;

const int SZ=1<<19,N=1e5+9,M=2*N;

char buf[SZ],*ie=buf+SZ,*ip=ie-1;

inline int in(){

    G;while(*ip<'-')G;

    R x=*ip&15;G;

    while(*ip>'-'){x*=10;x+=*ip&15;G;}

    return x;

}

int he[N],ne[M],to[M],f[N],a[N],b[N];

int Getf(R x){

    return x==f[x]?x:f[x]=Getf(f[x]);

}

void Dfs(R x,R op){

    a[x]=op;

    for(R y,i=he[x];i;i=ne[i])

        if((y=to[i])!=f[x])

            f[y]=x,Dfs(y,-op),a[x]+=a[y];

}

int main(){

    R n=in(),m=in(),rt=1,re=1,p=0,ans=0;

    for(R i=1;i<=n;++i)f[i]=i;

    for(R p=0,i=1;i<=m;++i){

        R x=in(),y=in();

        if(Getf(x)!=Getf(y))f[f[x]]=f[y];

        else{rt=x,re=y;continue;}

        ne[++p]=he[x];to[he[x]=p]=y;

        ne[++p]=he[y];to[he[y]=p]=x;

    }

    f[rt]=0;Dfs(rt,1);

    if(n==m){

        for(R x=re;x;x=f[x])b[++p]=a[x];

        if(p&1){

            if(a[rt]&1)return puts("-1"),0;

            for(R x=re;x;x=f[x])a[x]-=a[rt]/2;

        }

        else{

            if(a[rt])return puts("-1"),0;

            sort(b+1,b+p+1);

            for(R x=re;x;x=f[x])a[x]-=b[p/2];

        }

    }

    else if(a[rt])return puts("-1"),0;

    for(R i=1;i<=n;++i)ans+=abs(a[i]);

    return cout<<ans<<endl,0;

}
// Slower C++ solution:
#include <iostream> 



#include <stdio.h>

using namespace std; 

typedef long ll;



 int main(){



    int length;

    ll arr[200000];

    ll res[200000]={0};

    ll temp = 0;

    ll m = 2147483647;

    scanf("%d",&length);

   	for(int i=0;i<length;++i){

   		scanf("%ld",&arr[i]);

   	}

   	res[0] = arr[0];

    for(int i=1;i<length;++i){

    	res[i] += res[i-1] + arr[i];

    }

    for(int i=1;i<length;++i){

    	temp = abs(res[length-1]-res[i-1]*2);

    	m = min(temp,m);

    }

    printf("%ld\n", m);





 	return 0;

 }


// Faster C++ solution for the same problem (measured speedup: 1.4644802315484804x):
#include<stdio.h>



long long int abs_1(long long int i){

	if(i<0) return -i;

	else return i;

}

int main()

{

	 int N,i,j;

	 long long int sum1=0,sum=0;

	scanf("%d",&N);

	long long int a[200000]={0},x,min=2e+9;

	for(i=0;i<N;i++)

	{

		scanf("%lld",&a[i]);

		sum+=a[i];

	}

	for(i=0;i<N-1;i++)

	{

		sum1+=a[i];

		x=abs_1(2*sum1-sum);

		if(x<=min)

		{

			min=x;

		}

	}

	printf("%lld",min);

	return 0;

}
// Slower C++ solution:
#include <iostream> 



#include <stdio.h>

using namespace std; 

typedef long ll;



 int main(){



    int length;

    ll arr[200000];

    ll res[200000]={0};

    ll temp = 0;

    ll m = 2147483647;

    scanf("%d",&length);

   	for(int i=0;i<length;++i){

   		scanf("%ld",&arr[i]);

   	}

   	res[0] = arr[0];

    for(int i=1;i<length;++i){

    	res[i] += res[i-1] + arr[i];

    }

    for(int i=1;i<length;++i){

    	temp = abs(res[length-1]-res[i-1]*2);

    	m = min(temp,m);

    }

    printf("%ld\n", m);





 	return 0;

 }


// Faster C++ solution for the same problem (measured speedup: 2.678572517592531x):
#include<iostream>

#include<cmath>

using namespace std;

const int MAXN = 2e5 + 100;

long long x,sum[MAXN],n,min_,i;

int main()

{

    cin>>n;

    sum[0]=0;

    for(i=1;i<=n;i++)

       {

           cin>>x;

           sum[i]=sum[i-1]+x;

       }

    min_=abs(2*sum[1]-sum[n]);

   for(i=2;i<n;i++)

   {

       min_=min_<abs(2*sum[i]-sum[n])?min_:abs(2*sum[i]-sum[n]);

   }

    cout<<min_;

}
// Slower C++ solution:
#include<stdio.h>



long long int abs_1(long long int i){

	if(i<0) return -i;

	else return i;

}

int main()

{

	 int N,i,j;

	 long long int sum1=0,sum=0;

	scanf("%d",&N);

	long long int a[200000]={0},x,min=2e+9;

	for(i=0;i<N;i++)

	{

		scanf("%lld",&a[i]);

		sum+=a[i];

	}

	for(i=0;i<N-1;i++)

	{

		sum1+=a[i];

		x=abs_1(2*sum1-sum);

		if(x<=min)

		{

			min=x;

		}

	}

	printf("%lld",min);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.829026066647769x):
#include<iostream>

#include<cmath>

using namespace std;

const int MAXN = 2e5 + 100;

long long x,sum[MAXN],n,min_,i;

int main()

{

    cin>>n;

    sum[0]=0;

    for(i=1;i<=n;i++)

       {

           cin>>x;

           sum[i]=sum[i-1]+x;

       }

    min_=abs(2*sum[1]-sum[n]);

   for(i=2;i<n;i++)

   {

       min_=min_<abs(2*sum[i]-sum[n])?min_:abs(2*sum[i]-sum[n]);

   }

    cout<<min_;

}
// Slower C++ solution:
#include <iostream> 



#include <stdio.h>

using namespace std; 

typedef long ll;



 int main(){



    int length;

    ll arr[200000];

    ll res[200000]={0};

    ll temp = 0;

    ll m = 2147483647;

    scanf("%d",&length);

   	for(int i=0;i<length;++i){

   		scanf("%ld",&arr[i]);

   	}

   	res[0] = arr[0];

    for(int i=1;i<length;++i){

    	res[i] += res[i-1] + arr[i];

    }

    for(int i=1;i<length;++i){

    	temp = abs(res[length-1]-res[i-1]*2);

    	m = min(temp,m);

    }

    printf("%ld\n", m);





 	return 0;

 }


// Faster C++ solution for the same problem (measured speedup: 2.347015183840847x):
#include <iostream>

using namespace std;

int main()

{

	int a[200010];

	long long int b[200010];

	int N = 2;

	cin >> N;

	for (int i = 1; i <= N; i++)

	{

		cin >> a[i];

	}

	long long int sum = 0;

	long long int m, n;

	for(int j=1;j<=N;j++)

	{

		sum = sum + a[j];

	}

	m = sum;

	n = sum;

	long long int x[200009], y[200009];

	for (int j = 1; j <= (N - 1); j++)

	{

		y[j] = sum - a[j];

		sum = sum - a[j];

	}

	for (int k = 1; k <= (N - 1); k++)

	{

		x[k] = m - y[k];

		m = n;

	}

	for (int n = 1; n <= (N - 1); n++)

	{

		b[n] = abs(x[n] - y[n]);

	}

	long long int min = b[1];

	for (int i = 2; i <= N - 1; i++)

	{

		if (min > b[i])

			min = b[i];

	}

	cout << min<<endl;

	return 0;

}
// Slower C++ solution:
#include<stdio.h>



long long int abs_1(long long int i){

	if(i<0) return -i;

	else return i;

}

int main()

{

	 int N,i,j;

	 long long int sum1=0,sum=0;

	scanf("%d",&N);

	long long int a[200000]={0},x,min=2e+9;

	for(i=0;i<N;i++)

	{

		scanf("%lld",&a[i]);

		sum+=a[i];

	}

	for(i=0;i<N-1;i++)

	{

		sum1+=a[i];

		x=abs_1(2*sum1-sum);

		if(x<=min)

		{

			min=x;

		}

	}

	printf("%lld",min);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.6026267431136374x):
#include <iostream>

using namespace std;

int main()

{

	int a[200010];

	long long int b[200010];

	int N = 2;

	cin >> N;

	for (int i = 1; i <= N; i++)

	{

		cin >> a[i];

	}

	long long int sum = 0;

	long long int m, n;

	for(int j=1;j<=N;j++)

	{

		sum = sum + a[j];

	}

	m = sum;

	n = sum;

	long long int x[200009], y[200009];

	for (int j = 1; j <= (N - 1); j++)

	{

		y[j] = sum - a[j];

		sum = sum - a[j];

	}

	for (int k = 1; k <= (N - 1); k++)

	{

		x[k] = m - y[k];

		m = n;

	}

	for (int n = 1; n <= (N - 1); n++)

	{

		b[n] = abs(x[n] - y[n]);

	}

	long long int min = b[1];

	for (int i = 2; i <= N - 1; i++)

	{

		if (min > b[i])

			min = b[i];

	}

	cout << min<<endl;

	return 0;

}