//#pragma GCC optimize ("-O3","unroll-loops")
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<time.h>
#include <random>

using namespace std;

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n-1;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m-1;i >= n;i--)
#define SORT(v, n) sort(v, v+n)
#define VSORT(v) sort(v.begin(), v.end())
#define REVERSE(v,n) reverse(v,v+n)
#define VREVERSE(v) reverse(v.begin(), v.end())
#define ll long long
#define pb push_back
#define print(x) cout<<x<<'\n'
#define pe(x) cout<<x<<" "
#define lb lower_bound
#define ub upper_bound
#define all(x) (x).begin(), (x).end()
#define print_space(v) REP(i,v.size())cout << v[i] << ((i == v.size() - 1) ? "\n" : " ")
#define int long long
template<typename T1, typename T2> inline void chmin(T1 & a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
typedef pair<int, int>P;
const int MOD = 1e9 + 7; const int MAX = 200060;
const double pi = acos(-1); const double EPS = 1e-12;
const ll INF = 1e18;

set<int>G[707];
bool used[707];
int N, M;
set<int>st[2];
set<int>rem;
bool ok = true;
void no() {
	print(-1); exit(0);
}
vector<int>opposite(int x,int c,set<int>&rem) {
	vector<int>v;
	int c2 = (c + 1) % 2;
	REP(i, N) {
		if (i == x)continue;
		
		if (G[x].find(i) == G[x].end()) {
			//pe(i);
			if (st[c].find(i) != st[c].end())ok = false;
			else if (used[i])continue;
			//print("here");
			if (st[c2].find(i) != st[c2].end())continue;
			v.push_back(i);
			st[c2].insert(i); rem.erase(i);
		}
	}
	//cout << endl;
	return v;
}
bool complete(set<int>& rem) {
	for (auto x : rem) {
		for (auto y : rem) {
			if (x == y)continue;
			if (G[x].find(y) == G[x].end())return false;
		}
	}
	return true;
}
int N1, N2;
void func(set<int>rem) {
	int n = rem.size();
	if (complete(rem)) {
		
		REP(i, n) {
			if (N1 < N2)N1++; else N2++;
		}
	}
	else {
		int mn = INF, id = 0;
		for (auto x : rem) {
			if (G[x].size() < mn) {
				mn = G[x].size();
				id = x;
			}
		}
		queue<int>que[2]; que[0].push(id);
		st[0].clear(); st[1].clear();
		used[id] = true;
		rem.erase(id);
		st[0].insert(id);
		REP(i, 2 * n) {
			int c = i % 2;
			int c2 = (i + 1) % 2;
			if (que[c].empty() && que[c2].empty()) {
				int max_n = max(st[0].size(), st[1].size()), min_n = min(st[0].size(), st[1].size());
				if (N1 < N2) {
					N1 += max_n; N2 += min_n;
				}
				else {
					N1 += min_n; N2 += max_n;
				}
				func(rem);
				return;
			}
			while (!que[c].empty()) {
				int now = que[c].front();
				for (auto nxt : st[c]) {
					if (nxt == now)continue;
					if (G[now].find(nxt) == G[now].end())no();
				}
				que[c].pop();
				used[now] = true;
				vector<int>v = opposite(now, c,rem);
				if (!ok)no();
				for (auto x : v) {
					que[c2].push(x);
				}
			}
		}
	}
}

void solve() {
	cin >> N >> M;
	REP(i, M) {
		int u, v; cin >> u >> v; u--, v--;
		G[u].insert(v);
		G[v].insert(u);
	}
	
	int id = 0, mn = INF;
	REP(i, N){
		rem.insert(i);
		if (G[i].size() < mn) {
			mn = G[i].size();
			id = i;
		}
	}
	func(rem);
	ll ans = 0;
	ans += N1 * (N1 - 1) / 2 + N2 * (N2 - 1) / 2;
	print(ans);
}

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

	solve();
}

Measured memory_bytes: 23296