#include <stdio.h>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
#define mp make_pair
#define pb push_back
const int N=705;
vector<int> E[N];
set<pair<int,int> > has;
vector<pair<int,int> > sz;
int cnt[2];
int was[N];
bool bad;
void DFS(int u)
{
	cnt[was[u]]++;
	for(int i=0;i<E[u].size();i++)
	{
		int v=E[u][i];
		if(was[v]==-1) was[v]=was[u]^1,DFS(v);
		else
		{
			if(was[u]==was[v]) bad=1;//,printf("(%i %i)\n",u,v);
		}
	}
}
bool dp[N][N];
int main()
{
	int u,v,n,m,i,j;
	scanf("%i %i",&n,&m);
	while(m--) scanf("%i %i",&u,&v),has.insert(mp(u,v)),has.insert(mp(v,u));
	for(i=1;i<=n;i++)
	{
		for(j=i+1;j<=n;j++)
		{
			if(!has.count(mp(i,j)))
			{
				E[i].pb(j);
				E[j].pb(i);
				//printf("->%i %i\n",i,j);
			}
		}
	}
	sz.pb(mp(-1,-1));
	for(i=1;i<=n;i++) was[i]=-1;
	for(i=1;i<=n;i++) if(was[i]==-1)
	{
		cnt[0]=cnt[1]=0;
		was[i]=1;DFS(i);
		sz.pb(mp(cnt[0],cnt[1]));
	}
	if(bad) return printf("-1\n"),0;
	int goal=n/2;
	dp[0][0]=1;
	for(i=1;i<sz.size();i++)
	{
		for(j=0;j<=goal;j++)
		{
			dp[i][j]=(j>=sz[i].first?dp[i-1][j-sz[i].first]:0)|(j>=sz[i].second?dp[i-1][j-sz[i].second]:0);
		}
	}
	int ans=0;
	for(i=0;i<=goal;i++) if(dp[sz.size()-1][i]) ans=i;
	int ret=n-ans;
	int out=ans*(ans-1)/2+ret*(ret-1)/2;
	printf("%i\n",out);
	return 0;
}