Problem: Example

Input

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


Output

11

Solution (in CPP):

Solution:
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <bitset>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

typedef vector<int> Edges;
typedef vector<Edges> Graph;

int n, m;
int color[100010];
bitset<100010> ok[2];
Graph g;

bool dfs(int from, int c, int &cnt1, int &cnt2) {
  if (color[from] != -1) { return color[from] == c; }
  color[from] = c;
  if (c == 1) { cnt1++; }
  else { cnt2++; }
  bool ret = true;
  FORIT(it, g[from]) {
    int to = *it;
    ret &= dfs(to, c ^ 1, cnt1, cnt2);
  }
  return ret;
}

int main() {
  while (scanf("%d %d", &n, &m) > 0) {
    MEMSET(color, -1);
    g = Graph(n);
    REP(i, m) {
      int f, t;
      scanf("%d %d", &f, &t);
      f--; t--;
      g[f].push_back(t);
      g[t].push_back(f);
    }
    int base = 0;
    map<int, int> cnt;
    REP(i, n) {
      if (color[i] != -1) { continue; }
      int c1 = 0;
      int c2 = 0;
      if (!dfs(i, 0, c1, c2)) {
        goto ng;
      }
      base += min(c1, c2);
      if (c1 == c2) { continue; }
      cnt[max(c1, c2) - min(c1, c2)]++;
    }
    {
      ll ans = 0;
      ok[0].reset();
      ok[1].reset();
      ok[0][0] = 1;
      int prev = 0;
      int next = 1;
      FORIT(it, cnt) {
        int v = it->first;
        int c = it->second;
        REP(start, v) {
          int rest = 0;
          for (int i = start; i < n; i += v) {
            if (ok[prev][i]) {
              ok[next][i] = 1;
              rest = c;
            } else if (rest > 0) {
              ok[next][i] = 1;
              rest--;
            }
          }
        }
        swap(prev, next);
      }
      ok[0] |= ok[1];
      REP(i, n) {
        if (!ok[0][i]) { continue; }
        ll left = base + i;
        ll right = n - left;
        ans = max(ans, left * right - m);
      }
      printf("%lld\n", ans);
    }
    continue;
ng:
    puts("-1");
  }
}