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;

struct Benri { Benri() { std::cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(12);}} benri;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vll = vector<long long>;
using pll = pair<ll, ll>;
using ull = unsigned long long;

template <typename T> using PQ = priority_queue<T>;
template <typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define mp make_pair
#define F first
#define S second

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; }

constexpr long long MOD = 1000000007;
//constexpr long long MOD = 998244353;
constexpr int INF = 1001001001;
//constexpr ll INF = 1001001001001001001ll;
constexpr double EPS = 1e-10;
using number = long long;



// nums[i] := i 番目の連結成分の {左ノード数, 右ノード数}, 「dir = 1: 左、-1: 右」
using Graph = vector<vector<int> >;

//dfs()とisbiparite()で二部グラフ判定を行う 　副作用でi番目の連結成分について調べる(UnionFindでも似たようなことはできる)
bool dfs(const Graph &G, int v, int vdir, pii &num, vector<int> &dir) {
    bool res = true;
    dir[v] = vdir;
    if (vdir == 1) ++num.first;
    else if (vdir == -1) ++num.second;
    for (auto nv : G[v]) {
        if (dir[nv] == 0) {
            if (!dfs(G, nv, -vdir, num, dir)) res = false;
        }
        else if (dir[nv] != -vdir) res = false;
    }
    return res;
}

bool isbipartite(const Graph &G, vector<pii> &nums) {
    bool res = true;
    int N = (int)G.size();
    vector<int> dir(N, 0);
    for (int v = 0; v < N; ++v) {
        if (dir[v] != 0) continue;
        pii num = {0, 0};
        if (!dfs(G, v, 1, num, dir)) res = false;
        nums.push_back(num);
    }
    return res;
}


int main() {
    int V, E; cin >> V >> E;
    Graph G(V);
    for (int i = 0; i < E; ++i) {
        int a, b; cin >> a >> b; --a, --b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    // 二部グラフ判定して、左ノード数と右ノード数の差分ごとに集計
    vector<pii> nums;
    if (!isbipartite(G, nums)) {
        cout << -1 << endl;
        return 0;
    }

    //√Vでの平方分割を行う
    map<int, int> ma;
    for (auto p : nums) ma[abs(p.first - p.second)]++;

    // DP　dp[i][v]は最初の i (<= √V)種類だけ見て、総和が実質 v になるようにしたときの、最後の要素の使用最小値
    //特にINFでなければ総和がvの組み合わせが存在(余分な情報を持たせてdpを回す 個数制限付き部分和問題)　
    //実装上iは省略し配列使いまわし
    int geta = 0;
    vector<int> dp(V * 2 + 10, INF);
    dp[0] = 0;
    for (auto it = ma.begin(); it != ma.end(); ++it) {
        int diff = it->first;
        geta += diff * it->second;
        for (int v = 0; v <= V * 2; ++v) {
            if (dp[v] < INF) dp[v] = 0;
        }
        for (int v = 0; v <= V * 2; ++v) {
            if (v + diff * 2 <= V * 2 && dp[v] < it->second) {
                chmin(dp[v + diff * 2], dp[v] + 1);
            }
        }
    }

    // 集計
    int diff = V;
    for (int v = 0; v <= V * 2; ++v) {
        if (dp[v] < INF) chmin(diff, abs(v - geta));
    }

    ll a = (V + diff) / 2, b = (V - diff) / 2;
    cout << a * b - E << endl;
}