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>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;

#define REP(i, n) for (int i = 0; i < (n); i++)
#define int long long
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define all(x) x.begin(), x.end()
using pii = pair<int, int>;
using ll = long long;
using ld = long double;

int N, M;
vector<int> G[100010];

bool vis[100010];
bool col[100010];

void dfs(int n, bool res, int &a, int &b) {
    vis[n] = true;
    if (res == 0)
        a++;
    else
        b++;
    col[n] = res;
    for (auto nxt : G[n]) {
        if (vis[nxt]) {
            if (col[nxt] == res) {
                cout << -1 << endl;
                exit(0);
            }
            continue;
        }
        dfs(nxt, !res, a, b);
    }
}
bitset<100010> dp[2];
bool solve() {
    cin >> N >> M;
    REP(i, M) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    vector<int> A, B, C;
    REP(i, N) {
        if (!vis[i]) {
            int a = 0, b = 0;
            dfs(i, 0, a, b);
            A.push_back(a);
            B.push_back(b);
            C.push_back(abs(a - b));
        }
    }
    int K = A.size();
    dp[0][0] = true;
    REP(i, K) {
        //cerr << A[i] << " " << B[i] << endl;
        int now = i % 2;
        int nxt = (now + 1) % 2;
        dp[nxt] = (dp[now] << A[i]) | (dp[now] << B[i]);
    }
    int mx = 0;
    int sum = N;
    // cout << dp[K % 2] << endl;
    REP(i, N + 1) {
        if (dp[K % 2][i]) {
            mx = max(mx, (N - i) * i);
        }
    }
    cout << mx - M << endl;
    return true;
}

signed main() {
    // while (solve())
    solve();
}