// C++ program to find out whether a given graph can be
// converted to two Cliques or not.
#include <bits/stdc++.h>
using namespace std;

int V;

int GC[701][701];

// This function returns true if subgraph reachable from
// src is Bipartite or not.
pair<int, int> isBipartiteUtil(int src, int colorArr[])
{
    int c0 = 0, c1 = 0;

    colorArr[src] = 1;
    c1++;

    // Create a queue (FIFO) of vertex numbers and enqueue
    // source vertex for BFS traversal
    queue<int> q;
    q.push(src);

    // Run while there are vertices in queue (Similar to BFS)
    while (!q.empty()) {
        // Dequeue a vertex from queue
        int u = q.front();
        q.pop();

        // Find all non-colored adjacent vertices
        for (int v = 0; v < V; ++v) {
            // An edge from u to v exists and destination
            // v is not colored
            if (GC[u][v] && colorArr[v] == -1) {
                // Assign alternate color to this adjacent
                // v of u
                colorArr[v] = 1 - colorArr[u];

                if (colorArr[v] == 0) {
                    c0++;
                } else {
                    c1++;
                }

                q.push(v);
            }

            // An edge from u to v exists and destination
            // v is colored with same color as u
            else if (GC[u][v] && colorArr[v] == colorArr[u])
                return make_pair(-1, -1);
        }
    }

    // If we reach here, then all adjacent vertices can
    // be colored with alternate color
    return make_pair(c0, c1);
}

int tbl[701][1402];

int solve(int pos, int d, const vector<pair<int, int>>& ps)
{
    if (pos == ps.size()) {
        return abs(d);
    }

    auto& ret = tbl[pos][d + 700];
    if (ret >= 0) {
        return ret;
    }

    ret = solve(pos + 1, d + ps[pos].first - ps[pos].second, ps);
    ret = min(ret, solve(pos + 1, d - ps[pos].first + ps[pos].second, ps));

    return ret;
}

// Returns true if a Graph G[][] is Bipartite or not. Note
// that G may not be connected.
int isBipartite()
{
    // Create a color array to store colors assigned
    // to all veritces. Vertex number is used as index in
    // this array. The value '-1' of  colorArr[i]
    // is used to indicate that no color is assigned to
    // vertex 'i'.  The value 1 is used to indicate first
    // color is assigned and value 0 indicates
    // second color is assigned.
    int colorArr[V];
    for (int i = 0; i < V; ++i)
        colorArr[i] = -1;

    vector<pair<int, int>> ps;

    // One by one check all not yet colored vertices.
    for (int i = 0; i < V; i++) {
        if (colorArr[i] == -1) {
            auto t = isBipartiteUtil(i, colorArr);

            if (t.first < 0) {
                return -1;
            }

            ps.push_back(t);
        }
    }

    memset(tbl, -1, sizeof(tbl));
    int diff = solve(0, 0, ps);

    // int c0 = 0, c1 = 0;
    // for (int i = 0; i < V; i++) {
    //     if (colorArr[i] == 0) {
    //         c0++;
    //     } else {
    //         c1++;
    //     }
    // }

    // c0 - c1 = diff;
    // c0 + c1 = V;

    int c0 = (diff + V) / 2;
    int c1 = V - c0;

    return c0 * (c0 - 1) / 2 + c1 * (c1 - 1) / 2;
}

int G[701][701];

// Returns true if G can be divided into
// two Cliques, else false.
int canBeDividedinTwoCliques()
{
    // Find complement of G[][]
    // All values are complemented except
    // diagonal ones
    for (int i = 0; i < V; i++)
        for (int j = 0; j < V; j++)
            GC[i][j] = (i != j) ? !G[i][j] : 0;

    // Return true if complement is Bipartite
    // else false.
    return isBipartite();
}

// Driver program to test above function
int main()
{
    int m;
    cin >> V >> m;

    for (int i = 0; i < m; i++) {
        int f, t;
        cin >> f >> t;
        f--, t--;
        G[f][t] = G[t][f] = 1;
    }

    cout << canBeDividedinTwoCliques() << endl;

    return 0;
}

Measured memory_bytes: 7936