#include <bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define ALL(a) a.begin(), a.end()
#define RALL(a) a.rbegin(), a.rend()
#define REP(i, a) for (ll i(0), _##i(a); i < _##i; ++i)
#define FOR(i, a, b) for (ll i(a), _##i(b); i <= _##i; ++i)

#ifdef LOCAL
#define _NTH_ARG(_1, _2, _3, _4, _5, _6, N, ...) N
#define _FE_1(_CALL, x) _CALL(x)
#define _FE_2(_CALL, x, ...) _CALL(x) _FE_1(_CALL, __VA_ARGS__)
#define _FE_3(_CALL, x, ...) _CALL(x) _FE_2(_CALL, __VA_ARGS__)
#define _FE_4(_CALL, x, ...) _CALL(x) _FE_3(_CALL, __VA_ARGS__)
#define _FE_5(_CALL, x, ...) _CALL(x) _FE_4(_CALL, __VA_ARGS__)
#define _FE_6(_CALL, x, ...) _CALL(x) _FE_5(_CALL, __VA_ARGS__)
#define FOR_EACH_MACRO(MACRO, ...)                                             \
  _NTH_ARG(__VA_ARGS__, _FE_6, _FE_5, _FE_4, _FE_3, _FE_2, _FE_1)              \
  (MACRO, __VA_ARGS__)
#define watch(x) cerr << "\033[1;32m" #x " = \033[1;34m" << (x) << "\033[0m; ";
#define debug(...)                                                             \
  cerr << "\033[2;31mLine " << __LINE__ << ": \033[0m";                        \
  FOR_EACH_MACRO(watch, __VA_ARGS__)                                           \
  cerr << endl
#else
#define debug(...)
#endif

using namespace std;

template <class T1, class T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
  return os << '{' << p.first << ", " << p.second << '}';
}

template <class T, class = decltype(begin(declval<T>())),
          class = enable_if_t<!is_same<T, string>::value>>
ostream &operator<<(ostream &os, const T &c) {
  os << '[';
  for (auto it = begin(c); it != end(c); ++it)
    os << (it == begin(c) ? "" : ", ") << *it;
  return os << ']';
}
using ll = long long;

void solve() {
  int n, m;
  cin >> n >> m;
  vector<vector<int>> adj(n);
  {
    vector<vector<bool>> mt(n, vector<bool>(n));
    while (m--) {
      int a, b;
      cin >> a >> b, --a, --b;
      mt[a][b] = mt[b][a] = 1;
    }
    REP(i, n) FOR(j, i + 1, n - 1) if (!mt[i][j]) {
      adj[i].EB(j); 
      adj[j].EB(i); 
    }
  }

  vector<int> vis(n, -1);

  auto bfs = [&](int u) -> pair<int,int> {
    queue<int> q;
    vector<int> cc;
    q.push(u);
    pair<int,int> ans;
    while (!q.empty()){
      u = q.front();
      cc.EB(u);
      q.pop();
      if (vis[u] == 0) ++ans.F;
      else ++ans.S;
      for(int v : adj[u]){
        if (vis[v] == -1){
          vis[v] = vis[u] ^ 1;
          q.push(v);
        } else if (vis[v] == vis[u]){
          return {-1, -1};
        }
      }
    }
    return ans;
  };

  vector<pair<int,int>> comp;
  REP(i, n){
    if (vis[i] == -1){
      vis[i] = 0;
      auto p = bfs(i);
      if (p == make_pair(-1, -1)){
        cout << "-1\n";
        return;
      }
      comp.EB(p);
    }
  }
  int k = comp.size();
  vector<int> cur(n + 1);
  cur[0] = 1;
  for(int i = 1; i <= k; ++i){
    vector<int> nxt(n + 1);
    for(int j = 0; j <= n; ++j){
      for(int x : {comp[i - 1].F, comp[i - 1].S}){
        int f = j - x;
        if (f >= 0 && cur[f]){
          nxt[j] = 1;
        }
      }
    }
    swap(cur, nxt);
  }
  const int INF = 1e9;
  int ans = INF;
  for(int i = 0; i <= n; ++i){
    if (cur[i]){
      ans = min(ans, i * (i - 1)/ 2 + (n - i) * (n - i - 1) / 2);
    }
  }
  cout << ans << "\n";
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int T = 1;
  // cin >> T;
  while (T--) {
    solve();
  }
}


Measured memory_bytes: 3200