Submission #1814859

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;

#define A first
#define B second

const int MAXN = 1e5+5;

ll n, m, ans;
vector<int> g[MAXN];
bool isc[MAXN];

pii dfs(int v, int f = -1) {
	pii tot = pii(0, 0);
	for (int u : g[v]) {
		if (isc[u] || u == f)
			continue;
		pii t = dfs(u, v);
		tot.A += t.A;
		tot.B += t.B;
	}

	if (tot.A >= tot.B)
		tot.A -= tot.B, tot.B = 0;
	else
		tot.B -= tot.A, tot.A = 0;

	if (tot.B >= 1)
		tot.B--;
	else
		tot.A++;

	ans += (tot.A + tot.B);
	swap(tot.A, tot.B);
	return tot;
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}

	if (n%2 == 1) {
		cout << "-1\n";
		return 0;
	}

	pii t = dfs(0, -1);

	if (t != pii(0, 0)) {
		cout << "-1\n";
		return 0;
	}

	cout << ans << endl;
}

Submission Info

Judge Result