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;

#define for_(i,a,b) for(int i=(a);i<(b);++i)
typedef long long lint;
typedef pair< int, int > pii;

int N, M, part_cnt[100010], dp[100010];
vector< vector< int > > adj;
vector< int > g[2], col;

bool dfs(int v, int c) {
	if (col[v] != -1) {
		if (col[v] != c) return false;
		return true;
	}
	
	col[v] = c;
	g[c].push_back(v);
	
	for (int u : adj[v]) if (!dfs(u, 1 - c)) return false;
	
	return true;
}

lint calc(lint A) {
	memset(dp, -1, sizeof(dp));
	
	dp[0] = 0;
		
	for (int a = 0; a <= N; ++a) {
		int c = part_cnt[a];
		if (c == 0) continue;
		
		for_(j,0,N+1) {
			if (dp[j] >= 0) {
				dp[j] = c;
			} else if (j < a || dp[j - a] <= 0) {
				dp[j] = -1;
			} else {
				dp[j] = dp[j - a] - 1;
			}
		}
	}
	
	lint res = 0;
	
	for_(a,0,N+1) {
		if (dp[a] == -1) continue;
		lint B = N - (A + a);
		res = max(res, (A + a) * B);
	}
	
	return res;
}

void solve() {
	col.assign(N, -1);
	memset(part_cnt, 0, sizeof(part_cnt));
	
	bool flag = true;
	lint A = 0;
	
	for_(v,0,N) {
		if (col[v] != -1) continue;
		for_(i,0,2) g[i].clear();
		
		flag &= dfs(v, 0);
		
		int a = min(g[0].size(), g[1].size()), b = max(g[0].size(), g[1].size());
		++part_cnt[b - a];
		A += a;
	}
		
	cout << (!flag ? -1 : calc(A) - M) << endl;
}

int main() {
	cin >> N >> M;
	
	adj.assign(N, vector< int >());
	
	for_(i,0,M) {
		int u, v;
		scanf("%d %d", &u, &v);
		--u; --v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	
	solve();
}