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>
#define FOR(i,k,n) for(int64_t i=(k);i<(int64_t)(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(x) begin(x),end(x)

using namespace std;
using Graph = vector<vector<int>>;

void add_edge(Graph &g, int a, int b) {
  g[a].push_back(b);
  g[b].push_back(a);
}

bool dfs(const Graph &g, vector<int> &vis, int i) {
  for (int j : g[i]) {
    if (vis[j] == -1) {
      vis[j] = vis[i] ^ 1;
      if (!dfs(g, vis, j)) return false;
    } else if (vis[j] == vis[i]) {
      return false;
    }
  }
  return true;
}

int main() {
  int64_t v,e;
  cin>>v>>e;
  Graph g(v);
  REP(i,e) {
    int a,b;
    cin>>a>>b;
    --a;--b;
    add_edge(g, a, b);
  }
  vector<int> vis(v, -1);
  bool ok = true;
  int cnt = 0;
  REP(i,v) {
    if (vis[i] == -1) {
      vis[i] = 2 * cnt;
      if (!dfs(g, vis, i)) {
        ok = false;
      }
      ++cnt;
    }
  }
  if (!ok) {
    cout << -1 << endl;
    return 0;
  }
  vector<int> ary(cnt, 0);
  REP(i,v) {
    if ((vis[i] % 2) == 0) {
      ++ary[vis[i]/2];
    } else {
      --ary[vis[i]/2];
    }
  }
  REP(i,cnt) ary[i] = abs(ary[i]);
  int64_t sum = 0;
  REP(i,cnt) sum += ary[i];
  bitset<100001> dp;
  dp[0] = true;
  REP(i,cnt) {
    bitset<100001> tmp = dp;
    tmp |= dp << ary[i];
    swap(tmp, dp);
  }
  int64_t mx = 0;
  REP(i,sum+1) {
    if (dp[i]) {
      int64_t k = 2*i - sum;
      mx = max(mx, (v - k)/2 * (v + k)/2 - e);
    }
  }
  cout << mx << endl;
  return 0;
}