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

#define NDEBUG
#ifdef DEBUG
#include "../cout11.h"
#undef NDEBUG
#endif
#include <cassert>

typedef long long ll;
typedef long double Double;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<long double> vD;

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))
#define cons make_pair


class UnionFind {
  vector<int> data;
 public:
  UnionFind(int size) : data(size, -1) { }
  bool unionSet(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] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) { return root(x) == root(y); }
  int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
  int size(int x) { return -data[root(x)]; }
};


ll solve(int N,int M,vi& a,vi& b) {
    int mmax = N*(N-1)/2;
    if (M == mmax) {
        int best = 0x7fffffff;
        for (int p=0; p<=N; ++p) {
            int q = N-p;
            int score = p*(p-1)/2 + q*(q-1)/2;
            best = min(best, score);
        }
        return best;
    }

    vvi d(N, vi(N, 1));

    rep(i,N) d[i][i] = 0;
    rep(i,M){
        int u = a[i], v = b[i];
        d[u][v] = d[v][u] = 0;
    }

    // vector<ii> no;
    vvi next(N);
    UnionFind uf(N);
    repC2(u,v,N){
        if (d[u][v]) {
            next[u].pb(v);
            next[v].pb(u);
            uf.unionSet(u,v);
            // no.pb(ii(i,j));
        }
    }

    // 各グループの代表を1人決める
    set<int> groups;
    map<int,vi> group_stat;
    queue<ii> q;
    rep(u,N) {
        int r = uf.root(u);
        if (!found(groups, r)) {
            q.push(ii(u,0));
            groups.insert(r);
            group_stat[r] = vi(2,0);
        }
    }

    vi pm(N,-1);
    while (!q.empty()) {
        int u = q.front().first, f = q.front().second; q.pop();
        if (pm[u] == f) continue;
        else if (pm[u] != -1) return -1;///
        pm[u] = f;
        group_stat[uf.root(u)][f]++;
        // visited[u] = true;
        for (int v: next[u]){
            if (pm[v] == -1 || pm[v] == 1-f) q.push(ii(v,1-f));
            else return -1;
        }
    }
#ifdef DEBUG
    cerr << pm << endl;
    cerr << group_stat << endl;
#endif

    vi dp(N+1, 0);
    dp[0] = 1;
    for (auto a : group_stat){
        int r = a.first;
        int x = a.second[0], y = a.second[1];
        vi dp2(N+1, 0);
        rep(i, N+1) {
            if (dp[i] && i+x<=N) {
                dp2[i+x] = dp[i];
                dp2[i+y] = dp[i];
            }
        }
        dp = dp2;
    }
#ifdef DEBUG
    cerr << dp << endl;
#endif
    int best = 0x7fffffff;
    rep(i,N+1){
        if (!dp[i]) continue;
        best = min(best, i*(i-1)/2 + (N-i)*(N-i-1)/2);
    }
    return best;
}

int main() {
    int N,M; cin >> N >> M;
    vi a(M), b(M);
    rep(i,M) {
        cin >> a[i] >> b[i];
        --a[i]; --b[i];
    }
    cout << solve(N,M,a,b) << endl;
    return 0;
}


Measured memory_bytes: 4992