神仙题。

考虑一个 $n$ 个点的树的情况怎么处理。

首先进行一次转化，树是一个二分图，于是就进行一次二分图染色。不难发现新图上两端颜色不同当且仅当原图两端颜色相同，所以我们可以把操作从同色翻转变成异色反转，也就是我们进行的操作其实就是在新图上移动黑色点。抄一个官方题解的图：

_ZJXZH7_FJJB91Y`3TKZRI0.png

然后问题就变成了一棵树，有一些位置是黑色点，一些位置是白色点，我们每次要移动一个黑色点到相邻的白色点，最后要让所有黑色点归位。

对于树的情况，如果黑点白点数量不同，必然无解。

这是一个经典模型，首先答案是有下界的。我们随意取一个根，对于一个子树，我们设它内部的黑点数减去白点数量为 $a$ ，那么这个子树向上的边至少会被经过 $a$ 次。我们可以证明这个下界是可以达到的。首先，如果不考虑同一个点上不能有两个黑色点，那么移动的次数相当于是一个最小权匹配。这个东西对于一条边，它被经过的次数显然可以是它一边的黑色点个数与白色点个数的差值。因为剩下的可以在内部匹配。然后考虑黑色点不能覆盖，那么对于之前的一种 $u \to v$ 的移动方案，假设中间存在第一个 $t$ 在 $u \to v$ ，那么我们可以让 $t \to v$ 并且让 $u \to t$ 。这样不断调整，一定可以达成 $u$ 上的黑点到达 $v$ 上的目的。

于是答案就是下界 $\sum |a_i|$ 。

具体做法就是，给白色点权值设为 $-1$ ，黑色点设为 $+1$ ，然后求所有位置子树和的绝对值和。

然后就是基环树。

如果环是偶环，那么环边的两侧的颜色是不同的。设环边是 $u \to v$ ， 我们假定这个边会操作 $x$ 次（如果 $x < 0$ 就说明从 $v$ 向 $u$ 操作）。于是我们考虑环中边与环的顶点分成的这两部分，一部分到父亲的边一定会多向下操作 $x$ 次，另一部分到父亲的边一定会多向上操作 $x$ 次。于是设把这条边断掉后每个点跑出的答案是 $a_i$ ，那么最后的答案就是

$$\sum_{i \in left} |a_i - x| + \sum_{i\in right} |-a_i-x| + |-x|$$

这个东西就是在数轴上一些点到 $x$ 的和的最小值。可以确定出 $x$ 的值。

如果环是奇环，那么环边操作一次就会让黑色点增加 $2$ 或者让黑色点减少 $2$ 。不难发现，这种情况下如果黑色点白色点的差是偶数就一定可以通过操作这个白边来让整个图有一个解，并且这种边的唯一用处就是用来增加点。

于是我们可以直接给这条基环边的两侧加上全图黑色点与白色点的差除以 $2$ ，然后跑树的做法即可。

cpp

int n , m;
int A[MAXN];
vi G[MAXN];
int w[MAXN] , od , ev , s = 0;
int lu , lv , fa[MAXN];
void dfs( int u , int f , int wu ) {
	w[u] = wu , s += wu;
	for( int v : G[u] ) if( v != f ) {
		if( w[v] ) {
			if( w[v] * w[u] > 0 ) od = 1;
			else ev = 1;
			lu = u , lv = v;
		} else {
			fa[v] = u;
			dfs( v , u , wu * -1 );
		}
	}
}
int dep[MAXN];
void cfs( int u , int f ) {
	dep[u] = dep[f] + 1;
	for( int v : G[u] ) if( v != f ) {
		if( dep[v] ) continue;
		cfs( v , u );
		w[u] += w[v];
	}
}
int onc[MAXN];
void solve() {
	cin >> n >> m;
	rep( i , 1 , m ) {
		static int u , v;
		scanf("%d%d",&u,&v);
		G[u].pb( v ) , G[v].pb( u );
	}
	dfs( 1 , 1 , 1 );
	if( s & 1 ) return void( puts("-1") );
	ll res = 0;
	if( od ) {
		w[lu] -= s >> 1 , w[lv] -= s >> 1;
		res += abs( s >> 1 );
		s = 0;
	}
	if( s ) return void( puts("-1") );
	cfs( 1 , 1 );
	if( ev ) {
		vi ps;
		if( dep[lu] < dep[lv] ) swap( lu , lv );
		while( dep[lu] != dep[lv] ) onc[lu] = 1 , ps.pb( w[lu] ) , lu = fa[lu];
		ps.pb( 0 );
		sort( all( ps ) );
		int t = ps[ps.size() / 2];
		for( int x : ps ) res += abs( x - t );
	}
	rep( i , 1 , n ) if( !onc[i] ) res += abs( w[i] );
	printf("%lld\n",res);
}
 
signed main() {
//    int T;cin >> T;while( T-- ) solve();
    solve();
}