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;

#ifdef LOCAL
#include "debug.h"
#else
#define DEBUG(...)
#endif

struct dsu {
  int cc;
  vector<int> p, sz;
  dsu(int n = 0) : cc(n), p(n, -1), sz(n, 1) {}
  int root(int v) const {
    while (p[v] != -1) v = p[v];
    return v;
  }
  bool unite(int u, int v) {
    u = root(u), v = root(v);
    if (u == v) return false;
    --cc;
    if (sz[u] < sz[v]) swap(u, v);
    p[v] = u;
    sz[u] += sz[v];
    return true;
  }
  bool same(int u, int v) const { return root(u) == root(v); }
  int size(int v) const { return sz[root(v)]; }
};

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  dsu d(n), b(2 * n + 1);
  long long res = -m;
  while (m--) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    d.unite(u, v);
    b.unite(u, n + v);
    b.unite(n + u, v);
  }
  for (int v = 0; v < n; ++v) {
    if (b.same(v, n + v)) {
      cout << "-1\n";
      exit(0);
    }
    if (b.same(v, 2 * n) or b.same(n + v, 2 * n)) continue;
    b.unite(v, 2 * n);
  }
  vector<int> x(n), y(n);
  for (int v = 0; v < n; ++v) {
    if (b.same(v, 2 * n)) {
      ++x[d.root(v)];
    } else {
      ++y[d.root(v)];
    }
  }
  bitset<100001> dp;
  dp[0] = 1;
  for (int v = 0; v < n; ++v) {
    if (v != d.root(v)) continue;
    dp = dp << x[v] | dp << y[v];
  }
  for (int i = n / 2; ; --i) {
    if (dp[i]) {
      assert(dp[n - i]);
      res += (long long)i * (n - i);
      break;
    }
  }
  cout << res << '\n';
}