#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;
struct UnionFind {
    vector<int> par;
    vector<int> rank;

    UnionFind(int n = 1) {
        init(n);
    }

    void init(int n = 1) {
        par.resize(n + 1); rank.resize(n + 1);
        for (int i = 0; i <= n; ++i) par[i] = i, rank[i] = 0;
    }

    int root(int x) {
        if (par[x] == x) {
            return x;
        }
        else {
            int r = root(par[x]);
            return par[x] = r;
        }
    }

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

    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (rank[x] < rank[y]) swap(x, y);
        if (rank[x] == rank[y]) ++rank[x];
        par[y] = x;
        return true;
    }
};


int main() {
    //cout.precision(10);
    bool dp[720][720];
    UnionFind uni(3000);
    int n, m;
    cin >> n >> m;
    int field[720][720];
    for(int i = 0; i <= 710; i++){
        for(int j = 0; j <= 710; j++){
            dp[i][j] = false;
            field[i][j] = 0;
        }
    }
    dp[0][0] = true;
    for(int i = 1; i <= m; i++){
        int a, b;
        cin >> a >> b;
        field[a][b] = 1;
        field[b][a] = 1;
    }
    for(int i = 1; i <= n; i++){
        for(int j = i + 1; j <= n; j++){
            if(field[i][j] == 0){
                uni.merge(i, j + 1000);
                uni.merge(i + 1000, j);
                if(uni.issame(i, i + 1000) || uni.issame(j, j + 1000)){
                    cout << -1 << endl;
                    return 0;
                }
            }
        }
    }
    vector<int> part[2];
    for(int i = 1; i <= n; i++){
        if(uni.root(i) != i) continue;
        int sum1 = 0;
        int sum2 = 0;
        for(int j = 1; j <= n; j++){
            if(uni.issame(i, j)){
                sum1++;
            }
            if(uni.issame(i, j + 1000)){
                sum2++;
            }
        }
        part[0].push_back(sum1);
        part[1].push_back(sum2);
    }
    /*for(int i = 1; i <= n; i++){
        if(uni.root(i + 1000) != (i + 1000)) continue;
        int sum1 = 0;
        int sum2 = 0;
        for(int j = 1; j <= n; j++){
            if(uni.issame(i, j)){
                sum1++;
            }
            if(uni.issame(i, j + 1000)){
                sum2++;
            }
        }
        part[0].push_back(sum1);
        part[1].push_back(sum2);
    }
    for(int i = 0; i < part[1].size(); i++){
        cout << part[0][i] << " " << part[1][i] << endl;
    }*/
    for(int i = 0; i < part[0].size(); i++){
        for(int j = 0; j <= n; j++){
            if(dp[i][j]){
                dp[i + 1][j + part[0][i]] = true;
                dp[i + 1][j + part[1][i]] = true;
            }
        }
    }
    int index = part[0].size();
    for(int i = (n / 2); i>= 0; i--){
        if(dp[index][i]){
            int a = i;
            int b = n - i;
            int ans = a * (a - 1) / 2 + b * (b - 1) / 2;
            cout << ans << endl;
            return 0;
        }
    }
    return 0;
}


Measured memory_bytes: 2816