Problem: Example

Input

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


Output

11

Solution (in CPP):

Solution:
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <bitset>
using namespace std;

int n;
vector<vector<int>> g;
vector<int> color;
vector<int> parts;
vector<pair<int, int>> ps;

bool dfs(int u, int c) {
    color[u] = c;
    parts[c]++;
    for (int v: g[u]) {
        if (~color[v]) {
            if (color[v] == color[u]) return false;
        } else {
            if (!dfs(v, c ^ 1)) return false;
        }
    }
    return true;
}

bool is_bipartite() {
    color.assign(n, -1);
    parts.assign(2, 0);
    for (int u = 0; u < n; u++) if (color[u] == -1) {
        if (!dfs(u, 0)) return false;
        ps.emplace_back(parts[0], parts[1]);
        parts.assign(2, 0);
    }
    return true;
}

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    int m; cin >> n >> m;
    g.resize(n);
    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b; a--; b--;
        g[a].emplace_back(b);
        g[b].emplace_back(a);
    }
    if (!is_bipartite()) return !(cout << -1 << endl);
    map<int, int> diff;
    for (auto &p: ps) diff[abs(p.first - p.second)]++;
    bitset<(int)2e5 + 1> dp; dp.set(n);
    vector<int> ds;
    for (auto &p: diff) {
        int u = 1;
        while (p.second >= u) {
            ds.emplace_back(p.first * u);
            p.second -= u, u <<= 1;
        }
        if (p.second) ds.emplace_back(p.first * p.second);
    }
    for (auto d: ds) dp = dp << d | dp >> d;
    long long ma = 0;
    for (int d = 0; d <= n; d++) if (dp[d + n]) {
        int t = (n - d) / 2;
        ma = max(ma, 1LL * t * (t + d));
    }
    cout << ma - m << endl;
    return 0;
}