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 <algorithm>
#include <map>
using namespace std;
typedef long long int lli;

bool dfs_coloring(int v, int c, vector<int> &num_c, vector<int> &color, vector<vector<int>> &g){
    if(color[v] != -1) return color[v]==c;
    color[v] = c;
    num_c[c]++;
    for(int next: g[v]){
        bool ret = dfs_coloring(next, 1-c, num_c, color, g);
        if(!ret) return false;
    }
    return true;
}
vector<vector<int>> bipertite_color_count(vector<vector<int>> &g){
    int n = g.size();
    vector<int> color(n, -1);
    vector<vector<int>> res;
    for(int i=0; i<n; i++){
        if(color[i] != -1) continue;
        vector<int> num_color{0, 0};
        bool ret = dfs_coloring(i, 0, num_color, color, g);
        if(!ret) return {};
        res.push_back(num_color);
    }
    return res;
}

int main(){
    int n,m;
    cin >> n >> m;
    vector<vector<int>> adj(n);
    for(int i=0; i<m; i++){
        int a,b;
        cin >> a >> b;
        a--; b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    auto ret = bipertite_color_count(adj);
    if(ret.empty()){
        cout << -1 << endl;
        return 0;
    }

    map<int, int> w_pre;
    int base = 0;
    for(auto v: ret){
        if(v[0] != v[1]){
            w_pre[abs(v[0]-v[1])]++;
        }
        base += min(v[0], v[1]);
    }
    int ulim = n-2*base;
    vector<int> w;
    for(auto p: w_pre){
        int num = 1;
        while(p.second >= num){
            w.push_back(p.first * num);
            p.second -= num;
            num *= 2;
        }
        if(p.second > 0){
            w.push_back(p.first * p.second);
        }
    } 
    vector<bool> dp(ulim+1, false);
    dp[0] = true;
    for(int t: w){
        for(int i=ulim; i>=0; i--){
            if(dp[i] and i+t <= ulim){
                dp[i+t] = true;
            }
        }
    }
    lli ans = 0;
    for(int i=0; i<=ulim; i++){
        if(!dp[i]) continue;
        ans = max(ans, 1LL*(base+i)*(base+ulim-i)-m);
    }
    cout << ans << endl;
    return 0;
}