Problem: Example

Input

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


Output

11

Solution (in CPP):

Solution:
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <climits>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <bitset>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define chmax(a,b) (a<b?(a=b,1):0)
#define chmin(a,b) (a>b?(a=b,1):0)
#define valid(y,x,h,w) (0<=y&&y<h&&0<=x&&x<w)
typedef long long ll;
typedef pair<int,int> pii;
const int INF = 1<<29;
const double PI = acos(-1);
const double EPS = 1e-8;

vector<int> g[100000];
int n,m;

int color[100000];

int c1,c2;
bool dfs(int v, int c) {
  color[v] = c;
  if (c == 1) c1++;
  else c2++;
  FOR(it, g[v]) {
    if (color[*it] == c) return 0;
    if (color[*it] == 0 && !dfs(*it,-c)) return 0;
  }
  return 1;
}

int dp[100001];
ll ans;
bool solve() {
  map<int,int> mp;
  int summin = 0;
  int sumdiff = 0;
  REP(i,n) {
    if (color[i] == 0) {
      c1 = 0, c2 = 0;
      if (!dfs(i,1)) return 0;
      mp[abs(c1-c2)]++;
      summin += min(c1,c2);
      sumdiff += abs(c1-c2);
    }
  }
  memset(dp,-1,sizeof(dp));
  dp[0] = 0;
  int i = 0;
  FOR(it, mp) {
    REP(j,n+1) {
      if (dp[j] >= 0) {
        dp[j] = it->second;
      } else if (j<it->first || dp[j-it->first] <= 0) {
        dp[j] = -1;
      } else {
        dp[j] = dp[j-it->first]-1;
      }
    }
    i++;
  }
  ans = 0;
  REP(i,n+1) {
    if (dp[i] >= 0) {
      ll a = summin + i;
      ll b = summin + sumdiff - i;
      chmax(ans, a*b);
    }
  }
  ans -= m;
  return 1;
}

int main() {
  cin >> n >> m;
  REP(i,m) {
    int a,b;
    cin >> a >> b;
    a--;b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  if (!solve()) cout << -1 << endl;
  else cout << ans << endl;
}