Problem: Example

Input

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


Output

11

Solution (in CPP):

Solution:
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
#include <functional>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define rep1(i,n) for(int i=1;i<=(n);++i)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl;
vector<int> G[100000];
bool visited[100000][2],vis[100000];
int cnt=0,a[100000],b[100000];
typedef vector<int> vi;
vector<vi> group(100000);
void dfs(int v,int x){
	visited[v][x]=true;
	rep(i,G[v].size()){
		if(visited[G[v][i]][1-x]) continue;
		dfs(G[v][i],1-x);
	}
}
void dfs2(int v){
	group[cnt].pb(v);
	vis[v]=true;
	rep(i,G[v].size()){
		if(vis[G[v][i]]) continue;
		dfs2(G[v][i]);
	}
}
int cnta[100001];
vector<int> vca,vcm;
int dp[100001];
int main(){
	int V,E;
	cin>>V>>E;
	rep(i,E){
		int a,b;
		scanf("%d%d",&a,&b);
		G[a-1].pb(b-1);
		G[b-1].pb(a-1);
	}
	rep(i,V) if(!(visited[i][0]||visited[i][1])) dfs(i,0);
	rep(i,V) if(visited[i][0]&&visited[i][1]){
		printf("-1\n");
		return 0;
	}
	rep(i,V) if(!vis[i]) dfs2(i),cnt++;
	int ssum=0;
	rep(i,cnt){
		rep(j,group[i].size()){
			if(visited[group[i][j]][0]) a[i]++;
			else b[i]++;
		}
		if(a[i]<b[i]) swap(a[i],b[i]);
		ssum+=b[i];
//		cout<<a[i]<<" "<<b[i]<<endl;
	}
	rep(i,cnt) cnta[a[i]-b[i]]++;
	rep1(i,100000) if(cnta[i]>0){
		vca.pb(i);
		vcm.pb(cnta[i]);
	}
	int n=vca.size();
	rep(i,100001) dp[i]=-1;
	dp[0]=0;
	rep(i,n){
		rep(j,100001){
			if(dp[j]>=0){
				dp[j]=vcm[i];
			}else if(j<vca[i]||dp[j-vca[i]]<=0){
				dp[j]=-1;
			}else{
				dp[j]=dp[j-vca[i]]-1;
			}
		}
	}
	long long ans=0;
	rep(i,100001) if(dp[i]>=0){
		long long si=ssum+i;
		ans=max(ans,si*(V-si));
	}
	cout<<ans-E<<endl;
}