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 vector<int> vi;
typedef long long ll;

#define range(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  range(i,0,n)
#define clr(a,b) memset((a), (b) ,sizeof(a))

const double eps = 1e-10;
const double pi  = acos(-1.0);
const ll INF =1LL << 62;
const int inf =1 << 29;

const int vmax=100010;
vi graph[vmax];
int color[vmax];
ll black=0LL,white=0LL;

bool dfs(int v,int c){
	color[v]=c;
	if(c==1) black++;
	if(c==-1) white++;
	for(auto &v2:graph[v]){
		if(color[v2]==0&&dfs(v2,-c)==false) return false;
		if(color[v2]==color[v]) return false;
	}
	return true;
}

ll base=0LL;
ll num[100010];
ll dp[100010];

ll calc(ll v){
	clr(dp,-1);
	dp[0]=0LL;

	rep(i,v+1){
		if(num[i]==0) continue;
		rep(j,v+1){
			if(dp[j]>=0)
				dp[j]=num[i];
			else if(j<i || dp[j-i]<=0)
				dp[j]=-1;
			else
				dp[j]=dp[j-i]-1;
		}
	}
	ll all=0LL;
	rep(i,v+1){
		if(dp[i]>=0){
			ll white=base+i;
			ll black=v-white;
			all=max(all,white*black);
		}
	}
	return all;
}

int main(void){
	ll v,e;
	cin >> v >> e;
	rep(i,e){
		int a,b;
		cin >> a >> b;
		graph[a-1].push_back(b-1);
		graph[b-1].push_back(a-1);
	}

	bool ok=true;;
	rep(i,v){
		if(color[i]!=0) continue;
		int c=1;
		if(dfs(i,c)==false) ok=false;
		base+=min(black,white);
		num[max(black,white)-min(black,white)]++;
		black=0,white=0;
	}

	// ?????°??¶???????????¨????????????????§£???
	ll all=calc(v);
	if(ok)
		cout << all-e << endl;
	else
		cout << -1 << endl;
	return 0;
}