#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
using ll = long long;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-8;
const int MOD = 1000000007;
// const int MOD = 998244353;
const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};
const int dy8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx8[] = {0, -1, -1, -1, 0, 1, 1, 1};
template <typename T, typename U> inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; }
template <typename T, typename U> inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; }
struct IOSetup {
  IOSetup() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
  }
} iosetup;

struct UnionFind {
  UnionFind(int n) : data(n, -1) {}

  int root(int ver) { return data[ver] < 0 ? ver : data[ver] = root(data[ver]); }

  bool unite(int u, int v) {
    u = root(u);
    v = root(v);
    if (u == v) return false;
    if (data[u] > data[v]) swap(u, v);
    data[u] += data[v];
    data[v] = u;
    return true;
  }

  bool same(int u, int v) { return root(u) == root(v); }

  int size(int ver) { return -data[root(ver)]; }

private:
  vector<int> data;
};

using CostType = bool;
struct Edge {
  int src, dst; CostType cost;
  Edge(int src, int dst, CostType cost = 0) : src(src), dst(dst), cost(cost) {}
  inline bool operator<(const Edge &x) const {
    return cost != x.cost ? cost < x.cost : dst != x.dst ? dst < x.dst : src < x.src;
  }
  inline bool operator<=(const Edge &x) const { return !(x < *this); }
  inline bool operator>(const Edge &x) const { return x < *this; }
  inline bool operator>=(const Edge &x) const { return !(*this < x); }
};

bool is_bipartite(const vector<vector<Edge> > &graph, vector<int> &color) {
  int n = graph.size();
  color.assign(n, 0);
  function<bool(int, int)> dfs = [&](int ver, int now) {
    color[ver] = now;
    for (const Edge &e : graph[ver]) {
      if (color[e.dst] == now || (color[e.dst] == 0 && !dfs(e.dst, -now))) return false;
    }
    return true;
  };
  REP(i, n) {
    if (color[i] == 0 && !dfs(i, 1)) return false;
  }
  return true;
}

int main() {
  int n, m; cin >> n >> m;
  int ans = m;
  vector<vector<bool> > graph(n, vector<bool>(n, false));
  while (m--) {
    int a, b; cin >> a >> b; --a; --b;
    graph[a][b] = graph[b][a] = true;
  }
  UnionFind uf(n);
  vector<vector<int> > com(n);
  REP(i, n) REP(j, n) {
    if (i != j && !graph[i][j]) {
      uf.unite(i, j);
      com[i].emplace_back(j);
      // cout << i << ' ' << j << '\n';
    }
  }
  vector<bool> dp(n + 1, false);
  dp[0] = true;
  map<int, vector<int> > root;
  REP(i, n) root[uf.root(i)].emplace_back(i);
  for (auto &pr : root) {
    const vector<int> &vers = pr.second;
    int m = vers.size();
    // REP(i, m) cout << vers[i] << " \n"[i + 1 == m];
    map<int, int> mp;
    REP(i, m) mp[vers[i]] = i;
    vector<vector<Edge> > sub(m);
    REP(i, m) for (int e : com[vers[i]]) {
      // cout << vers[i] << ' ' << e << '\n';
      sub[mp[vers[i]]].emplace_back(mp[vers[i]], mp[e]);
    }
    vector<int> color;
    if (!is_bipartite(sub, color)) {
      cout << "-1\n";
      return 0;
    }
    int cnt = 0;
    REP(i, m) cnt += color[i] == 1;
    // cout << cnt << ' ' << m << '\n';
    vector<bool> nx(n + 1, false);
    REP(i, n + 1) {
      if (dp[i]) {
        if (i + cnt <= n) nx[i + cnt] = true;
        if (i + m - cnt <= n) nx[i + m - cnt] = true;
      }
    }
    dp.swap(nx);
  }
  REP(i, n + 1) {
    if (dp[i]) {
      // cout << i << '\n';
      chmin(ans, i * (i - 1) / 2 + (n - i) * (n - i - 1) / 2);
    }
  }
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 11648