#include <bits/stdc++.h>
using namespace std;
//#include <boost/multiprecision/cpp_int.hpp>
//using multiInt = boost::multiprecision::cpp_int;

using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<typename Q_temp>
using smaller_queue = priority_queue <Q_temp, vector<Q_temp>, greater<Q_temp> >;

const ll MOD = (ll) 998244353;
const int INF = (int) 1e9;
const ll LINF = (ll) 4e18;
const double PI = acos(-1.0);

#define REP(i,m,n) for(ll i = m; i < (ll)(n); ++i)
#define rep(i,n) REP(i, 0, n)
#define MP make_pair
#define MT make_tuple
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x_) cerr << #x_ << ":" << x_ << endl;
#define dbg2(x_) for(auto a_ : x_) cerr << a_ << " "; cerr << endl;
#define dbg3(x_ , sx_) rep(i, sx_) cerr << x_[i] << " "; cerr << endl;
vector<int> Dx = {0, 0, -1, 1, -1, 1, -1, 1, 0};
vector<int> Dy = {1, -1, 0, 0, -1, -1, 1, 1, 0};

inline ll CEIL(ll a, ll b) {
    return (a + b - 1) / b;
}

void finish() {
    cout << -1 << endl;
    exit(0);
}

//------------------------------------------------------

class UnionFind {
private:
    vector<int> par, sizes;

public:

    UnionFind(int n = 200010) : par(n), sizes(n, 1) {
        rep(i, n) par[i] = i;
    }

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

    void unite(int x, int y) {
        x = root(x);
        y = root(y);
        if (x == y) return;
        if (sizes[x] < sizes[y]) swap(x, y);
        par[y] = x;
        sizes[x] += sizes[y];
    }

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

    int size(int x) {
        return sizes[root(x)];
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(20) << setiosflags(ios::fixed);

    int n, m;
    cin >> n >> m;
    bool E_matrix[700][700];
    rep(i, n) rep(j, n) E_matrix[i][j] = (i != j); //補グラフの隣接行列

    rep(i, m) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        E_matrix[a][b] = E_matrix[b][a] = false;
    }

    vector<int> E[700]; //補グラフの隣接リスト

    rep(i, n) rep(j, n) {
        if (E_matrix[i][j]) E[i].push_back(j);
    }

    UnionFind uf(700);
    pii block[700] = {};

    int parity[700];
    rep(i, n) parity[i] = -1;

    rep(i, n) {
        if (parity[i] != -1) continue;
        parity[i] = 0;
        block[i].first++;
        queue<int> que;
        que.push(i);
        while (!que.empty()) {
            int q = que.front();
            que.pop();
            for (auto to : E[q]) {
                if (parity[to] == -1) {
                    uf.unite(q, to);
                    parity[to] = !parity[q];
                    if (parity[to]) block[uf.root(to)].second++;
                    else block[uf.root(to)].first++;
                    que.push(to);
                } else if (parity[q] == parity[to]) {//二部グラフではないとき
                    finish();
                }
            }
        }
    }

    //rep(i, n) cout << parity[i] << endl;

    vector<pii> v; //連結成分のサイズ

    rep(i, n) {
        if (block[i] != MP(0, 0)) v.push_back(block[i]);
    }

    //for (auto p : v) cerr << p.first << " " << p.second << endl;

    int dp_n = v.size();
    bool dp[710][710] = {};
    dp[0][0] = true;

    rep(i, dp_n) {

        rep(j, 710) {
            if (dp[i][j]) dp[i + 1][j + v[i].first] = true;
            if (dp[i][j]) dp[i + 1][j + v[i].second] = true;
        }
    }

    int ans = INF;

    rep(i, 360) {
        if (dp[dp_n][i]) {
            int a = i;
            int b = n - i;
            ans = min(ans, a * (a - 1) / 2 + b * (b - 1) / 2);
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3584