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;

const int M = 1000000007;

int dfs(int p, vector<vector<int>>& edge, vector<int>& col) {
    int ret = (col[p] ? 1 : -1);
    for (int i : edge[p]) {
        if (col[i] == col[p])
            return M;
        if (col[i] == 1 - col[p])
            continue;

        col[i] = col[p] ^ 1;
        int t = dfs(i, edge, col);
        if (t == M)
            return M;

        ret += t;
    }
    return ret;
}

int main() {
    int v, e;
    cin >> v >> e;
    vector<vector<int>> edge(v);
    for (int i = 0; i < e; ++i) {
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    vector<int> col(v, -1);
    vector<int> pm;
    int sum = 0, c1 = 0;
    for (int i = 0; i < v; ++i) {
        if (col[i] == -1) {
            col[i] = 0;
            int t = dfs(i, edge, col);
            if (t == M) {
                cout << "-1\n";
                return 0;
            }
            if (t < 0) t = -t;
            if (t == 1) ++c1;
            sum += t;
            if (t > 0) pm.push_back(t);
        }
    }
    if (c1 >= sum / 2) {
        long long a = v / 2;
        long long b = v - a;
        cout << (a * b - e) << "\n";
        return 0;
    }
    vector<int> dp(sum + 1, 0);
    dp[0] = 1;
    for (int i : pm) {
        for (int j = sum; j >= i; --j) {
            dp[j] |= dp[j - i];
        }
    }
    long long ma = 0;
    long long vv = (v - sum) / 2;
    for (int i = 0; i <= sum; ++i) {
        if (dp[i]) {
            ma = max(ma, (vv + i) * (vv + sum - i));
        }
    }
    cout << (ma - e) << "\n";
    return 0;
}