#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int read(){
	int x=0,w=1;
	char ch=0;
	while (ch<'0' || ch>'9'){
		  if (ch=='-') w=-1;
		  ch=getchar();
	}
	while (ch<='9' && ch>='0'){
		  x=(x<<1)+(x<<3)+ch-'0';
		  ch=getchar();
	}
	return x*w;
}
const int N=1e3+5;
int n,m,vis[N],ans;
int a[N][N];
int cnt[2],flag;
int sz[N][2],tot;
int dp[N][N];
void dfs(int x,int fa,int c){
	if (flag) return;
	vis[x]=c;
	cnt[c]++;
	for (int i=1;i<=n;++i)
		if (a[x][i] && i!=fa){
			if (vis[i]==vis[x]) flag=1;
			if (vis[i]==-1) dfs(i,x,c^1);
		}
}
int main(){
	n=read();m=read();
	for (int i=1;i<=n;++i)
		a[i][i]=1;
	for (int i=1;i<=m;++i){
		int u=read(),v=read();
		a[u][v]=a[v][u]=1;
	}
	for (int i=1;i<=n;++i)
		for (int j=1;j<=n;++j)
			a[i][j]^=1;
	memset(vis,-1,sizeof(vis));
	for (int i=1;i<=n;++i){
		if (vis[i]==-1){
			cnt[0]=cnt[1]=0;
			dfs(i,0,1);
			sz[++tot][0]=cnt[0];
			sz[tot][1]=cnt[1];
		}
	}
	dp[0][0]=1; 
	for (int i=1;i<=tot;++i){
		for (int j=0;j<=n;++j){
			if (dp[i-1][j]){
				dp[i][j+sz[i][0]]=1;
				dp[i][j+sz[i][1]]=1;	
			}
		}
	}
	int ans=-1;
	for (int i=n>>1;i>=0;--i)
		if (dp[tot][i]){
			ans=i;
			break;
		}
	ans=(ans*ans)+((n-ans)*(n-ans))-n;
	ans>>=1;
	if (flag) ans=-1;
	printf("%d\n",ans);
	return 0;
}
