简要题意
略
思路
先考虑树的的情况，直接黑白染色，统计子树和的绝对值即可
再考虑奇环，发现这时会有两个同色相邻点，只需把多余的操作，在这两个点处理掉即可
最后考虑偶环，先断掉一条边，最后再考虑这条边的贡献，推一下柿子，就变成了初中数学题，取中位数即可
code
#include<bits/stdc++.h>
using namespace std;
#define N 100005
#define int long long
int n,m,sum,A,B,ans,top,ji,k;
int h[N],w[N],K[N],q[N];
struct AB{
int a,b,n;
}d[N*2];
void cun(int x,int y){
d[++k]={x,y,h[x]},h[x]=k;
}
void dfs(int x,int fa){
for(int i=h[x];i;i=d[i].n){
int y=d[i].b;
if(y==fa) continue;
if(w[y]) ji=(w[x]==w[y]),A=x,B=y;
else w[y]=-w[x],dfs(y,x);
}
sum+=w[x];
}
void dfs2(int x,int fa){
for(int i=h[x];i;i=d[i].n){
int y=d[i].b;
if(y==fa||(x==A&&y==B)||(x==B&&y==A)) continue;
dfs2(y,x);w[x]+=w[y],K[x]+=K[y];
}
}
signed main(){
freopen("color.in","r",stdin);
freopen("color.out","w",stdout);
scanf("%lld%lld",&n,&m);
for(int i=1,x,y;i<=m;i++){
scanf("%lld%lld",&x,&y);
cun(x,y),cun(y,x);
}
if(n&1){
printf("-1");
return 0;
}
w[1]=1;dfs(1,0);
if(sum&&!ji){
printf("-1\n");
return 0;
}
if(ji&&n==m) ans+=abs(sum>>1),w[A]-=(sum>>1),w[B]-=(sum>>1);
else if(n==m) K[A]=1,K[B]=-1;
dfs2(1,0);
for(int i=1;i<=n;i++){
if(K[i]) q[++top]=K[i]*w[i];
else ans+=abs(w[i]);
}
q[++top]=0;
sort(q+1,q+1+top);
int zws=q[(top+1)/2];
for(int i=1;i<=top;i++) ans+=abs(q[i]-zws);
printf("%lld\n",ans);
return 0;
}