Problem: Example

Input

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


Output

11

Solution (in CPP):

Solution:
#include <iostream>
#include <bitset>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <cmath>
using namespace std;
typedef long long i64;
typedef long double ld;
typedef pair<i64,i64> P;
#define rep(i,s,e) for(int i = (s);i <= (e);i++)

int v;
int e;

vector<vector<int>> edges(101010,vector<int>());
vector<int> vis(101010,-1);

vector<int> vec;

int c(int k){
	priority_queue<int> que;
	que.push(k);
	for(int a : vec){
		que.push(a);
	}
	while(que.size() >= 2){
		int t1 = que.top();
		que.pop();
		int t2 = que.top();
		que.pop();
		que.push(t1 - t2);
	}
	return que.top();
}

int binary(){
	for(int i = 0;i <= v;i++){
		if(c(i) == 0){
			return i;
		}
	}
	return -1;
}


P bfs(int s){
	queue<P> que;
	que.emplace(s,0);
	vis[s] =  0;
	P res = {0,0};
	while(!que.empty()){
		int v = que.front().first;
		int d= que.front().second;
		que.pop();
		if(d % 2 == 0) res.first++;
		else res.second++;

		for(auto& to : edges[v]){
			if(vis[to] == -1){
				vis[to] = (d + 1) % 2;
				que.emplace(to,vis[to]);
			}
			else if((vis[to] - vis[v] + 1) % 2 != 0){
				return {-1,-1};
			}
		}
	}
	return res;
}

int main(){
	cin >> v >> e;
	for(int i = 0;i < e;i++){
		int a,b;
		cin >> a >> b;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}
	bitset<101010> bit(1);
	for(int i = 1;i <= v;i++){
		if(vis[i] == -1){
			auto p = bfs(i);
			if(p.first == -1){
				cout << -1 << endl;
				return 0;
			}
			bit = (bit << p.first) | (bit << p.second);
		}
	}

	i64 res = 0;
	for(i64 i = 0;i < v;i++){
		if(bit[i])res = max(res, i * (v - i) - e);
	}

	cout << res << endl;
}