Problem: Example

Input

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


Output

11

Solution (in CPP):

Solution:
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <sstream>
#include <vector>
using namespace std;

#define REP2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define REP(i, n) REP2(i, 0, n)
#define ALL(c) (c).begin(), (c).end()
#define FOREACH(i, c) for(auto i = (c).begin(); i != (c).end(); ++i)
#define BIT(n, m) (((n) >> (m)) & 1)

typedef long long ll;
typedef pair<int, int> PI;

const ll inf = 1e15;
const ll mod = 1000 * 1000 * 1000 + 7;
const double eps = 1e-9;

template <typename S, typename T> ostream &operator<<(ostream &out, const pair<S, T> &p) {
  out << "(" << p.first << ", " << p.second << ")";
  return out;
}

template <typename T> ostream &operator<<(ostream &out, const vector<T> &v) {
  out << "[";
  REP(i, v.size()){
    if (i > 0) out << ", ";
    out << v[i];
  }
  out << "]";
  return out;
}



int main(){
  int N, M;
  cin >> N >> M;
  vector<vector<int> > G(N);
  REP(i, M){
    int a, b;
    cin >> a >> b; a--, b--;
    G[a].push_back(b);
    G[b].push_back(a);
    // cout << a << " " << b << endl;
  }

  vector<int> color(N, -1);
  map<int, int> diffs;


  ll S = 0;
  REP(i, N) if (color[i] == -1){
    queue<int> que;
    que.push(i);
    color[i] = 0;
    vector<int> count(2, 0);

    
    while (!que.empty()){
      int v = que.front(); que.pop();
      // cout << v << endl;

      count[color[v]]++;
      for (int w : G[v]){
        if (color[w] == color[v]) {
          cout << -1 << endl;
          return 0;
        } else if (color[w] == -1){
          color[w] = 1 - color[v];
          que.push(w);
        }
      }
    }
    diffs[abs(count[1] - count[0])]++;
    S += *min_element(ALL(count));
  }
  vector<int> dp(2 * N + 1, -1);
  dp[0] = 0;
  for (const auto &p : diffs){
    REP(j, 2 * N + 1){
      if (dp[j] >= 0){
        dp[j] = p.second;
      } else if (j < p.first || dp[j - p.first] <= 0){
        dp[j] = -1;
      } else {
        dp[j] = dp[j - p.first] - 1;
      }
    }
  }
  ll res = 0;
  REP(i, 2 * N + 1) if (dp[i] != -1){
    ll A = S + i;
    ll B = N - A;
    // cout << A << " "<< B << endl;
    res = max(res,  A * B - M);
  }
  cout << res << endl;
  
  return 0;
}