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;
using ll=long long;
using ld=long double;
using P=pair<ll,ll>;
#define MOD 1000000007ll
#define INF 1000000000ll
#define EPS 1e-10
#define FOR(i,n,m) for(ll i=n;i<(ll)m;i++)
#define REP(i,n) FOR(i,0,n)
#define DUMP(a) REP(d,a.size()){cout<<a[d];if(d!=a.size()-1)cout<<" ";else cout<<endl;}
#define ALL(v) v.begin(),v.end()
#define UNIQUE(v) sort(ALL(v));v.erase(unique(ALL(v)),v.end());
#define pb push_back

ll v, e;
vector<vector<ll>> g;
vector<ll> used;

bool dfs(ll p, ll col, P &cnt) {
	used[p] = col;
	if(col == 0) cnt.first++;
	else cnt.second++;
	bool ret = true;
	REP(i,g[p].size()) {
		if(used[g[p][i]] != -1) {
			if(used[g[p][i]] == col) ret = false;
			continue;
		}
		ret = ret & dfs(g[p][i], !col, cnt);
	}
	return ret;
}

ll solve() {
	used.assign(v, -1);
	bitset<100010> dp(0);
	dp[0] = 1;
	REP(i,v) {
		if(used[i] != -1) continue;
		P cnt = P(0, 0);
		if(!dfs(i, 0, cnt)) return -1;
		dp = (dp << cnt.first) | (dp << cnt.second);
	}
	ll ans = 0;
	REP(i,100010) if(dp[i]) {
		ans = max(ans, i * (v - i) - e);
	}
	return ans;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> v >> e;
	g.resize(v);
	REP(i,e) {
		ll a, b;
		cin >> a >> b;
		a--; b--;
		g[a].pb(b);
		g[b].pb(a);
	}
	cout << solve() << endl;
	return 0;
}