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);
  }
  vector<PLL> 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;
	  }
	  xs.EB(res);
	}
  }
  
  LL ans = 0;
  bitset<100001> bs;
  bs[0] = 1;
  for(auto& p: xs)
	bs = (bs << p.FF) | (bs << p.SS);

  REP(i,V+1)
	if(bs[i]){
	  maxi(ans, (LL)i * (V - i));
	}
  cout << ans - E << endl;

  return 0;
}