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 MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int n,m;
vector<int> G[100001];
int col[100001];
ll dp[2][901];
vector<P> p;
P po;

bool dfs(int v,int c){
	if(c==1){
		po.first++;
	}else{
		po.second++;
	}
	col[v]=c;
	for(int i=0;i<G[v].size();i++){
		if(col[G[v][i]]==0){
			if(!dfs(G[v][i],-c))return false;
		}else if(col[G[v][i]]==c){
			return false;
		}
	}
	return true;
}

int main(void){
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		a--;
		b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	for(int i=0;i<n;i++){
		if(col[i]==0){
			po=P(0,0);
			if(!dfs(i,1)){
				printf("-1\n");
				return 0;
			}
			p.push_back(po);
		}
	}
	dp[0][0]=1;
	int cur=0,nxt=1;
	for(int i=0;i<p.size();i++){
		for(int j=0;j<900;j++){
			for(int k=0;k<2;k++){
				int v=p[i].first;
				int dig=v/60;
				int diff=v%60;
				if(j+dig<900){
					ll va=dp[cur][j]&((1LL<<(60-diff))-1LL);
					dp[nxt][j+dig]|=va<<diff;
				}
				if(j+dig+1<900 && diff>0){
					dp[nxt][j+dig+1]|=dp[cur][j]>>(60-diff);
				}
				swap(p[i].first,p[i].second);
			}
		}
		swap(cur,nxt);
		memset(dp[nxt],0,sizeof(dp[nxt]));
	}
	int best=0;
	for(int i=0;i<900;i++){
		for(int j=0;j<60;j++){
			if(dp[cur][i]>>j & 1){
				int val=j+i*60;
				if(abs(n/2-val)<abs(n/2-best)){
					best=val;
				}
			}
		}
	}
	printf("%lld\n",(ll)best*(n-best)-m);
	return 0;
}