Problem: Example

Input

8 5
1 2
6 5
6 4
1 3
4 7


Output

11

Solution (in CPP):

Solution:
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>g[110000];
vector<int>v;
int color[110000];
bool ok=true;
int B,W;
void dfs(int a,int b){
	color[a]=b;
	//printf("%d %d\n",a,b);
	if(b)B++;
	else W++;
	for(int i=0;i<g[a].size();i++){
		if(!~color[g[a][i]]){
			dfs(g[a][i],!b);
		}else if(color[g[a][i]]==b){
			ok=false;
		}
	}
}
int sg[310];
int dp[2][110000];
int dp2[110000];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<b;i++){
		int p,q;scanf("%d%d",&p,&q);p--;q--;
		g[p].push_back(q);
		g[q].push_back(p);
	}
	for(int i=0;i<a;i++)color[i]=-1;
	int now=0;
	for(int i=0;i<a;i++){
		if(!~color[i]){
			B=W=0;
			dfs(i,0);
			now+=min(B,W);
			if(max(B,W)-min(B,W)<300)sg[max(B,W)-min(B,W)]++;
			else v.push_back(max(B,W)-min(B,W));
		}
	}
	if(!ok){
		printf("-1\n");
		return 0;
	}
	for(int i=0;i<110000;i++)dp[0][i]=dp[1][i]=-1;
	dp[1][0]=0;
	for(int i=1;i<300;i++){
		int f=i%2;
		for(int j=0;j<110000;j++){
			if(~dp[f][j])dp[!f][j]=0;
			else dp[!f][j]=-1;
		}
		for(int j=0;j<110000;j++){
			if(j-i>=0&&~dp[!f][j-i]&&dp[!f][j-i]<sg[i]){
				if(!~dp[!f][j])dp[!f][j]=dp[!f][j-i]+1;
				else dp[!f][j]=min(dp[!f][j],dp[!f][j-i]+1);
			}
		}
	/*	if(i<5){
			for(int j=0;j<20;j++)printf("%d ",dp[!f][j]);
			printf("\n");
		}*/
	}
	for(int i=0;i<110000;i++)if(~dp[0][i])dp2[i]=1;
	for(int i=0;i<v.size();i++){
		for(int j=109999;j>=v[i];j--){
			dp2[j]|=dp2[j-v[i]];
		}
	}
	long long ret=0;
	for(int i=0;i<110000;i++){
		if(dp2[i]){
			ret=max(ret,(long long)(now+i)*(a-now-i)-b);
		}
	}
	printf("%lld\n",ret);
}