#include <bits/stdc++.h>
#define typeof(x) __typeof__(x)
#define int long long int
#define double long double
#define mod(x) ((x % MOD) + MOD) % MOD
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);--i)

#define ALL(c) (c).begin(),(c).end()
#define SZ(c) (int)((c).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define SORT(c) sort(ALL(c))
#define LB(c,x) (int)(lower_bound(ALL(c),x)-(c).begin())
#define UB(c,x) (int)(upper_bound(ALL(c),x)-(c).begin())
#define COUNT(c,x) UB(c,x)-LB(c,x)
#define UNIQUE(c) SORT(c); (c).erase(unique(ALL(c)),(c).end());
#define COPY(c1,c2) copy(ALL(c1),(c2).begin())
#define EXIST(s,e) (s).find(e)!=(s).end()
#define PB push_back
#define MP make_pair
#define vec vector

#define dump(x)  cerr << #x << " = " << (x) << endl;

using namespace std;

typedef pair<int,int> P;
struct edge { int to, cost; };

const int INF = 1e18;
const int MOD = 1e9+7;

template<typename T> ostream& operator << (ostream& s, const vector<T>& v) {
   s << "[";
   for (int i = 0; i < v.size(); i++) { s << v[i]; if (i < v.size() - 1) s << " "; }
   s << "]";
   return s;
}
template<typename T1, typename T2> ostream& operator << (ostream& s, const pair<T1,T2>& p) {
   s << "(" << p.first << "," << p.second << ")";
   return s;
}

bool bfs(const vec<vec<int>>& G, vec<int>& color, int s, int& S, int& T) {
   queue<P> que;
   if (color[s] == 0) {
      que.push(MP(s,1));
      color[s] = 1;
      S++;
   }
   while (!que.empty()) {
      P p = que.front(); que.pop();
      int i = p.first, c = (-1) * p.second;
      rep(j, 0, G[i].size()) {
         int to = G[i][j];
         if (color[to] == 0) {
            color[to] = c;
            que.push(MP(to,c));
            if (c == 1) {
               S++;
            } else {
               T++;
            }
         } else if (color[to] != c) {
            return false;
         }
      }
   }
   return true;
}

signed main()
{
   // string filename; cin >> filename;
   // std::ifstream in(filename);
   // std::cin.rdbuf(in.rdbuf());

   int N, M; cin >> N >> M;
   vec<vec<bool>> c(N,vec<bool>(N,true));
   int a, b;
   rep(i, 0, M) {
      cin >> a >> b; a--; b--;
      c[a][b] = false;
      c[b][a] = false;
   }

   vec<vec<int>> G(N,vec<int>());
   rep(i, 0, N) {
      rep(j, 0, N) {
         if (i != j && c[i][j]) {
            G[i].PB(j);
         }
      }
   }

   vec<int> color(N,0);
   vec<P> list;
   rep(i, 0, N) {
      if (color[i] == 0) {
         int S = 0, T = 0;
         if (!bfs(G, color, i, S, T)) {
            cout << -1 << endl;
            return 0;
         }
         list.PB(MP(S,T));
      }
   }
   int len = SZ(list);

   vec<vec<bool>> dp(len+1,vec<bool>(N+1,false));
   dp[0][0] = true;
   rep(i, 0, len) {
      int S = list[i].first, T = list[i].second;
      rep(j, 0, N+1) {
         if (j-S >= 0 && j-T >= 0) {
            dp[i+1][j] = dp[i][j-S] | dp[i][j-T];
         } else if (j-S >= 0) {
            dp[i+1][j] = dp[i][j-S];
         } else if (j-T >= 0) {
            dp[i+1][j] = dp[i][j-T];
         } else {
            dp[i+1][j] = false;
         }
      }
   }

   rrep(j, 0, N/2+1) {
      if (dp[len][j]) {
         cout << j*(j-1)/2 + (N-j)*(N-j-1)/2 << endl;
         return 0;
      }
   }

   return 0;
}


Measured memory_bytes: 6016