Problem: Example

Input

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


Output

11

Solution (in CPP):

Solution:
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
using namespace std;

#define INF 1e18

bool dfs(int now, const vector<vector<long long int> >& adj,
         vector<long long int>& history, long long int& a, long long int& b, int odd_even = 1){
  history[now] = odd_even;
  if(odd_even == 1){ ++a; }
  else{ ++b; }
  
  for(int i = 0; i < (int)adj[now].size(); i++){
    if(history[adj[now][i]] == odd_even){ return false; }
    if(history[adj[now][i]] == 0)
      if(!dfs(adj[now][i], adj, history, a, b, -odd_even))
        return false;
  }
  
  return true;
}


int main(void){
  int v, e;
  cin >> v >> e;

  long long int input_a, input_b;
  vector<vector<long long int> > adj(v);
  for(int i = 0; i < e; i++){
    cin >> input_a >> input_b;
    --input_a;
    --input_b;
    adj[input_a].push_back(input_b);
    adj[input_b].push_back(input_a);
  }

  long long int a_sum = 0, b_sum = 0;
  vector<long long int> c_tmp;
  vector<long long int> history(v, 0);
  for(int i = 0; i < v; i++){
    if(history[i] == 0){
      long long int a = 0;
      long long int b = 0;
      if(!dfs(i, adj, history, a, b)){
        cout << -1 << endl;
        return 0;
      }
      else{
        if(a > b){ swap(a, b); }
        a_sum += a;
        b_sum += b;
        c_tmp.push_back(b - a);
      }
    }
  }
  map<long long int, int> c_map;
  for(size_t i = 0; i < c_tmp.size(); i++){ ++c_map[c_tmp[i]]; }

  vector<pair<long long int, int> > c;
  c.push_back(make_pair(0, INF));
  for(map<long long int, int>::iterator it = c_map.begin(); it != c_map.end(); ++it){ c.push_back(*it); }
  
  int n = c.size();
  vector<long long int> dp(vector<long long int>(v + 1, -INF));
  dp[0] = INF;
  for(int i = 1; i < n; i++)
    for(int j = 0; j <= v; j++)
      dp[j] = dp[j] >= 0 ? c[i].second :
        j >= c[i].first ? dp[j - c[i].first] - 1 : (int)INF * (-1);

  int minpoint = -1;
  long long int mindiff = INF;
  for(int i = 0; i <= v; i++){
    if(dp[i] >= 0){
      long long int candiate = abs((a_sum + i) - (b_sum - i));
      if(mindiff > candiate){
        mindiff = candiate;
        minpoint = i;
      }
    }
  }

  long long int ans = (a_sum + minpoint) * (b_sum - minpoint) - e;
  cout << ans << endl;
  
  return 0;
}