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

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


// nums[i] := i 番目の連結成分の {左ノード数, 右ノード数}, 「dir = 1: 左、-1: 右」
using pint = pair<int,int>;
using Graph = vector<vector<int> >;

bool dfs(const Graph &G, int v, int vdir, pint &num, vector<int> &dir) {
    bool res = true;
    dir[v] = vdir;
    if (vdir == 1) ++num.first;
    else if (vdir == -1) ++num.second;
    for (auto nv : G[v]) {
        if (dir[nv] == 0) {
            if (!dfs(G, nv, -vdir, num, dir)) res = false;
        }
        else if (dir[nv] != -vdir) res = false;
    }
    return res;
}

bool isbipartite(const Graph &G, vector<pint> &nums) {
    bool res = true;
    int N = (int)G.size();
    vector<int> dir(N, 0);
    for (int v = 0; v < N; ++v) {
        if (dir[v] != 0) continue;
        pint num = {0, 0};
        if (!dfs(G, v, 1, num, dir)) res = false;
        nums.push_back(num);
    }
    return res;
}

const int INF = 1<<29;

int main() {
    int V, E; cin >> V >> E;
    Graph G(V);
    for (int i = 0; i < E; ++i) {
        int a, b; cin >> a >> b; --a, --b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    
    // 二部グラフ判定して、左ノード数と右ノード数の差分ごとに集計
    vector<pint> nums;
    if (!isbipartite(G, nums)) {
        cout << -1 << endl;
        return 0;
    }
    map<int,int> ma;
    for (auto p : nums) ma[abs(p.first - p.second)]++;
    
    // DP
    int geta = 0;
    vector<int> dp(V*2+10, INF);
    dp[0] = 0;
    for (auto it = ma.begin(); it != ma.end(); ++it) {
        int diff = it->first;
        geta += diff * it->second;
        for (int v = 0; v <= V*2; ++v) {
            if (dp[v] < INF) dp[v] = 0;
        }
        for (int v = 0; v <= V*2; ++v) {
            if (v + diff * 2 <= V*2 && dp[v] < it->second) chmin(dp[v + diff*2], dp[v] + 1);
        }
    }

    // 集計
    int diff = V;
    for (int v = 0; v <= V*2; ++v) {
        if (dp[v] < INF) diff = min(diff, abs(v-geta));
    }
    long long a = (V + diff)/2, b = (V - diff)/2;
    cout << a * b - E << endl;
}