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;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef pair<int, int> P;
typedef long long ll;
vector<int> v[100100];
vector<int> e(100100); //0:uncolored 1:white -1:black
bool flag;
P dfs(int color, int node)
{ //P.first:1 P.decond:-1
    P res = P(0, 0);
    for (auto i : v[node])
    {
        if (e[i] == 0)
        {
            e[i] = -color;
            P p = dfs(-color, i);
            res.first += p.first;
            res.second += p.second;
        }
        else if (e[i] == color)
        {
            flag = true;
        }
    }
    if (color == 1)
    {
        res.first++;
    }
    else
    {
        res.second++;
    }
    return res;
}
int dp[100100];
int main()
{
    ll n, m;
    cin >> n >> m;
    rep(i, m)
    {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    vector<P> ans;
    for (int i = 1; i <= n; i++)
    {
        if (e[i] == 0)
        {
            e[i] = 1;
            P p = dfs(1, i);
            ans.push_back(p);
        }
    }
    int mx = 0;
    int mn = 0;
    dp[0] = 1;
    for (auto i : ans)
    {
        int tmn = dp[mn] + i.first;
        int tmx = tmn;
        for (int j = n; j >= 0; j--)
        {
            if (dp[j])
            {
                dp[j] = 0;
                dp[j + i.first] = 1;
                dp[j + i.second] = 1;
                tmx = max(tmx, dp[j + i.first]);
                tmx = max(tmx, dp[j + i.second]);
                tmn = min(tmn, dp[j + i.first]);
                tmn = min(tmn, dp[j + i.second]);
            }
        }
        mx = tmx;
        mn = tmn;
    }
    if (flag)
    {
        cout << -1 << endl;
    }
    else
    {
        ll ans = 0;
        for(ll i = 1;i<=n;i++){
            if(dp[i]){
                ans = max(ans,i*(n-i));
            }
        }
        cout << ans - m << endl;
    }
    return 0;
}