Problem: Example

Input

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


Output

11

Solution (in CPP):

Solution:
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
#include<numeric>
using namespace std;
#define INF (1 << 30) - 1
#define LINF 1LL << 60
const int MOD = 1000000007;
using ll = long long;
using P = pair<int, int>;

vector<vector<int>> g;

vector<int> color;
P dfs(int v, int c){
  P res = {0, 0};
  color[v] = c;
  if(c == 1)++res.first; 
  else ++res.second; 
  for(auto nv : g[v]){
    if(color[nv] == c)return {-1, -1};
    if(color[nv] == 0){
      P tmp = dfs(nv, -c);
      if(tmp.first < 0)return {-1, -1};
      res.first += tmp.first;
      res.second += tmp.second;
    }
  }
  return res;
}

int dp[100100];
map<int, int> mp;

int main(){
  int n, m;
  cin >> n >> m;
  g.resize(n);
  for(int i = 0; i < m; ++i){
    int a, b;
    cin >> a >> b;
    --a;
    --b;
    g[a].push_back(b);
    g[b].push_back(a);
  }

  color.assign(n, 0);
  int v = 0;
  for(int i = 0; i < n; ++i){
    if(color[i] != 0)continue;
    P p = dfs(i, 1);
    int a = min(p.first, p.second);
    int b = max(p.first, p.second);
    if(a < 0){
      cout << -1 << endl;
      return 0;
    }
    ++mp[b - a];
    v += a;
  }

  memset(dp, -1, sizeof(dp));
  dp[0] = 0;
  for(auto p : mp){
    int plus = p.first;
    int num = p.second;
    for(int i = 0; i <= n; ++i){
      if(dp[i] >= 0)dp[i] = num;
      else if(i < plus || dp[i - plus] <= 0)dp[i] = -1;
      else dp[i] = dp[i - plus] - 1;
    }
  }

  ll ans = 0;
  for(int i = 0; i <= n; ++i){
    if(dp[i] >= 0)ans = max(ans, ll(v + i) * (n - v - i));
  }
  cout << ans - m << endl;
  return 0;
}