#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cassert>
#include <utility>
#include <iomanip>
#include <chrono>
#include <random>
#include <bitset>
using namespace std;
#define sz(x) (int) x.size()
#define unique(x) x.erase(unique(x.begin(), x.end()), x.end())
#define all(a) a.begin(), a.end()
#define sqr(x) ((x) * (x)) 
#define y1 aksjdaskdjksjfksdjf
#define left kdnvldvoiwejifejg
#define right lkdsjflksdjfdjfk
#define prev asdasfsadjkjsdfjs
#define tm aklsjdasjdasjdkdjjf
#define lcm hddalkwjeidjjhasda
#define random_shuffle asdasdd

const int MAXN = 750;

int n, m;
int g[MAXN][MAXN];
vector < pair <int, int> > miss;
bool used[MAXN];
int usedNum = 0;
vector < pair <int, int> > halves;
int dp[MAXN];
int all = 0;
int missP = 0;

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

int main() {

	scanf("%d %d", &n, &m);
  for (int i = 0; i < m; i++) {
    int from, to;
    scanf("%d %d", &from, &to);
    from--; to--;
    g[from][to] = 1;
    g[to][from] = 1;
  }

  if (m == n * (n - 1) / 2) {
    int mn = m;
    for (int i = 0; i <= n; i++) {
      mn = min(mn, i * (i - 1) / 2 + (n - i) * (n - i - 1) / 2);
    }
    cout << mn << endl;
    return 0;
  }

  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (g[i][j] == 0) {
        miss.push_back({i, j});
        // cerr << "MISS " << i << " " << j << endl;
      }
    }
  }

  while (true) {
    while (missP < sz(miss) && (used[miss[missP].first] || used[miss[missP].second])) {
      missP++;
    }
    if (missP == sz(miss)) {
      all = n - usedNum;
      break;
    }

    vector <int> a = {miss[missP].first}, b = {miss[missP].second};
    used[a[0]] = true; used[b[0]] = true;
    usedNum += 2;
    missP++;

    int ap = 0, bp = 0;
    while (ap < sz(a) || bp < sz(b)) {
      if (ap < sz(a)) {
        int cur = a[ap];
        ap++;
        for (int i = 0; i < n; i++) {
          if (!used[i] && g[cur][i] == 0) {
            used[i] = true;
            usedNum++;
            b.push_back(i);
          }
        }
      } else {
        int cur = b[bp];
        bp++;
        for (int i = 0; i < n; i++) {
          if (!used[i] && g[cur][i] == 0) {
            used[i] = true;
            usedNum++;
            a.push_back(i);
          }
        }
      }
    }

    for (int i = 0; i < sz(a); i++) {
      for (int j = i + 1; j < sz(a); j++) {
        if (g[a[i]][a[j]] == 0) {
          bad();
        }
      }
    }
    for (int i = 0; i < sz(b); i++) {
      for (int j = i + 1; j < sz(b); j++) {
        if (g[b[i]][b[j]] == 0) {
          bad();
        }
      }
    }

    halves.push_back({sz(a), sz(b)});
    // cerr << sz(a) << " " << sz(b) << " " << sz(a) * (sz(a) - 1) / 2 << " " << sz(b) * (sz(b) - 1) / 2 << endl;
  }

  dp[0] = 1;
  for (int i = 0; i < sz(halves); i++) {
    int a = halves[i].first, b = halves[i].second;
    for (int j = n; j >= 1; j--) {
      if (j >= a && dp[j - a] == i + 1) {
        dp[j] = i + 2;
      }
      if (j >= b && dp[j - b] == i + 1) {
        dp[j] = i + 2;
      }
    }
  }

  int ans = m;

  // cerr << all << endl;

  for (int i = 0; i <= n; i++) {
    if (dp[i] != sz(halves) + 1) {
      continue;
    }
    for (int j = 0; j <= all; j++) {
      int a = i + j; 
      int b = n - a;

      // cerr << a << " " << b << " " << a * (a - 1) / 2 + b * (b - 1) / 2 << endl;

      ans = min(ans, a * (a - 1) / 2 + b * (b - 1) / 2);
    }
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 2940