Problem: Example

Input

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


Output

11

Solution (in CPP):

Solution:
#include<iostream>
#include<sstream>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<complex>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cassert>

#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define mp make_pair
#define pb push_back
#define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define dbg(x) cerr<<__LINE__<<": "<<#x<<" = "<<(x)<<endl

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
const int inf = (int)1e9;
const double INF = 1e12, EPS = 1e-9;

const int MX = 200001;
int n, m, v[100000], sum[MX];
bool dp[2][MX];
vector<vi> e;

bool rec(int c, int col, int &a, int &b){
	a++;
	v[c] = col;
	rep(i, e[c].size()){
		if(v[e[c][i]]){
			if(v[e[c][i]] == col) return 0;
		}
		else rec(e[c][i], -col, b, a);
	}
	return 1;
}

int main(){
	scanf("%d%d", &n, &m);
	e.resize(n);
	rep(i, m){
		int a, b;
		scanf("%d%d", &a, &b);
		a--; b--;
		e[a].pb(b);
		e[b].pb(a);
	}
	map<int, int> s;
	rep(i, n) if(!v[i]){
		int a = 0, b = 0;
		if(!rec(i, 1, a, b)){
			cout << -1 << endl;
			return 0;
		}
		s[abs(a - b)]++;
	}
	
	//each(i, s) cerr<<i->first<<" "<<i->second<<endl;
	const int GETA = 100000;
	dp[0][GETA] = 1;
	int cur = 0, next = 1;
	each(i, s){
		memset(dp[next], 0, sizeof(dp[next]));
		memset(sum, 0, sizeof(sum));
		
		int a = i->first, b = i->second;
		if(a == 0) continue;
		
		rep(j, MX) if(dp[cur][j]){
			int t = (MX - 1 - j) / a;
			if(t % 2 != b % 2) t--;
			t = min(t, b);
			if(t >= 0 && j + a * (t + 2) < MX) sum[j + a * (t + 2)]--;
			
			t = j / a;
			if(t % 2 != b % 2) t--;
			t = min(t, b);
			if(t >= 0) sum[j - a * t]++;
		}
		rep(j, 2 * a){
			int l = 0;
			for(int k = j; k < MX; k += 2 * a){
				l += sum[k];
				if(l) dp[next][k] = 1;
			}
		}
		swap(cur, next);
	}
	ll mx = 0;
	rep(i, MX) if(dp[cur][i]){
		mx = max(mx, (ll)((n + i - GETA) / 2) * ((n - i + GETA) / 2));
	}
	cout << mx - m << endl;
	return 0;
}