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>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 100000

ll V,E;
int color[NUM];
ll num[2];
bool dp[2][NUM];
vector<int> G[NUM];

//2部グラフか判定する(2色で全連結成分を塗れるか)
bool dfs(int node_id,int which){

	color[node_id] = which;
	num[which]++;

	for(int i = 0; i < G[node_id].size(); i++){
		//隣接している頂点が同じ色ならfalse
		if(color[G[node_id][i]] == which)return false;
		//隣接している頂点がまだ塗られていないなら反対色で塗る
		if(color[G[node_id][i]] == -1 && dfs(G[node_id][i],1-which) == false)return false;
	}

	return true; //全ての頂点を塗れたらtrue
}


int main(){

	scanf("%lld %lld",&V,&E);

	for(ll i = 0; i < V; i++){
		color[i] = -1;
	}

	int from,to;
	for(ll loop = 0; loop < E; loop++){
		scanf("%d %d",&from,&to);
		from--;
		to--;
		G[from].push_back(to);
		G[to].push_back(from);
	}

	map<int,int> MAP; //MAP[差] = 差の個数
	ll base_num = 0;

	for(int i = 0; i < V; i++){
		if(color[i] != -1)continue;

		num[0] = 0;
		num[1] = 0;

		if(!dfs(i,0)){ //2部グラフでない
			printf("-1\n");
			return 0;
		}

		MAP[max(num[0],num[1])-min(num[0],num[1])]++;
		base_num += min(num[0],num[1]);
	}

	//任意の個数を作れるかを計算する
	int CURRENT = 0,NEXT = 0;
	for(int i = 0; i < NUM; i++){
		dp[CURRENT][i] = false;
		dp[NEXT][i] = false;
	}



	int add,count,num,mult;

	dp[CURRENT][0] = true;
	dp[NEXT][0] = true;

	for(auto at: MAP){

		add = at.first; //差分
		count = at.second; //add分の差分を反映できる数

		//ダブリングナップザック
		num = count;
		for(int k = 1; num > 0; k *= 2){
			mult = min(k,num);
			for(int diff = NUM-1; diff-add*mult >= 0; diff--){
				if(dp[CURRENT][diff-add*mult] == false)continue;
				dp[NEXT][diff] = true;
			}
			num -= mult;
		}

		swap(CURRENT,NEXT);
	}

	ll ans = 0;
	for(int i = 1; i < NUM; i++){
		if(dp[CURRENT][i]){
			ans = max(ans,(base_num+i)*(V-(base_num+i)));
		}
	}

	printf("%lld\n",ans-E);

	return 0;
}