Problem: Example

Input

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


Output

11

Solution (in CPP):

Solution:
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cerr<<*i<<" "; cerr<<endl; }
inline bool valid(int x, int y, int W, int H){ return (x >= 0 && y >= 0 && x < W && y < H); }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
typedef vector<int> Node;
typedef vector<Node> Graph;
typedef pair<int, int> P;
P dfs(int u, int c, Graph& G, vector<int>& color){
  P res;
  if(color[u] != -1){
    if(color[u] == c) return P(0, 0);
    else return P(INF, INF);
  }else{
    color[u] = c;
    if(c == 0) res.first ++;
    else res.second ++;
  }
  REP(i, G[u].size()){
    int v = G[u][i];
    P p = dfs(v, c ^ 1, G, color);
    if(p.first >= INF) return P(INF, INF);
    res = P(res.first + p.first, res.second + p.second);
  }
  return res;
}

int main(){
  int V, E;
  while(cin >> V >> E && V){
    Graph G(V);
    REP(i, E){
      int a, b;
      scanf("%d %d", &a, &b);
      a--; b--;
      G[a].push_back(b);
      G[b].push_back(a);
    }
    vector<int> color(V, -1);
    vector<P> ps;
    int ans = 0;
    REP(i, V) if(color[i] == -1){
      P p = dfs(i, 0, G, color);
      if(p.first >= INF) ans = -1;
      ps.push_back(p);
    }
    if(ans == -1){
      cout << ans << endl;
      continue;
    }
    map<int, int> cnt;
    int sum = 0;
    REP(i, ps.size()){
      int a = min(ps[i].first, ps[i].second);
      int b = max(ps[i].first, ps[i].second);
      sum += a;
      if(b - a > 0) cnt[b - a]++;
    }
    vector<P> goods;
    FORIT(it, cnt) goods.push_back(P(it->first, it->second));
    vector<bool> dp(V / 2 - sum + 1, false);
    dp[0] = true;
    int max_c = 0;
    REP(i, goods.size()){
      int num = goods[i].second;
      for(int k = 1; num > 0; k <<= 1) {
        int s = min(num, k);
        num -= s;
        for(int j = dp.size() - 1; j >= 0; j--)if(dp[j]){
          int nj = j + goods[i].first * s;
          if(nj < dp.size()){
            max_c = max(max_c, nj);
            dp[nj] = true;
          }
        }
      }
    }
    max_c += sum;
    cout << (ll)max_c * (V - max_c) - E << endl;
  }
  return 0;
}