Problem: Example

Input

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


Output

11

Solution (in CPP):

Solution:
#include<cstdio>
#include<vector>
#include<deque>
#include<map>
#include<cstdlib>
#include<algorithm>

using namespace std;

const int MN=100100;

vector<int> G[MN];
bool used[MN];
int root[MN],dep[MN];
int even[MN],odd[MN];
int N;

void dfs(int v,int p,int d,int r){
	used[v]=true;
	dep[v]=d;
	root[v]=r;
	if(d%2==0) even[r]++;
	else odd[r]++;
	
	for(int i=0;i<G[v].size();i++){
		int u=G[v][i];
		if(u==p) continue;
		if(used[u]){
			if((dep[v]-dep[u])%2==0){
				printf("-1\n");
				exit(0);
			}else continue;
		}
		dfs(u,v,d+1,r);
	}
}

int w[MN],v[MN],num[MN];
map<int,int> nums;
int K,n;

int dp[MN];

void solve(){
	for(int i=0;i<K;i++){
		for(int a=0;a<w[i];a++){
			deque<int> deqi,deqv;
			for(int j=0;j*w[i]+a<=n;j++){
				int val=dp[j*w[i]+a]-j*v[i];
				while(!deqi.empty()&&deqv.back()<=val){
					deqi.pop_back();
					deqv.pop_back();
				}
				deqi.push_back(j);
				deqv.push_back(val);
				dp[j*w[i]+a]=deqv.front()+j*v[i];
				if(deqi.front()==j-num[i]){
					deqi.pop_front();
					deqv.pop_front();
				}
			}
		}
	}
}

int main(){
	int E;
	scanf("%d%d",&N,&E);
	if(E==0){
		int a=N/2;
		int b=N-a;
		long long all=(long long)a*b;
		printf("%lld\n",all);
		return 0;
	}
	for(int i=0;i<E;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		u--;v--;
		G[v].push_back(u);
		G[u].push_back(v);
	}
	for(int i=0;i<N;i++){
		if(used[i]==false){
			dfs(i,-1,0,i);
		}
	}
	int S=0;
	for(int i=0;i<N;i++){
		if(root[i]==i){
			int d=max(odd[i]-even[i],even[i]-odd[i]);
			if(d!=0) nums[d]++;
			S+=d;
		}
	}
	if(nums.size()==0){
		int n=N/2;
		long long all=(long long)n*n;
		printf("%lld\n",all-E);
		return 0;
	}
	n=S/2;
	K=nums.size();
	map<int,int>::iterator it=nums.begin();
	int c=0;
	for(;it!=nums.end();it++){
		v[c]=it->first;
		w[c]=it->first;
		num[c++]=it->second;
	}
	solve();
	int a=0;
	for(int i=0;i<=n;i++) a=max(a,dp[i]);
//	int dif=S-2*dp[n];
	int dif=S-2*a;
	int x=(N-dif)/2;
	int y=x+dif;
	long long all=(long long)x*y;
	printf("%lld\n",all-E);
	return 0;
}