Problem: Example

Input

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


Output

11

Solution (in CPP):

Solution:
#include <bits/stdc++.h>

using namespace std;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
template<class T> inline T sqr(T x) {return x*x;}

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;

#define all(a)  (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define pb push_back
#define mp make_pair
#define each(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define exist(s,e) ((s).find(e)!=(s).end())
#define range(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  range(i,0,n)
#define clr(a,b) memset((a), (b) ,sizeof(a))
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

const double eps = 1e-10;
const double pi  = acos(-1.0);
const ll INF =1LL << 62;
const int inf =1 << 29;

const int vmax=100010;
vi graph[vmax];
int color[vmax];
ll black=0LL,white=0LL;

bool dfs(int v,int c){
	color[v]=c;
	if(c==1) black++;
	if(c==-1) white++;
	for(auto &v2:graph[v]){
		if(color[v2]==0&&dfs(v2,-c)==false) return false;
		if(color[v2]==color[v]) return false;
	}
	return true;
}

ll base=0LL;
ll num[100010];
ll dp[100010];

ll calc(ll v){
	clr(dp,-1);
	dp[0]=0LL;

	rep(i,v+1){
		if(num[i]==0) continue;
		rep(j,v+1){
			if(dp[j]>=0)
				dp[j]=num[i];
			else if(j<i || dp[j-i]<=0)
				dp[j]=-1;
			else
				dp[j]=dp[j-i]-1;
		}
	}
	ll all=0LL;
	rep(i,v+1){
		if(dp[i]>=0){
			ll white=base+i;
			ll black=v-white;
			all=max(all,white*black);
		}
	}
	return all;
}

int main(void){
	ll v,e;
	cin >> v >> e;
	rep(i,e){
		int a,b;
		cin >> a >> b;
		graph[a-1].pb(b-1);
		graph[b-1].pb(a-1);
	}

	bool ok=true;;
	rep(i,v){
		if(color[i]!=0) continue;
		int c=1;
		if(dfs(i,c)==false) ok=false;
		base+=min(black,white);
		num[max(black,white)-min(black,white)]++;
		black=0,white=0;
	}

	ll all=calc(v);
	if(ok)
		cout << all-e << endl;
	else
		cout << -1 << endl;
	return 0;
}