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;
#define FOR(i,k,n) for(int i = (int)(k); i < (int)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1000000007;
const int INF = MOD + 1;
const ld EPS = 1e-12;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }

/*--------------------template--------------------*/

typedef int Weight;
struct Edge
{
	int from, to; Weight cost;
	bool operator < (const Edge& e) const { return cost < e.cost; }
	bool operator > (const Edge& e) const { return cost > e.cost; }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;
void add_edge(Graph &g, int from, int to, Weight cost)
{
	g[from].push_back(Edge{ from, to, cost });
}


int main()
{
	cin.sync_with_stdio(false); cout << fixed << setprecision(10);
	int n, m;
	cin >> n >> m;
	Graph g(n);
	map<int, int> mp;
	REP(i, m)
	{
		int a, b; cin >> a >> b;
		a--; b--;
		add_edge(g, a, b, 0);
		add_edge(g, b, a, 0);
	}
	vi color(n, -1);
	REP(i, n)
	{
		if (color[i] >= 0) continue;
		int b = 1, w = 0;
		color[i] = 0;
		queue<int> que;
		que.push(i);
		while (!que.empty())
		{
			int t = que.front();
			que.pop();
			for (auto e : g[t])
			{
				int nx = e.to;
				if (color[nx] >= 0)
				{
					if (color[nx] == color[t])
					{
						cout << -1 << endl;
						return 0;
					}
					else continue;
				}
				color[nx] = 1 - color[t];
				if (color[nx]) w++;
				else b++;
				que.push(nx);
			}
		}
		mp[abs(b - w)]++;
	}
	vi v;
	int sum = 0;
	for (auto i : mp)
	{
		sum += i.first*i.second;
		int t = 1;
		int cnt = 0;
		while (1)
		{
			if (cnt + t <= i.second)
			{
				cnt += t;
				v.push_back(i.first*t);
				t *= 2;
			}
			else
			{
				v.push_back(i.first*(i.second - cnt));
				break;
			}
		}
	}
	vector<bool> dp(n + 1, false);
	dp[0] = true;
	REP(i, v.size())
	{
		for (int j = n; j >= 0; j--)
		{
			if (j - v[i] < 0) break;
			if (!dp[j - v[i]]) continue;
			dp[j] = true;
		}
	}
	ll ans = 0;
	REP(i, dp.size())
	{
		if (dp[i])
		{
			ll dif = abs(i - (sum - i));
			ll tmp = (n + dif) / 2 * (n - dif) / 2 - m;
			chmax(ans, tmp);
		}
	}
	cout << ans << endl;
	return 0;
}