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,n) for(int i = 0; i < n; i++)
#define MAX_N 100000
#define INF 100000000
#define MOD 1000000007
#define RANK 1000000000
#define EPS 1e-10
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> IP;

struct UF{
	int par[MAX_N];
	int rank[MAX_N];
	int si[MAX_N];

	void init(int n){
		rep(i,n){
			par[i] = i;
			rank[i] = 0;
			si[i] = 1;
		}
	}

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

	void unite(int x, int y){
		x = find(x);
		y = find(y);
		if(x == y) return;
		
		if(rank[x] < rank[y]){
			par[x] = y;
			si[y] += si[x];
		} else{
			par[y] = x;
			if(rank[x] == rank[y]) rank[x]++;
			si[x] += si[y];
		}
	}

	bool same(int x, int y){
		return find(x) == find(y);
	}
} uf;

int v, ee;
vector<int> e[100000];
int val[100000];
bool dp[2][100001];

P dfs(int x, int now){
    P ret = P(0,0);
    val[x] = now;
    if(now) ret.second++;
    else ret.first++;
    rep(i,e[x].size()){
        if(val[e[x][i]] != 2 && val[e[x][i]] != (now^1)){
            return P(-1,-1);
        }
        if(val[e[x][i]] != 2) continue;
        P tmp = dfs(e[x][i],now^1);
        if(tmp.first == -1) return P(-1,-1);
        ret.first += tmp.first;
        ret.second += tmp.second;
    }
    return ret;
}

int main(){
    cin >> v >> ee;
    rep(i,v) val[i] = 2;
    uf.init(v);
    int ho = 0, ge = 1;
    dp[ho][0] = true;
    rep(i,ee){
        int a, b;
        cin >> a >> b;
        a--; b--;
        e[a].push_back(b);
        e[b].push_back(a);
        uf.unite(a,b);
    }
    rep(i,v){
        if(uf.find(i) != i) continue;
        P d = dfs(i,0);
        if(d.first == -1){
            cout << -1 << endl;
            return 0;
        }
        if(d.first > d.second) swap(d.first,d.second);
        //cout << d.first << " " << d.second << endl;
        memset(dp[ge],0,sizeof(dp[ge]));
        for(int j = v/2+1; j >= 0; j--){
            if(j >= d.first) dp[ge][j] |= dp[ho][j-d.first];
            else break;
            if(j >= d.second) dp[ge][j] |= dp[ho][j-d.second];
        }
        swap(ho,ge);
    }
    ll ans = 0;
    for(ll i = 0; i <= v; i++){
        if(dp[ho][i]) ans = max(ans,i*(v-i));
    }
    cout << ans-ee << endl;
}