#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <unordered_map>
using namespace std;

#define REP(i, s) for (int i = 0; i < s; ++i)
#define ALL(v) (v.begin(), v.end())
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ EACH(it, P) { s << "<" << *it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }


const int MAX = 2100;
bool iscon[2100][2100];

vector<vector<int> > G;
int N, M;

typedef pair<int,int> pint;
vector<pint> nums;

const int LEFT = 0;
const int RIGHT = 1;
int dir[MAX];

bool ok = true;
vector<int> le, ri;
void dfs(int v, int tdir) {
  dir[v] = tdir;
  if (tdir == LEFT) le.push_back(v);
  else ri.push_back(v);
  for (auto e : G[v]) {
	if (dir[e] == -1) {
	  dfs(e, 1 - tdir);
	}
	else if (dir[e] != 1 - tdir) {
	  ok = false;
	  return;
	}
  }
}


bool dp[MAX][MAX];

int main() {
  while (cin >> N >> M) {
	for (int i = 0; i < MAX; ++i) for (int j = 0; j < MAX; ++j) iscon[i][j] = 1;
	for (int i = 0; i < M; ++i) {
	  int a, b;
	  cin >> a >> b; --a, --b;
	  iscon[a][b] = iscon[b][a] = 0;
	}
	
	G.clear(); G.resize(N);
	for (int i = 0; i < N; ++i) {
	  for (int j = 0; j < N; ++j) {
		if (i == j) continue;
		if (iscon[i][j]) G[i].push_back(j);
	  }
	}
	//COUT(G);

	
	
	nums.clear();
	for (int i = 0; i < MAX; ++i) dir[i] = -1;
	ok = true;
	for (int v = 0; v < N; ++v) {
	  if (dir[v] != -1) continue;
	  le.clear(); ri.clear();
	  dfs(v, LEFT);
	  nums.push_back(pint(le.size(), ri.size()));
	}

	//COUT(nums);

	if (!ok) cout << -1 << endl;
	else {
	  for (int i = 0; i < MAX; ++i) for (int j = 0; j < MAX; ++j) dp[i][j] = 0;
	  dp[0][0] = true;
	  for (int i = 0; i <= (int)nums.size(); ++i) {
		int u = nums[i].first;
		int v = nums[i].second;

		//for (int j = 0; j <= N; ++j) if (dp[i][j]) cout << pint(i, j) << endl;
		
		if (i == nums.size()) break;
		for (int j = 0; j <= N; ++j) {
		  dp[i+1][j + u] |= dp[i][j];
		  dp[i+1][j + v] |= dp[i][j];
		}
	  }

	  long long a = -1;
	  long long mindif = N;
	  for (int i = 0; i <= N; ++i) {
		if (dp[nums.size()][i]) {
		  if (mindif > abs(i - N/2)) {
			mindif = abs(i - N/2);
			a = i;
		  }
		}
	  }
	  long long b = N-a;

	  //COUT(a); COUT(b);

	  cout << a*(a-1)/2 + b*(b-1)/2 << endl;
		
	}
							
  }
}


















Measured memory_bytes: 9216