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 <bitset>
#include <utility>
using namespace std;

pair<int,int> dfs(vector< vector<int> > &G, int v, int c, vector<int> &visited){
  pair<int,int> ret = make_pair(1, 0);
  for(int i = 0; i < G[v].size(); ++i){
    int u = G[v][i];
    if(visited[u] == c) continue;
    if(visited[u] == 1-c) return make_pair(-1,-1);
    visited[u] = c;
    pair<int,int> p = dfs(G, u, 1 - c, visited);
    if(p == make_pair(-1,-1)) return p;
    ret.first += p.second;
    ret.second += p.first;
  }
  return ret;
}

int main(){
  int V, E;
  cin >> V >> E;
  vector< vector<int> > G(V);
  for(int i = 0; i < E; ++i){
    int a, b;
    cin >> a >> b;
    --a,--b;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  vector<int> visited(V, -1);
  bitset<100001> dp = 1;
  for(int i = 0; i < V; ++i){
    if(visited[i] >= 0) continue;
    visited[i] = 1;
    pair<int,int> p = dfs(G, i, 0, visited);
    if(p == make_pair(-1, -1)){
      cout << -1 << endl;
      return 0;
    }
    dp = (dp << p.first)|(dp << p.second);
  }
  long long int ans = 0;
  for(int i = 0; i <= V/2; ++i){
    if(dp[i]) ans = max(ans, (long long int)i*(V-i) - E);
  }
  cout << ans << endl;
  return 0;
}