Problem: Example

Input

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


Output

11

Solution (in CPP):

Solution:
#include<iostream>
#include<algorithm>
#include<vector>
#include<bitset>
#include<map>

using namespace std;

typedef long long ll;

int N, M;
vector<vector<int>> E;

int color[100001];

void dfs(int pos, int bef, bool now_color, pair<int, int>& cnt) {
	color[pos] = now_color ? 1 : 2;
	if (now_color)cnt.first++;
	else cnt.second++;
	for (int i = 0; i < E[pos].size(); i++) {
		int nxt = E[pos][i];
		if (nxt == bef)continue;
		if (color[nxt] != 0 && color[nxt] + color[pos] != 3) {
			//二部グラフではない
			cnt.first -= 114514, cnt.second -= 114514;
			break;
		}
		if (color[nxt] == 0) {
			dfs(nxt, pos, !now_color, cnt);
		}
	}
}

int main() {

	cin >> N >> M;
	
	E.resize(N);
	for (int i = 0; i < M; i++) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		E[u].push_back(v);
		E[v].push_back(u);
	}

	map<int, int> element_m;
	for (int i = 0; i < N; i++) {
		if (color[i] == 0) {
			pair<int, int> tmp;
			dfs(i, -1, true, tmp);
			if (tmp.first < 0 && tmp.second < 0) {
				cout << -1 << endl;
				return 0;
			}
			element_m[abs(tmp.first - tmp.second)]++;
		}
	}

	vector<pair<int, int>> element;
	for (auto it = element_m.begin(); it != element_m.end(); it++)element.push_back((*it));
	vector<int> dp(2 * N + 100, -1);

	int geta = 0;
	dp[0] = 0;
	for (int i = 0; i < element.size(); i++) {
		geta += element[i].second * element[i].first;
		for (int j = 0; j <= 2 * N; j++) {
			if (dp[j] >= 0)dp[j] = element[i].second;
			else if (j < 2 * element[i].first || dp[j - 2 * element[i].first] == -1)
				dp[j] = -1;//そのまま
			else dp[j] = dp[j - 2 * element[i].first] - 1;
		}
	}

	ll ans = 0;
	for (ll i = 0; i <= 2 * N; i++) {
		if (dp[i] >= 0) {
			ll diff = abs(i - geta);
			ans = max(ans, ((N - diff) / 2) * ((N - diff) / 2 + diff) - M);
		}
	}
	cout << ans << endl;
	return 0;
}