Problem: Example

Input

8 5
1 2
6 5
6 4
1 3
4 7


Output

11

Solution (in CPP):

Solution:
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
#include <functional>
using namespace std;

vector<vector<int> > edges;
vector<int> check;

bool solve(int curr, int color, vector<int>& x)
{
    check[curr] = color;
    ++ x[color];

    for(unsigned i=0; i<edges[curr].size(); ++i){
        int next = edges[curr][i];
        if(check[next] == -1){
            if(!solve(next, color^1, x))
                return false;
        }else{
            if(check[next] == color)
                return false;
        }
    }

    return true;
}

int main()
{
    int v, e;
    cin >> v >> e;

    edges.assign(v, vector<int>());
    for(int i=0; i<e; ++i){
        int a, b;
        cin >> a >> b;
        edges[a-1].push_back(b-1);
        edges[b-1].push_back(a-1);
    }

    check.assign(v, -1);
    bitset<50001> bs;
    bs[0] = true;

    for(int i=0; i<v; ++i){
        if(check[i] != -1)
            continue;

        vector<int> x(2, 0);
        if(!solve(i, 0, x)){
            cout << -1 << endl;
            return 0;
        }

        bs = (bs << x[0]) | (bs << x[1]);
    }

    int a = v / 2;
    while(!bs[a])
        -- a;

    long long ret = (long long)a * (v - a);
    ret -= e;
    cout << ret << endl;

    return 0;
}