Problem: Example

Input

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


Output

11

Solution (in CPP):

Solution:
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define SORT(x) sort((x).begin(),(x).end())
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define repn(i,a,n) for(int (i)=(a);(i)<(int)(n);(i)++)
#define EQ(a,b) (abs((a)-(b))<eps)
int V,E;
vector<int> g[100100];
bool used[100100];
int col[100100];
bool flag=false;
int cnt[3];
int dp[100100];
int num[600];
map<int,int> m;
void dfs(int v,int c)
{
	used[v]=true;
	col[v] = c;
	cnt[c+1]++;
	for(int i=0;i<g[v].size();i++)
	{
		if(used[g[v][i]]&&col[g[v][i]]==col[v])flag=true;
		if(!used[g[v][i]])dfs(g[v][i],-c);
	}
}
int main()
{
	scanf("%d %d",&V,&E);
	for(int i=0;i<E;i++)
	{
		int a,b;
		scanf("%d %d",&a,&b);
		a--;b--;
		g[a].pb(b);
		g[b].pb(a);
	}
	vector<int> v;
	ll base = 0ll;
	ll sum = 0ll;
	for(int i=0;i<V;i++)
	{
		cnt[0]=0,cnt[2]=0;
		if(!used[i])
		{
			dfs(i,1);
			if(cnt[0]>cnt[2])swap(cnt[0],cnt[2]);
			base += cnt[0];
			sum += cnt[2]-cnt[0];
			v.pb(cnt[2]-cnt[0]);
			m[cnt[2]-cnt[0]]++;
		}
	}
	if(flag)
	{
		printf("-1\n");
		return 0;
	}
	sort(all(v));
	v.erase(unique(all(v)),v.end());
	int N = v.size();
	//cout << base << ' ' << sum << endl;
	for(int i=0;i<N;i++)num[i]=m[v[i]];
	//for(int i=0;i<N;i++)printf("%d %d\n",v[i],num[i]);
	memset(dp,-1,sizeof(dp));
	dp[0]=0;
	for(int i=0;i<N;i++)
	{
		for(int j=0;j<=V;j++)
		{
			if(dp[j]>=0)dp[j]=num[i];
			else if(j<v[i]||dp[j-v[i]]<=0)dp[j]=-1;
			else dp[j] = dp[j-v[i]]-1;
		}
	}
	ll ans = 0ll;
	for(int i=0;i<=V;i++)if(dp[i]>=0)ans = max(ans,(base+i)*(base+sum-i));
	printf("%lld\n",ans-E);
	return 0;
}