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 <tuple>
#include <algorithm>
#include <numeric>

using namespace std;
using ll = long long;


struct Graph {
    Graph(const int n) : edge(n) {}
    void addEdge(const int from, const int to)
    {
        edge[from].push_back(to);
        edge[to].push_back(from);
    }
    vector<vector<int>> edge;
};

using P = pair<int, int>;
P dfs(const Graph& g, const int s, vector<int>& color, bool black = true)
{
    int b = 1;
    int w = 0;
    color[s] = (int)(black);
    for (const int to : g.edge[s]) {
        if (color[to] != -1) {
            if (black == color[to]) {
                return make_pair(-1, -1);
            }
            continue;
        }
        int sb, sw;
        tie(sw, sb) = dfs(g, to, color, not black);
        if (sw == -1) {
            return make_pair(-1, -1);
        }
        w += sw;
        b += sb;
    }
    return make_pair(b, w);
}

int main()
{
    ll V, E;
    cin >> V >> E;
    Graph g(V);
    for (int i = 0; i < E; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        g.addEdge(a, b);
    }
    vector<int> div;
    vector<int> color(V, -1);
    for (int i = 0; i < V; i++) {
        if (color[i] != -1) {
            continue;
        }
        const auto p = dfs(g, i, color);
        if (p.first == -1) {
            cout << -1 << endl;
            return 0;
        }
        div.push_back(abs(p.first - p.second));
    }

    sort(div.begin(), div.end());
    vector<int> a = div;
    a.erase(unique(a.begin(), a.end()), a.end());
    vector<int> num(a.size());
    int pos = 0;
    for (int i = 0; i < a.size(); i++) {
        int n = 0;
        for (; pos < div.size(); pos++) {
            if (div[pos] == a[i]) {
                n++;
            } else {
                break;
            }
        }
        num[i] = n;
    }
    const int sum = accumulate(div.begin(), div.end(), 0);
    vector<int> dp(sum + 1, -1);
    const int size = a.size();
    dp[0] = 0;
    for (int i = 0; i < size; i++) {
        for (int j = 0; j <= sum; j++) {
            if (dp[j] >= 0) {
                dp[j] = num[i];
            } else if (j < a[i] or dp[j - a[i]] <= 0) {
                dp[j] = -1;
            } else {
                dp[j] = dp[j - a[i]] - 1;
            }
        }
    }
    constexpr ll INF = 1LL << 60;
    ll mini = INF;
    for (int i = 0; i <= sum; i++) {
        if (dp[i] > -1) {
            mini = min(mini, (ll)abs(i - (sum - i)));
        }
    }
    cout << ((V - mini) / 2) * ((V + mini) / 2) - E << endl;

    return 0;
}