Problem: Example

Input

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


Output

11

Solution (in CPP):

Solution:
#include <iostream>
#include <vector>
#include <utility>
#include <map>
#define llint long long
#define inf 1e18

using namespace std;
typedef pair<llint, llint> P;

llint V, E;
vector<llint> G[100005];
llint color[100005];
map<llint, llint> mp;
llint dp[2][100005];

P dfs(int v, int prev, int c)
{
	color[v] = c;
	P ret = make_pair(0, 0);
	if(c == 1) ret.first++;
	else ret.second++;
	
	for(int i = 0; i < G[v].size(); i++){
		if(G[v][i] == prev) continue;
		if(color[G[v][i]]){
			if(color[G[v][i]] != -c) return make_pair(-1, -1);
			else continue;
		}
		P res = dfs(G[v][i], v, -c);
		if(res.first == -1) return make_pair(-1, -1);
		ret.first += res.first;
		ret.second += res.second;
	}
	return ret;
}

int main(void)
{
	cin >> V >> E;
	llint a, b;
	for(llint i = 0; i < E; i++){
		cin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	
	llint goal = 0;
	for(llint i = 1; i <= V; i++){
		if(color[i]) continue;
		P res = dfs(i, -1, 1);
		if(res.first == -1){
			cout << -1 << endl;
			return 0;
		}
		goal += abs(res.first - res.second);
		mp[2 * abs(res.first - res.second)]++;
	}
	llint N = mp.size();
	
	for(llint j = 0; j <= V; j++){
		dp[0][j] = dp[1][j] = -1;
	}
	dp[0][0] = 0;
	
	auto it = mp.begin();
	for(llint i = 1; i <= N; i++){
		for(llint j = 0; j <= V; j++){
			if(dp[(i+1)%2][j] >= 0) dp[i%2][j] = max(dp[i%2][j], it->second);
			if(j - it->first >= 0){
				if(dp[i%2][j - it->first] >= 1) dp[i%2][j] = max(dp[i%2][j], dp[i%2][j - it->first] - 1);
			}
		}
		it++;
	}
	
	llint close_val = inf, close_i;
	for(llint i = 0; i <= V; i++){
		if(dp[N%2][i] < 0) continue;
		if(close_val > abs(goal - i)){
			close_val = abs(goal - i);
			close_i = i;
		}
	}
	
	llint black = (close_i - goal + V) / 2;
	llint ans = black * (V - black) - E;
	cout << ans << endl;
	return 0;
}