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>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define int long long
using namespace std;
typedef pair<int, int> P;

const int MAX_V = 100010;
vector<int> G[MAX_V];
int odd, even;
vector<P> d;
// 2部グラフ判定
struct BipartiteGraph{
    int n;    
    vector<int> color;
    BipartiteGraph(int _n){
        n = _n;
        color.resize(n, 0);
    }
    bool dfs(int v, int c){
        color[v] = c;
        if(c == 1) odd++;
        else even++;
        bool res = true;
        for(int i = 0; i < G[v].size(); i++){
            if(color[G[v][i]] == c) res &= false;
            if(color[G[v][i]] == 0) res &= dfs(G[v][i], -c);
        }
        return res;
    }
    bool isBipartiteGraph(){
        bool res = true;
        for(int i = 0; i < n; i++){
            if(color[i] == 0){
                odd = 0; even = 0;
                res &= dfs(i, 1);
                d.push_back({odd, even});
            }
        }
        return res;
    }
};

bitset<MAX_V> dp, nxt;

signed main(){
    long long n, m;
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int s, t;
        cin >> s >> t;
        s--; t--;
        G[s].push_back(t);
        G[t].push_back(s);
    }
    BipartiteGraph bg(n);
    bool f = bg.isBipartiteGraph();
    if(!f){
        cout << -1 << endl;
        return 0;
    }
    dp[0] = true;
    rep(i, 0, d.size()){
        nxt.reset();
        nxt = dp << d[i].first;
        nxt |= dp << d[i].second;
        dp = nxt;
    }
    int ans = 0;
    rep(i, 0, n + 1){
        if(dp[i]){
            int tmp = i * (n - i);
            ans = max(ans, tmp - m);
        }
    }
    cout << ans << endl;
}