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;

struct UnionFind
{
  vector< int > data;

  UnionFind(int sz)
  {
    data.assign(sz, -1);
  }

  void unite(int x, int y)
  {
    x = find(x), y = find(y);
    if(x != y) {
      if(data[x] > data[y]) swap(x, y);
      data[x] += data[y];
      data[y] = x;
    }
  }

  int find(int k)
  {
    if(data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }

  int size(int k)
  {
    return (-data[find(k)]);
  }
};

vector< int > g[100000];
bool v[100000];
int black, white;

void dfs(int idx, bool pre)
{
  if(v[idx]++) return;
  if(pre) ++black;
  else ++white;
  for(auto &to : g[idx]) dfs(to, 1 - pre);
}

int main()
{
  int V, E;
  cin >> V >> E;
  UnionFind tree(V + V);
  for(int i = 0; i < E; i++) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    g[a].push_back(b);
    g[b].push_back(a);
    tree.unite(a + V, b);
    tree.unite(a, b + V);
  }

  for(int i = 0; i < V; i++) {
    if(tree.find(i) == tree.find(i + V)) {
      cout << -1 << endl;
      return (0);
    }
  }

  bitset< 50001 > dp;
  dp[0] = 1;

  for(int i = 0; i < V; i++) {
    if(v[i]) continue;
    black = white = 0;
    dfs(i, 0);
    dp = (dp << black) | (dp << white);
  }

  long long ret = 0;
  for(int i = 0; i <= V / 2; i++) {
    if(dp[i]) ret = max(ret, 1LL * i * (V - i));
  }
  cout << ret - E << endl;
}