Problem: Example

Input

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


Output

11

Solution (in CPP):

Solution:
#include <bitset>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int V, E, a, b, col[100009]; bool flag; vector<int> g[100009];
void dfs(int pos) {
	a++;
	if (col[pos] == 1) b++;
	for (int i : g[pos]) {
		if (col[pos] == col[i]) flag = true;
		if (!col[i]) col[i] = 3 - col[pos], dfs(i);
	}
}
int main() {
	scanf("%d %d", &V, &E);
	for (int i = 0; i < E; i++) {
		scanf("%d %d", &a, &b); a--, b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	bitset<100001> dp = 1;
	int cur = 0;
	for (int i = 0; i < V; i++) {
		if (!col[i]) {
			a = b = 0; col[i] = 1;
			dfs(i);
			if (b * 2 > a) b = a - b;
			cur += b;
			dp |= dp << (a - b * 2);
		}
	}
	long long ret = 0;
	for (int i = cur; i <= V; i++) {
		if (dp[i - cur]) ret = max(ret, 1LL * i * (V - i));
	}
	printf("%lld\n", (flag ? -1LL : ret - E));
	return 0;
}