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;

bool dfs(long long node, long long c, long long& cnt_0, long long& cnt_1, vector<long long>& used, vector<vector<long long> >& adj){

    used[node] = c;
    long long next_c = (c + 1) % 2;
    if(c == 0) cnt_0++;
    else cnt_1++;

    for(auto next_node : adj[node]){
        if(used[next_node] == next_c) continue;
        else if(used[next_node] == c) return false;
        else{
            if(!dfs(next_node, next_c, cnt_0, cnt_1, used, adj)) return false;
        }
    }

    return true;
}


int main(){
    
    // 入力受け取り
    long long V, E; cin >> V >> E;
    vector<vector<long long> > adj(V);

    for(long long i = 0; i < E; i++){
        long long a, b; cin >> a >> b;
        a--; b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }



    //二部グラフ判定パート
    vector<long long> used(V, -1);     //-1 := 見訪問  0:= 白  1 := 黒
    map<long long, long long> M;
    long long sum = 0;
    for(long long i = 0; i < V; i++){
        if(used[i] == -1){

            long long cnt_0 = 0;
            long long cnt_1 = 0;
            if(!dfs(i, 0, cnt_0, cnt_1, used, adj)){
                cout << -1 << endl;
                return 0;
            }

            //cout << i + 1 << " " << cnt_0 << " " << cnt_1 << endl;
            sum += (long long)abs(cnt_0 - cnt_1);
            M[(long long)abs(cnt_0 - cnt_1)]++;
        }
    }



    //個数制限付き部分和問題

    long long n = (long long)M.size();

    //dp[i][j] := i番目までのものを使って j を作る最大の a[i]の残る個数 (作れない場合は -1)
    vector<vector<long long> > dp(2, vector<long long> (sum + 1, -1LL));
    dp[0][0] = 0;
    int now_i = 0;
    int next_i = 1;
    for(auto x : M){
        for(long long j = 0; j <= sum; j++){

            if(dp[now_i][j] != -1) dp[next_i][j] = x.second;
            else{
                if(j - x.first >= 0) dp[next_i][j] = max(-1LL, dp[next_i][j - x.first] - 1LL);
            }
            //cout << "dp[" << i << "][" << j << "] = " << dp[i][j] << endl;
        }
        swap(now_i, next_i);
    }

    long long ans = sum;
    for(long long j = 0; j <= sum; j++){

        //cout << "dp[" << i - 1 << "][" << j << "] = " << dp[i - 1][j] << endl;         
        if(dp[now_i][j] != -1) ans = min(ans, (long long)abs(sum - 2 * j));
    }

    cout << (V * V - ans * ans) / 4 - E << endl;
    return 0;
}