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 <bitset>
using namespace std;
vector<int> G[100010];
int col[100010];
void dfs(int s,int c){
    col[s] = c;
    for(int v:G[s]){
        if(col[v]==-1) dfs(v,1 - c);
    }
}

bool bip_ch(int v){
    int i;
    for(i=0;i<v;i++){
        col[i] = -1;
    }
    for(i=0;i<v;i++){
        if(col[i]==-1) dfs(i,0);
    }
    for(i=0;i<v;i++){
        for(int ver:G[i]){
            if(col[i]==col[ver]) return false;
        }
    }
    return true;
}

int par[100010],sz[100010],wh[100010];
void init(int n){
	for(int i=0;i<n;i++){
		par[i] = i; sz[i] = 1; wh[i] = col[i];
	}
}

int find(int x){
	if(par[x]==x) return x;
	return par[x] = find(par[x]);
}

void unite(int x, int y){
	x = find(x); y = find(y);
	if(x==y) return;
	if(sz[x]>sz[y]) swap(x,y);
	par[x] = y;
	sz[y] += sz[x]; wh[y] += wh[x];
}

bitset<100010> dp1,dp2;
int main(){
    long long i,j,n,m;
    cin >> n >> m;
    for(i=0;i<m;i++){
        int a,b; cin >> a >> b;
        a--; b--;
        G[a].push_back(b); G[b].push_back(a);
    }
    if(!bip_ch(n)){
        cout << -1 << endl;
        return 0;
    }
    init(n);
    for(i=0;i<n;i++){
        for(int v:G[i]){
            unite(v,i);
        }
    }
    dp1[0] = 1;
    for(i=0;i<n;i++){
        if(par[i]==i){
            dp2 = (dp1<<wh[i]);
            dp2 |= (dp1<<(sz[i] - wh[i]));
            dp1 = dp2;
        }
    }
    for(i=n/2;i>=0;i--){
        if(dp1[i]){
            cout << i*(n - i) - m << endl;
            return 0;
        }
    }
}