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>
using namespace std;

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define FF first
#define SS second
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}


const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;

bool dfs(VVI& G, int u, VI& parity, PLL& res){
  if(parity[u] > 0) res.FF++;
  else res.SS++;

  for(int to: G[u]){
	if(parity[to]){
	  if(parity[to] == parity[u])
		return false;
	}
	else{
	  parity[to] = -parity[u];
	  if(!dfs(G, to, parity, res))
		return false;
	}
  }
  return true;
}

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int V, E; cin >> V >> E;
  VVI G(V);
  REP(i,E){
	int u, v; cin >> u >> v;
	--u;
	--v;
	G[u].PB(v);
	G[v].PB(u);
  }

  map<PLL,int> xs;
  VI parity(V);
  REP(i,V){
	if(!parity[i]){
	  parity[i] = 1;
	  PLL res;
	  if(!dfs(G, i, parity, res)){
		cout << -1 << endl;
		return 0;
	  }
	  if(res.FF < res.SS) swap(res.FF, res.SS);
	  xs[res]++;
	}
  }

  int crt = 0, nxt = 1;
  vector<vector<bool>> dp(2, vector<bool>(V+1));
  dp[crt][0] = true;
  for(auto&& p_: xs){
	int num = p_.SS;
	int b = 1;
	while(num){
	  fill(ALL(dp[nxt]), false);
	  if(num < b)
		b = num;
	  num -= b;

	  PLL p(p_.FF.FF * b, p_.FF.SS*b);
	  for(int i=V;i-p.FF>=0;--i)
		dp[nxt][i] = dp[nxt][i] || dp[crt][i-p.FF];
	  for(int i=V;i-p.SS>=0;--i)
		dp[nxt][i] = dp[nxt][i] || dp[crt][i-p.SS];
	  
	  b <<= 1;
	  swap(crt, nxt);
	}
  }

  LL ans = 0;
  REP(i,V+1) if(dp[crt][i]) maxi(ans, (LL)i*(V-i));
  cout << ans - E << endl;

  return 0;
}