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<queue>
#include<map>
#include<cmath>
using namespace std;
int n, m, a, b, d, u[200000]; vector<int>x[100000], c[100000], H; bool used[100000], f[200009], g[200009];
vector<pair<int, int>>I;
bool solve() {
	vector<int>col(n, -1);
	for (int i = 0; i < d; i++) {
		queue<int>Q; col[c[i][0]] = 0; Q.push(c[i][0]);
		while (!Q.empty()) {
			int a1 = Q.front(); Q.pop();
			for (int j : x[a1]) {
				if (col[j] == -1) { Q.push(j); col[j] = 1 - col[a1]; }
				else if (col[j] == col[a1]) { return false; }
			}
		}
		int v = 0; for (int j = 0; j < c[i].size(); j++) { if (col[c[i][j]] == 0)v++; else v--; }
		H.push_back(abs(v));
	}
	return true;
}
void knapsack() {
	for (int i = 0; i <= n * 2; i++)f[i] = false; f[n] = true;
	for (int i = 0; i < I.size(); i++) {
		for (int j = 0; j <= n * 2; j++) { g[j] = false; u[j] = -1; }
		for (int j = 0; j <= n * 2; j++) {
			if (f[j] == false)continue;
			int r1 = I[i].first * 2;
			if (r1 == 0) { g[j] = true; continue; }
			int r3 = I[i].first*I[i].second*-1, r4 = -r3; r4 += j; r3 += j;
			r3 = max(r3, u[r3%r1]);
			for (int k = r3; k <= r4; k += r1) { g[k] = true; u[k%r1] = k; }
		}
		for (int j = 0; j <= n * 2; j++)f[j] = g[j];
	}
}
int main() {
	cin >> n >> m; for (int i = 0; i < m; i++) { cin >> a >> b; a--; b--; x[a].push_back(b); x[b].push_back(a); }
	for (int i = 0; i < n; i++) {
		if (used[i] == true)continue; queue<int>Q;
		Q.push(i); used[i] = true;
		while (!Q.empty()) {
			int a1 = Q.front(); Q.pop(); c[d].push_back(a1);
			for (int j : x[a1]) {
				if (used[j] == false) { Q.push(j); used[j] = true; }
			}
		}
		d++;
	}
	bool U = solve(); map<int, int>M, M2;
	if (U == false) { cout << "-1" << endl; return 0; }
	for (int i = 0; i < H.size(); i++) M[H[i]]++;
	for (int i = 0; i < H.size(); i++) {
		if (M2[H[i]] == 0) { M2[H[i]] = 1; I.push_back(make_pair(H[i], M[H[i]])); }
	}
	knapsack();
	long long ret = 0;
	for (int i = 0; i <= n; i++) { if (f[2 * i] == true)ret = max(ret, 1LL * (n - i)*i); }
	cout << ret - m << endl;
	return 0;
}