#include <bits/stdc++.h>
using namespace std;
const int maxn = 700 + 10;
int n, m, tot, ans;
bool M[maxn][maxn], dp[maxn][maxn];
int col[maxn], cnt[maxn][2];
vector<int> E[maxn]; 
void dfs(int x)
{
	if(!col[x]) ++cnt[tot][0];
	else ++cnt[tot][1];
	for(auto v : E[x])
	{
		if(col[v] == -1)
		{
			col[v] = col[x] ^ 1;
			dfs(v);
		}
		else if(col[v] == col[x])
		{
			puts("-1");
			exit(0);
		}
	}
}
int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; ++i)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		M[u][v] = M[v][u] = 1;
	}
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= n; ++j)
			if(i != j && !M[i][j])
				E[i].push_back(j);
	memset(col, -1, sizeof(col));
	for(int i = 1; i <= n; ++i)
		if(col[i] == -1)
		{
			++tot;
			col[i] = 0;
			dfs(i);
		}
	dp[0][0] = 1;
	for(int i = 1; i <= tot; ++i)
		for(int x = 0; x < 2; ++x)
			for(int j = cnt[i][x]; j < maxn; ++j)
				dp[i][j] |= dp[i - 1][j - cnt[i][x]];
	ans = n * (n - 1) / 2;
	for(int j = 0; j < maxn; ++j)
		if(dp[tot][j])
			ans = min(ans, j * (j - 1) / 2 + (n - j) * (n - j - 1) / 2);
	printf("%d\n", ans);
	return 0;
}
	
		
	 