AtCoder

分析

分三种情况讨论。

树

给奇数层的点染成白色，偶数层的点染成黑色。

现在问题变成，每次可以交换两个相邻的不同色的点，要让所有黑点变白、白点变黑。

显然，如果黑点数和白点数不同，则无解；否则设白点的权值为 $1$，黑点的权值为 $-1$，$sum_i$ 表示子树中的权值和，那么答案为 $\sum_{i=1}^n |sum_i|$。

奇环

可以看做树多了一条边。继续沿用上面的黑白色，那么多的那条边的两个端点颜色一定相同。

那么对这条边操作一次的话，黑与白的差会改变 $2$。

那么如果差是奇数则无解，否则可以利用这条边，把黑与白的差补成 $0$，转化为树的情况了。

偶环

此时多出来的那条边的两个端点的颜色不同。

假设这条边用了 $w$ 次，那么其中一个点的到 LCA 的 $sum$ 要加上 $w$，另一边要减掉 $w$。

此时的答案是不受影响的点权的绝对值之和加上 $\sum_i |w-k_i\times sum_i|$，这里的 $k_i$ 根据在哪一边取 $\pm 1$。当 $w$ 取中位数取最小值。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,m;

struct Edge { int v,nxt; } e[N<<1];
int head[N],cnt=0;

inline void addEdge(int u,int v) {
    e[++cnt]=(Edge){v,head[u]},head[u]=cnt;
}

namespace task1 {
    int s,c[N],sum[N];
    inline void dfs(int u,int fa) {
        sum[u]=c[u],s+=c[u];
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v; if (v==fa) continue;
            c[v]=-c[u],dfs(v,u),sum[u]+=sum[v];
        }
    }

    inline void work() {
        c[1]=1,dfs(1,0);
        if (s) { puts("-1"); return; }
        int ans=0;
        for (re int i=1;i<=n;++i) ans+=abs(sum[i]);
        printf("%d\n",ans);
    }
}

namespace task2 {
    int c[N],sum[N],fa[N];
    int s,isodd,st,ed;

    namespace odd {
        inline void work() {
            if (s&1) { puts("-1"); return; }
            int dlt=s/2,ans=abs(dlt);
            for (re int i=st;i;i=fa[i]) sum[i]-=dlt;
            for (re int i=ed;i;i=fa[i]) sum[i]-=dlt;
            for (re int i=1;i<=n;++i) ans+=abs(sum[i]);
            printf("%d\n",ans);
        }
    }

    namespace even {
        int tmp[N],mark[N],w;
        inline void work() {
            if (s) { puts("-1"); return; }
            int top=0;
            // DFS 树上两个点是祖先关系
            for (re int i=ed;i!=st&&i;i=fa[i])
                tmp[++top]=sum[i],mark[i]=1;
            sort(tmp+1,tmp+top+1);
            if (top&1) w=tmp[(top+1)/2];
            else w=(tmp[top/2]+tmp[top/2+1])/2;
            int ans=abs(w);
            for (re int i=1;i<=n;++i) {
                if (mark[i]) ans+=abs(sum[i]-w);
                else ans+=abs(sum[i]);
            }
            printf("%d\n",ans);
        }
    }

    inline void dfs(int u,int f) {
        sum[u]=c[u],s+=c[u],fa[u]=f;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v; if (v==f) continue;
            if (c[v]) {
                if (c[u]==c[v]) isodd=1;
                st=u,ed=v;
            }
            else c[v]=-c[u],dfs(v,u),sum[u]+=sum[v];
        }
    }

    inline void work() {
        c[1]=1,dfs(1,0);
        if (isodd) odd::work();
        else even::work();
    }
}

int main() {
    n=read(),m=read();
    for (re int i=1;i<=m;++i) {
        int u=read(),v=read();
        addEdge(u,v),addEdge(v,u);
    }
    if (m==n-1) task1::work();
    else task2::work();
    return 0;
}