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>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
struct UnionFind {vector<int> par; // uf(x,y)->y
    UnionFind(int NV) { par.clear(); rep(i, 0, NV) par.push_back(i); }
    void reset() { rep(i, 0, par.size()) par[i] = i; }
    int operator[](int x) { return par[x] == x ? x : par[x] = operator[](par[x]); }
    void operator()(int x, int y) {x = operator[](x); y = operator[](y);if (x != y) par[x] = y;}};
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/






int N, M;
vector<int> E[101010];
//---------------------------------------------------------------------------------------------------
inline int rev(int x) {
    if (x == 1) return 2;
    return 1;
}
vector<int> gr[101010];
int col[101010];
int dfs(int cu, int co) {
    col[cu] = co;
    fore(to, E[cu]) {
        if (col[to]) {
            if (col[cu] == col[to]) return -1;
        } else {
            int re = dfs(to, rev(co));
            if (re < 0) return -1;
        }
    }
    return 0;
}
int get(int st) {
    int res = dfs(st, 1);
    if (res < 0) return -1;

    int a = 0, b = 0;
    fore(i, gr[st]) {
        if (col[i] == 1) a++;
        else b++;
    }
    return abs(a-b);
}
//---------------------------------------------------------------------------------------------------
int dp[2][201010][2];
void _main() {
    cin >> N >> M;
    UnionFind uf(N);
    rep(i, 0, M) {
        int a, b; cin >> a >> b;
        a--; b--;
        E[a].push_back(b);
        E[b].push_back(a);
        uf(a, b);
    }

    map<int, int> m;
    rep(i, 0, N) gr[uf[i]].push_back(i);
    rep(i, 0, N) if(uf[i] == i) {
        auto p = get(i);
        if (p < 0) {
            printf("-1\n");
            return;
        }
        m[p]++;
    }

    vector<pair<int, int>> v;
    fore(p, m) v.push_back(p);
    int n = v.size();
    int offset = 100010;

    rep(d, 0, 201010) rep(parity, 0,2) dp[0][d][parity] = -1;
    dp[0][offset][0] = 0;
    rep(_i, 0, n) {
        int c = v[_i].first;
        int num = v[_i].second;
        int i = _i % 2;
        int ii = 1 - i;

        rep(d, 0, 201010) rep(parity, 0, 2) dp[ii][d][parity] = -1;

        rep(d, 0, 201010) if (0 <= dp[i][d][0]) dp[ii][d][num % 2] = num;
        rep(d, 0, 201010) rep(parity, 0, 2) if (0 < dp[ii][d][parity]) {
            int dd = d + c;
            if (dd < 201010) chmax(dp[ii][dd][1-parity], dp[ii][d][parity] - 1);
        }
        rrep(d, 201010-1, 0) rep(parity, 0, 2) if (0 < dp[ii][d][parity]) {
            int dd = d - c;
            if (0 <= dd) chmax(dp[ii][dd][1 - parity], dp[ii][d][parity] - 1);
        }
    }

    int mi = inf;
    rep(i, 0, 201010) if (0 <= dp[n%2][i][0]) chmin(mi, abs(i - offset));

    int a = (N - mi) / 2;
    int b = N - a;

    ll ans = 1LL * a * b - M;
    cout << ans << endl;
}