Problem: Example

Input

8 5
1 2
6 5
6 4
1 3
4 7


Output

11

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<int> G[100000];
bool flag = false;
int a = 0, b = 0;
int color[100000];

void dfs(int n, int c) {
	color[n] = c;
	if (c - 1) {
		b++;
	}
	else {
		a++;
	}
	for (auto v : G[n]) {
		if (color[v] == 0) {
			dfs(v, 3 - c);
		}
		else if (color[v] == c) {
			flag = true;
		}
	}
}

int main()
{
	cin.sync_with_stdio(false);
	ll V, E;
	cin >> V >> E;
	for (int i = 0, a, b; i < E; i++) {
		cin >> a >> b;
		G[a - 1].push_back(b - 1);
		G[b - 1].push_back(a - 1);
	}
	ll x = 0;
	vector<ll> d;
	for (int i = 0; i < V; i++) {
		if (color[i] == 0) {
			dfs(i, 1);
		}
		if (a != b) {
			d.push_back(abs(a - b) * 2);
			x += abs(a - b);
		}
		a = b = 0;
	}
	sort(d.begin(), d.end());
	ll ma = 0;
	vector<int> dp(x * 2 + 1); dp[0] = 1;
	for (auto bi : d) {
		for (int i = min(x * 2 - bi, ma); i >= 0; i--) {
			if (dp[i]) {
				dp[i + bi] = 1;
				ma = max(ma, i + bi);
			}
		}
	}
	ll res = 0;
	while (dp[x - res] == 0 && dp[x + res] == 0) res++;
	cout << (flag ? -1ll : (V + res) * (V - res) / 4 - E) << endl;
	return 0;
}