#include <algorithm>
#include <iostream>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <queue>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <bitset>
#include <complex>
#define _USE_MATH_DEFINES
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> plglg;
typedef tuple<int, int, int> tiii;
typedef tuple<ll, ll, ll> tlglglg;
typedef complex<double> xy_t;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
double pi = 3.141592653589793;
ll mod = 1000000007;
int intmax = 2147483647;
int intmin = -2147483648;
ll llmax = 9223372036854775807;
ll llmin = -9223372036854775807;
ll inf = llmax / 2;
double eps = 1e-11;

struct unionFind {
    vector<int> data;
    unionFind(int size) {
        for (int i = 0; i < size; i++) {
            data.push_back(i);
        }
    }
    
    bool unite(int x, int y) {
        x = root(x);
        y = root(y);
        if (x != y) {
            if(data[y] < data[x]) {
                swap(x, y);
            }
            //data[x] += data[y];
            data[y] = -1 * data[x];
        }
        return x != y;
    }

    bool same(int x, int y) {
        return root(x) == root(y);
    }

    int root(int x) {
        if (data[x] == x) {
            return x;
        }
        if (data[x] > 0) {
            data[x] = root(data[x]);
            return data[x];
        } else {
            data[x] = -1 * root(data[x]);
            return data[x];
        }
    }

    int rank(int x) {
        return -data[root(x)];
    }
};

struct edge {
    int to, cost;
};

int V;
vector<edge> G[1000000];
ll d[1000000];

vector<pii> vp;

bool BFS() {
    fill(d, d + V, -1);
    while (true) {
        int num = 0;
        for (int i = num; i < V; i++) {
            if (d[num] == -1) {
                break;
            }
            num++;
        }
        if (d[num] != -1) {
            return true;
        }
        d[num] = 0;
        queue<int> que;
        que.push(num);
        int x = 1;
        int y = 0;
        while (que.size() > 0) {
            int base = que.front();
            que.pop();
            int s = G[base].size();
            for (int i = 0; i < s; i++) {
                int to = G[base][i].to;
                if (d[to] == -1) {
                    if (d[base] == 0) {
                        d[to] = 1;
                        y++;
                    } else {
                        d[to] = 0;
                        x++;
                    }
                    que.push(to);
                } else {
                    if (d[to] == 1 && d[base] == 1) {
                        return false;
                    } else if (d[to] == 0 && d[base] == 0) {
                        return false;
                    }
                }
            }
        }
        vp.push_back(pii(x, y));
    }
}

bool p[800][800];

bool dp[800][800];

int main() {
    int N, M;
    cin >> N >> M;
    V = N;
    for (int i = 0; i < 800; i++) {
        fill(p[i], p[i] + 800, false);
    }
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        p[a - 1][b - 1] = true;
        p[b - 1][a - 1] = true;
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (i != j && !p[i][j]) {
                edge e1;
                e1.to = j;
                e1.cost = 1;
                G[i].push_back(e1);
                edge e2;
                e2.to = i;
                e2.cost = 1;
                G[j].push_back(e2);
            }
        }
    }
    bool ok = BFS();
    if (!ok) {
        cout << -1 << endl;
        return 0;
    } else {
        for (int i = 0; i < 800; i++) {
            fill(dp[i], dp[i] + 800, false);
        }
        int len = vp.size();
        dp[0][0] = true;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < N; j++) {
                if (dp[i][j]) {
                    dp[i + 1][j + vp[i].first] = true;
                    dp[i + 1][j + vp[i].second] = true;
                }
            }
        }
        ll min = llmax;
        for (int i = 0; i < N; i++) {
            if (dp[len][i]) {
                ll num = (i * (i - 1) / 2) + ((N - i) * (N - i - 1) / 2);
                if (num < min) {
                    min = num;
                }
            }
        }
        cout << min << endl;
    }
}


Measured memory_bytes: 36224