Problem: Example

Input

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


Output

11

Solution (in CPP):

Solution:
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define rep(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
#define mad(a,b) a=(a+b)%mod
#define N 100010
ll n,m;
vector<ll> g[N];
ll col[N],cnt[2];
bool dfs(ll x,ll c){
	if(~col[x]){
		return c==col[x];
	}
	col[x]=c;
	cnt[c]++;
	for(auto y:g[x]){
		if(!dfs(y,c^1))return 0;
	}
	return 1;
}
ll val[N],dp[N],dq[N];
int main(){
	cin>>n>>m;
	rep(i,m){
		ll a,b; cin>>a>>b;
		a--,b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	rep(i,N)val[i]=0;
	rep(i,n)col[i]=-1;
	bool ok=1;
	ll base=0;
	rep(i,n){
		if(col[i]==-1){
			rep(k,2)cnt[k]=0;
			if(!dfs(i,0))ok=0;
			if(cnt[0]>cnt[1])swap(cnt[0],cnt[1]);
			base+=cnt[0];
			val[cnt[1]-cnt[0]]++;
		}
	}
	rep(i,N)dp[i]=0; dp[0]=1;
	for(ll d=1;d<N;d++)if(val[d]>0){
		rep(i,N)dq[i]=(dp[i]>0);
		rep(i,N){
			if(i-d>=0){
				dp[i]=dp[i-d]+dq[i];
				ll id=i-d*(val[d]+1);
				if(id>=0)dp[i]-=dq[id];
			}
			else{
				dp[i]=dq[i];
			}
		}
	}
	ll ans=0;
	rep(i,N)if(dp[i]>0){
		ll x=i+base;
		chmax(ans,x*(n-x)-m);
	}
	if(ok==0)ans=-1;
	cout<<ans<<endl;
}