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

#define rep(i, m, n) for(int(i) = (int)(m); i < (int)(n); ++i)
#define rep2(i, m, n) for(int(i) = (int)(n)-1; i >= (int)(m); --i)
#define REP(i, n) rep(i, 0, n)
#define REP2(i, n) rep2(i, 0, n)
#define all(hoge) (hoge).begin(), (hoge).end()
#define en '\n'
using ll = long long;
using ull = unsigned long long;
template <class T>
using vec = vector<T>;
template <class T>
using vvec = vector<vec<T>>;
typedef pair<ll, ll> P;
constexpr long long INF = 1LL << 60;
constexpr int INF_INT = 1 << 25;
constexpr long long MOD = (ll)1e9 + 7;
//constexpr long long MOD = 998244353LL;
//constexpr long long MOD = 1777777777LL;
using ld = long double;
using tp = tuple<ll, ll, ll>;
static const ld pi = 3.141592653589793L;
typedef vector<ll> Array;
typedef vector<Array> Matrix;

template <class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

// long dobule
struct Edge {
    ll to, cap, rev;
    Edge(ll _to, ll _cap, ll _rev) {
        to = _to;
        cap = _cap;
        rev = _rev;
    }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

void add_edge(Graph &G, ll from, ll to, ll cap, bool revFlag, ll revCap) {
    G[from].push_back(Edge(to, cap, (ll)G[to].size()));
    if(revFlag)
        G[to].push_back(Edge(from, revCap, (ll)G[from].size() - 1));
}

void solve() {
    ll n, m;
    cin >> n >> m;

    vec<P> res;
    REP(i, m) {
        ll a, b;
        cin >> a >> b;
        a--;
        b--;
        res.push_back({a, b});
        res.push_back({b, a});
    }
    if(m == n * (n - 1) / 2) {
        cout << m - n / 2 * (n / 2 + n % 2) << en;
        return;
    }

    sort(all(res));

    Graph g(n);
    REP(i, n) {
        REP(j, n) {
            if(i == j)
                continue;
            if(!binary_search(all(res), make_pair((ll)i, (ll)j))) {
                add_edge(g, i, j, 1, false, 0);
            }
        }
    }

    vec<ll> used(n, -1);
    ll con0 = 0;
    ll con1 = 0;

    auto dfs = [&](auto &&self, int v, int p) -> bool {
        if(used[v])
            con1++;
        else
            con0++;
        for(auto e : g[v]) {
            if(e.to == p)
                continue;
            if(used[e.to] == -1) {
                used[e.to] = !used[v];
                if(!self(self, e.to, v)) {
                    return false;
                }
            } else {
                if(used[e.to] == used[v]) {
                    return false;
                }
            }
        }
        return true;
    };

    vec<P> con;
    REP(i, n) {
        if(used[i] != -1)
            continue;
        con0 = 0;
        con1 = 0;
        used[i] = 0;
        if(!dfs(dfs, i, -1)) {
            cout << -1 << en;
            return;
        }
        con.push_back({con0, con1});
    }

    vvec<ll> dp(con.size() + 1, vec<ll>(n + 1, 0));
    dp[0][0] = 1;

    REP(i, con.size()) {
        REP(j, n) {
            if(!dp[i][j])
                continue;
            dp[i + 1][j + con[i].first] = 1;
            dp[i + 1][j + con[i].second] = 1;
        }
    }

    ll num = n;
    REP(i, n) {
        if(dp[con.size()][i])
            chmin(num, max(n - i, (ll)i));
    }

    cout << num * (num - 1) / 2 + (n - num) * (n - num - 1) / 2 << en;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    /*
    ll t;
    cin >> t;
    while(t--)*/
    solve();

    return 0;
}


Measured memory_bytes: 17304