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>
using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int, int>;

constexpr int INF = 1e9;

using graph = vector<vector<int>>;

bool dfs(graph const& g, int v, int b, vector<int>& visited, pii& res) {
    (b ? res.first : res.second) += 1;
    visited[v] |= (1 << b);
    bool ret = (visited[v] == 0b11);
    for(auto to : g[v]) {
        int nb = !b;
        if(visited[to] & (1 << nb)) {
            continue;
        }
        ret |= dfs(g, to, nb, visited, res);
    }
    return ret;
}

int main() {
    int V, E;
    cin >> V >> E;
    graph g(V);
    for(int i = 0; i < E; ++i) {
        int a, b;
        cin >> a >> b;
        g[a - 1].push_back(b - 1);
        g[b - 1].push_back(a - 1);
    }

    vector<int> visited(V);
    vector<int> C(V + 1);
    ll sum = 0;
    for(int i = 0; i < V; ++i) {
        if(visited[i] == 0) {
            auto p = make_pair(0, 0);
            if(dfs(g, i, 0, visited, p)) {
                cout << -1 << endl;
                return 0;
            }
            if(p.first > p.second) {
                swap(p.first, p.second);
            }
            C[p.second - p.first]++;
            sum += p.first;
        }
    }
    vector<pii> s;
    for(int i = 1; i < C.size(); ++i) {
        if(C[i] > 0) {
            s.emplace_back(i, C[i]);
        }
    }

    vector<bool> dp(V + 1);
    dp[0] = true;
    for(int i = 0; i < s.size(); ++i) {
        auto nxt = dp;
        int prev = -1;
        int val = s[i].first, m = s[i].second;
        for(int j = 0; j < val; ++j) {
            for(int k = 0; k * val + j < V + 1; ++k) {
                nxt[k * val + j] = nxt[k * val + j] | (prev != -1);
                if(dp[k * val + j]) {
                    prev = k;
                }
                if(k - prev >= m) {
                    prev = -1;
                }
            }
        }
        dp = move(nxt);
    }

    ll res = 0;
    for(int i = 0; i < V + 1; ++i) {
        if(dp[i]) {
            ll a = sum + i;
            ll b = V - a;
            res = max(res, a * b - E);
        }
    }
    cout << res << endl;
}