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 int long long

pair<int, int> dfs(vector<vector<int>> &g, int v, vector<int> &bs, int b, int &f){
	pair<int, int> ans(0, 0);
	if(bs[v] != -1){
		if(bs[v] != b){
			f = 1;
		}
	}
	else{
		bs[v] = b;
		if(b == 0){
			ans.first++;
		}
		else{
			ans.second++;
		}
		for(int i = 0; i < g[v].size(); i++){
			pair<int, int> res = dfs(g, g[v][i], bs, 1 - b, f);
			ans.first += res.first;
			ans.second += res.second;
		}
	}
	return ans;
}

signed main(){
	int N, M, a, b, i;
	scanf("%lld%lld", &N, &M);
	vector<vector<int>> g(N, vector<int>(0));
	for(i = 0; i < M; i++){
		scanf("%lld%lld", &a, &b);
		a--;
		b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	vector<int> bs(N, -1);
	vector<pair<int, int>> ps(0);
	int f = 0;
	for(i = 0; i < N; i++){
		if(bs[i] == -1){
			ps.push_back(dfs(g, i, bs, 0, f));
			if(f == 1){
				printf("-1\n");
				return 0;
			}
		}
	}
/*	for(i = 0; i < ps.size(); i++){
		printf("(%lld, %lld)\n", ps[i].first, ps[i].second);
	}
*/	bitset<50001> dp(1);
	for(i = 0; i < ps.size(); i++){
		dp = ((dp << ps[i].first) | (dp << ps[i].second));
	}
	int near_half = 0;
	for(i = 0; i <= N / 2; i++){
		if(dp[i] == 1){
			near_half = max(near_half, i);
		}
	}
	printf("%lld\n", near_half * (N - near_half) - M);
	return 0;
}