Problem: Example

Input

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


Output

11

Solution (in CPP):

Solution:
#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<algorithm>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

typedef vector< vector<int> > graph;

// G を連結成分に分解する
vector<graph> decomp(const graph &G){
	int n=G.size();
	vector<graph> cc;
	map<int,int> f; // G における頂点番号 -> 連結成分の番号
	map<int,int> g; // G における頂点番号 -> 連結成分における頂点番号

	int c_id=0;
	vector<bool> vis(n);
	rep(u,n) if(!vis[u]) {
		vis[u]=true;

		vector<int> tmp; // 今調べている連結成分
		queue<int> Q; Q.push(u);
		while(!Q.empty()){
			int v=Q.front(); Q.pop();
			tmp.push_back(v);
			rep(i,G[v].size()){
				int w=G[v][i];
				if(!vis[w]) vis[w]=true, Q.push(w);
			}
		}

		cc.push_back(graph(tmp.size()));
		rep(i,tmp.size()){
			f[tmp[i]]=c_id;
			g[tmp[i]]=i;
		}
		c_id++;
	}

	rep(u,n) rep(i,G[u].size()) {
		int v=G[u][i];
		cc[f[u]][g[u]].push_back(g[v]);
	}

	return cc;
}

bool is_bipartite(const graph &G,int &L_res,int &R_res){
	int n=G.size();
	int L=0,R=0;
	vector<int> color(n,-1);

	rep(u,n) if(color[u]==-1) {
		color[u]=2*(L++);

		queue<int> Q; Q.push(u);
		while(!Q.empty()){
			int v=Q.front(); Q.pop();

			rep(i,G[v].size()){
				int w=G[v][i];
				if(color[w]%2==color[v]%2) return false;
				if(color[w]==-1){
					if(color[v]%2==0) color[w]=2*(R++)+1;
					else              color[w]=2*(L++);
					Q.push(w);
				}
			}
		}
	}

	L_res=L;
	R_res=R;
	return true;
}

vector<int> unify_ones(const vector<int> &a){
	vector<int> res;
	int one=0;
	rep(i,a.size()){
		if(a[i]==1) one++;
		else        res.push_back(a[i]);
	}

	int two=1;
	while(one>0){
		res.push_back(min(two,one));
		one-=min(two,one);
		two<<=1;
	}
	return res;
}

int main(){
	int n,m; scanf("%d%d",&n,&m);
	graph G(n);
	rep(i,m){
		int u,v; scanf("%d%d",&u,&v); u--; v--;
		G[u].push_back(v);
		G[v].push_back(u);
	}

	vector<graph> cc=decomp(G);

	vector<int> L(cc.size()),R(cc.size()); // 二部グラフの左右の頂点数
	rep(i,cc.size()){
		if(!is_bipartite(cc[i],L[i],R[i])) return puts("-1"),0;
		if(L[i]>R[i]) swap(L[i],R[i]);
	}

	int L_sum=0;
	vector<int> add(cc.size());
	rep(i,cc.size()){
		L_sum+=L[i];
		add[i]=R[i]-L[i];
	}

	// add[i]==1 がたくさんあると部分和問題を解くのに時間がかかりすぎるので, 適当にまとめる ( 個数制約があるナップザックと同じ tips )
	add=unify_ones(add);

	// knapsack DP
	int N=L_sum; // 最適な左の頂点数 ( n/2 以下で最大になるよう振り分ける )
	vector<bool> dp(n+1); dp[0]=true;
	rep(i,add.size()){
		for(int j=n/2-L_sum-add[i];j>=0;j--){
			if(dp[j]){
				dp[j+add[i]]=true;
				if(abs(L_sum+j+add[i]-n/2.0)<abs(N-n/2.0)) N=L_sum+j+add[i];
			}
		}
	}

	printf("%u\n",N*(n-N)-m);

	return 0;
}