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"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;

vector<pair<int,int>>colors;
vector<vector<int>>edges;
pair<int,int> dfs(const int now,const int num) {
	const int nextcolor = !colors[now].second;
	pair<int, int>nums(0,0);
	if (colors[now].second == 1)nums.second++;
	else nums.first++;
	for (auto e : edges[now]) {
		if (colors[e].second == -1) {
			colors[e] = make_pair(now,nextcolor);
			pair<int,int>p=dfs(e, num);
			if (!p.first&&!p.second)return p;
			nums.first += p.first;
			nums.second += p.second;
		}
		else if (colors[e].second != nextcolor)return make_pair(0, 0);
	}
	return nums;
}

bool dp[2][100001];
int main() {
	int V, E; cin >> V >> E;
	for (int i = 0; i < V; ++i) {
		colors.push_back(make_pair(-1, -1));
	}
	edges.resize(V);
	for (int i = 0; i < E; ++i) {
		int a, b; cin >> a >> b;
		a--; b--;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}
	int color = 0;
	vector<pair<int, int>>ps;
	bool ok = true;
	for (int i = 0; i < V; ++i) {
		if (colors[i].second == -1) {
			colors[i] = make_pair(color,0);
			pair<int,int>p=dfs(i, color);
			if (!p.first&&!p.second) {
				ok = false;
			}
			if (p.first > p.second)swap(p.first, p.second);
			ps.push_back(p);
			color++;
		}
	}
	if (!ok) {
		cout << -1 << endl;
	}
	else {
		int amin = 0;
		map<int,int>pluss;
		for (int i = 0; i < ps.size(); ++i) {
			amin += ps[i].first;
			if (ps[i].first != ps[i].second) {
				pluss[ps[i].second - ps[i].first]++;
			}
		}
		for (int i = 1; i < 100000; ++i) {
			if (pluss.find(i) != pluss.end()) {
				const int bai = (pluss[i] - 1) / 2;
				if (bai) {


					pluss[2 * i] += bai;
					pluss[i] -= bai * 2;
				}
			}
		}
		vector<int>naps;
		for (int i = 1; i < 100000; ++i) {
			if (pluss.find(i) != pluss.end()) {
				for (int j = 0; j < pluss[i]; ++j) {
					naps.push_back(i);
				}
			}
		}
		dp[0][0] = true;
		for (int i = 0; i < naps.size(); ++i) {
			int tar = i & 1, cur = tar ^ 1;
			for (int i = 0; i < 100001; ++i) {
				dp[cur][i] = 0;
			}
			if (i == 0)assert(tar == 0 && cur == 1);
			for (int j = 0; j < 100000; ++j) {
				if (dp[tar][j]) {
					dp[cur][j] = true;
					dp[cur][j + naps[i]] = true;
				}
			}
		}
		long long int ans = 0;
		for (int i = 0; i < 100000; ++i) {
			if (abs(ans+amin - V / 2)>abs(i+amin - V / 2) && dp[naps.size()%2][i]) {
				ans = i;
			}
		}
		cout << (amin+ans)*(V - ans-amin) - E << endl;
	}
	


	return 0;
}