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;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<ll ,P> P3;
const ll MOD = ll(1e9+7);
const int IINF = INT_MAX;
const ll LLINF = LLONG_MAX;
const int MAX_N = int(1e5 + 5);
const double EPS = 1e-6;
const int di[] = {0, 1, 0, -1}, dj[] = {1, 0, -1, 0};
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define SORT(v) sort((v).begin(), (v).end())
#define ALL(v) (v).begin(), (v).end()

int v, e, used[MAX_N], cnt[2]{}, dif[MAX_N];
vector<vector<int> > g;
bitset<MAX_N*2> dp;

bool dfs(int i, int c){
    used[i] = c;
    cnt[c]++;
    bool res = true;
    for(auto to : g[i]){
        if(used[to] < 0){
            res &= dfs(to,c^1);
        }
        else{
            res &= used[to] != c;
        }
    }
    return res;
}

int main() {
    cin >> v >> e;
    g.resize(v);
    REP(i,e){
        int a, b;
        cin >> a >> b;
        a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    // 二部グラフ判定
    bool ok = true;
    fill(used,used+v,-1);
    REP(i,v){
        if(used[i]<0){
            ok &= dfs(i,0);
            dif[abs(cnt[0]-cnt[1])]++;
            cnt[0] = cnt[1] = 0;
        }
    }
    if(ok){
        dp.set(v);  // 差分を調整してある数を作れるか
        vector<int> ls;
        for(int i=1;i<v;i++){  // 差分の種類はsqrt(V)程度なので圧縮できる
            int m=1;
            while(dif[i]>=m){
                ls.push_back(i*m);
                dif[i] -= m;
                m*=2;
            }
            if(dif[i]>0) ls.push_back(i*dif[i]);
        }
        for(auto i : ls){
            dp = dp<<i | dp>>i;
        }
        ll ans = 0;
        REP(i,v){
            if(dp[i+v]) ans = max(ans,ll(v-i)/2*ll((v-i)/2+i));
        }
        cout << ans - e << endl;
    }
    else{
        cout << -1 << endl;
    }
    return 0;
}