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>
struct UnionFind {
public:
  int n;
  std::vector<int> par;
  UnionFind(int n): n(n) {
    par.resize(n, -1);
  }
  int root(int x) {
    return par[x] < 0 ? x : par[x] = root(par[x]);
  }
  void unite(int x, int y) {
    int rx = root(x), ry = root(y);
    if(rx == ry) return;
    if(par[rx] < par[ry]) {
      std::swap(x, y);
      rx = root(x), ry = root(y);
    }
    par[rx] += par[ry];
    par[ry] = rx;
  }
  bool same(int x, int y) {
    return root(x) == root(y);
  }
  int size(int x) {
    return -par[root(x)];
  }
};
struct XorShift
{
   uint32_t w, x, y, z;
   XorShift(uint32_t seed = time(nullptr))
   {
       w = seed;
       x = w << 13;
       y = (w >> 9) ^ (x << 6);
       z = y >> 7;
   }
   uint32_t rand()
   {
       uint32_t t = x ^ (x << 11);
       x = y;
       y = z;
       z = w;
       return w = (w ^ (w >> 19) ^ (t ^ (t >> 8)));
   }
   int randInt(int min = 0, int max = 0x7FFFFFFF)
   {
       return rand() % (max - min + 1) + min;
   }
   double randDouble(double min = 0, double max = 1)
   {
       return (double)(rand() % 0xFFFF) / 0xFFFF * (max - min) + min;
   }
   void SetDefault()
   {
       w = 123456789;
       x = 362436069;
       y = 521288629;
       z = 88675123;
   }
};
XorShift randgen;
using namespace std;
using ll = long long;
using vi = vector<ll>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using P = pair<ll, ll>;
const double eps = 1e-8;
const ll MOD = 1000000007;
const ll INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;
template <typename T1, typename T2>
bool chmax(T1 &a, const T2 &b) {
  if(a < b) {a = b; return true;}
  return false;
}
template <typename T1, typename T2>
bool chmin(T1 &a, const T2 &b) {
  if(a > b) {a = b; return true;}
  return false;
}
template<typename T1, typename T2>
ostream& operator<<(ostream &os, const pair<T1, T2> p) {
  os << p.first << ":" << p.second;
  return os;
}
template<class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  for(ll i=0;i<((ll)(v.size()));++i) {
    if(i) os << " ";
    os << v[i];
  }
  return os;
}
vi col;
bool ok = true;
void dfs(ll now, ll prev, ll nowc, const vvi &g) {
  if(!ok) return;
  col[now] = nowc;
  for(ll i=0;i<((ll)(g[now].size()));++i) {
    ll nxt = g[now][i];
    if(nxt == prev) continue;
    if(col[nxt] == nowc) {
      ok = false;
      return;
    }
    if(col[nxt] != -1) continue;
    dfs(nxt, now, !nowc, g);
  }
}
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  ll n, m; cin >> n >> m;
  vvi g(n);
  UnionFind uf(n);
  for(ll i=0;i<(m);++i) {
    ll a, b; cin >> a >> b;
    a--; b--;
    g[a].push_back(b);
    g[b].push_back(a);
    uf.unite(a, b);
  }
  col.resize(n, -1);
  for(ll i=0;i<(n);++i) {
    if(col[i] != -1) continue;
    dfs(i, -1, 0, g);
  }
  if(!ok) {
    cout << -1 << endl;
    return 0;
  }
  map<ll, ll> mp;
  for(ll i=0;i<(n);++i) {
    mp[uf.root(i)] += col[i];
  }
  vi v;
  for(auto &e: mp) {
    v.push_back(abs(uf.size(e.first) - 2 * e.second));
  }
  bitset<200010> dp(0);
  dp[100001] = 1;
  for(auto &e: v) {
    auto tmp = dp >> e;
    dp = (dp << e) | tmp;
  }
  ll ans = LINF;
  for(ll i=0;i<(200010);++i) {
    if(dp[i]) chmin(ans, abs(i-100001));
  }
  ll add = (n - ans) / 2;
  cout << add * (add + ans) - m << endl;
}