Submission #1840992

---

Source Code Expand

#include <cstdio>
#include <iostream>
#include <algorithm>
inline int Get() {
	char ch;
	while ((ch = getchar()) < '0' || ch > '9');
	int Num = ch - '0';
	while ((ch = getchar()) >= '0' && ch <= '9')
		Num = (Num << 3) + (Num << 1) + ch - '0';
	return Num;
}
const int N = 1e5 + 5;
int n, m, que[N], qn, fa[N], g[N], deg[N], flag[N], a[N], cnt;
int tot, first[N], next[N << 1], end[N << 1], ans, sum[N], ret[N], w[N];
inline void AddEdge(int x, int y) {
	++deg[x], ++deg[y];
	next[++tot] = first[x], first[x] = tot, end[tot] = y;
	next[++tot] = first[y], first[y] = tot, end[tot] = x;
}
int calc(int x) {
	que[qn = 1] = x, fa[x] = 0;
	for (int ql = 1, u; u = que[ql], ql <= qn; ++ql)
		for (int k = first[u], v; v = end[k], k; k = next[k])
			if (v != fa[u] && deg[v] < 2) fa[v] = u, que[++qn] = v;
	
	int res = 0;
	for (int qr = qn, u; u = que[qr], qr; --qr) 
		for (int k = first[u], v; v = end[k], k; k = next[k])
			if (v != fa[u] && deg[v] < 2) {
				int delta = 1 - g[v];
				res += delta > 0 ? delta : -delta;
				g[u] += delta, g[v] += delta;
			}
	
	return res;
}
inline int Abs(int x) {
	return x > 0 ? x : -x;
}
int main() {
	n = Get(), m = Get();
	for (int i = 1; i <= m; ++i) AddEdge(Get(), Get());
	
	for (int i = 1; i <= n; ++i) if (deg[i] < 2) que[++qn] = i, flag[i] = true;
	for (int ql = 1, u; u = que[ql], ql <= qn; ++ql)
		for (int k = first[u], v; v = end[k], k; flag[v] = true, k = next[k])
			if ((deg[v]--) == 2) que[++qn] = v;
		
	int x = 0;
	for (int i = 1; i <= n; ++i) if (deg[i] > 1) x = i;
	
	if (!x) {
		ans = calc(1);
		printf("%d\n", g[1] == 1 ? ans : -1);
		return 0;
	}

	a[cnt = 1] = x;
	while (true) {
		int u = a[cnt];
		for (int k = first[u], v; v = end[k], k; k = next[k])
			if (deg[v] > 1 && v != a[cnt - 1]) {
				a[++cnt] = v; break;
			}
			
		if (a[cnt] == x) {
			--cnt; break;
		}
	}
		
	for (int k = 1, u; u = a[k], k <= cnt; ++k) if (flag[u]) ans += calc(u);
	for (int k = 1, u; u = a[k], k <= cnt; ++k) sum[k] = 1 - g[u];
	
	ret[1] = 0;
	for (int k = 2; k <= cnt; ++k) ret[k] = sum[k] - ret[k - 1];
	
	if (cnt & 1) {
		int y = sum[1] - ret[1] - ret[cnt];
		if (y & 1) {
			puts("-1");
			return 0;
		}
		
		y >>= 1;
		for (int i = 1; i <= cnt; ++i)
			if (i & 1) ans += Abs(ret[i] + y); else ans += Abs(ret[i] - y);
	}
	else {
		if (ret[1] + ret[cnt] != sum[1]) {
			puts("-1");
			return 0;
		}
		
		for (int i = 1; i <= cnt; ++i)
			if (i & 1) w[i] = -ret[i]; else w[i] = ret[i];
			
		std :: sort(w + 1, w + cnt + 1);
		for (int i = 1; i <= cnt; ++i)
			if (i * 2 <= cnt) ans -= w[i]; else ans += w[i];
	}
	printf("%d\n", ans);
}

Submission Info

Judge Result