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"

using namespace std;

using ll = long long;
using ld = long double;
using P = pair<int, int>;
constexpr ld EPS = 1e-12;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr int MOD = 1e9 + 7;

template <typename T>
void printv(const vector<T> &v)
{
    int sz = v.size();
    for (int i = 0; i < sz; i++)
    {
        cout << v[i] << " \n"[i == sz - 1];
    }
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll n, m;
    cin >> n >> m;
    vector<vector<int>> g(n);
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    bool f = false;
    vector<int> col(n, -1);
    vector<P> p;
    for (int i = 0; i < n; i++)
    {
        if (col[i] != -1)
            continue;
        queue<int> que;
        que.push(i);
        col[i] = 0;
        int one = 0, zero = 1;
        while (!que.empty())
        {
            int cur = que.front();
            que.pop();
            for (auto v : g[cur])
            {
                if (col[v] == -1)
                {
                    col[v] = 1 - col[cur];
                    que.push(v);
                    if (col[v])
                        one++;
                    else
                        zero++;
                    continue;
                }
                if (col[v] == col[cur])
                    f = true;
            }
        }
        p.emplace_back(min(one, zero), max(one, zero));
    }
    if (f)
    {
        cout << -1 << endl;
        return 0;
    }
    bitset<100000> bs;
    bs.set(0);
    for (auto pp : p)
    {
        int a = pp.first, b = pp.second;
        bs = (bs << a) | (bs << b);
    }
    ll ret = 0;
    for (ll i = 0; i <= n; i++)
        if (bs[i])
            ret = max(ret, i * (n - i) - m);
    cout << ret << endl;
}