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;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x, n) for(int i = x; i <= n; i++)
#define rep3(i, x, n) for(int i = x; i >= n; i--)
#define elif else if
#define sp(x) fixed << setprecision(x)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const int inf = (1<<30)-1;
const ll INF = (1LL<<60)-1;
const ld EPS = 1e-10;
template<typename T> bool chmax(T &x, const T &y) {return (x < y)? (x = y, true) : false;};
template<typename T> bool chmin(T &x, const T &y) {return (x > y)? (x = y, true) : false;};

const int MAX_V = 100000;
vector<int> es[MAX_V];
vector<int> c(MAX_V, -1);
ll cnt[] = {0, 0};
bool flag = false;

void dfs(int now, int col){
    cnt[c[now] = col]++;
    for(auto &e: es[now]){
        if(c[e] == -1) dfs(e, col^1);
        if(c[e] == col) flag = true;
    }
}

int main(){
    ll V, E;
    cin >> V >> E;
    rep(i, E){
        int u, v; cin >> u >> v; u--, v--;
        es[u].pb(v), es[v].pb(u);
    }
    ll base = 0;
    bitset<MAX_V+1> bs;
    bs.set(0);
    rep(i, V){
        if(c[i] != -1) continue;
        dfs(i, 0);
        if(cnt[0] < cnt[1]) swap(cnt[0], cnt[1]);
        base += cnt[1], bs |= (bs << (cnt[0]-cnt[1]));
        cnt[0] = cnt[1] = 0;
    }
    if(flag) {cout << -1 << endl; return 0;}
    ll ans = E;
    rep(i, V){
        if(!bs[i]) continue;
        ll x = base+i;
        chmax(ans, x*(V-x));
    }
    cout << ans-E << endl;
}