#include<bits/stdc++.h>
#define $ for(i=0;i++<n;)
using namespace std;
int n,m,g[777][777],C[777],t[777][2],A,c,i,j;
vector<int>G[777];
bitset<777>P(1);
int f(int u,int c){
	int t=1,i=0;
	for(C[u]=c;i<G[u].size();i++)t&=C[G[u][i]]<0?f(G[u][i],c^1):C[G[u][i]]^c;
	return t;
}
int main(){
	for(cin>>n>>m;cin>>i>>j;)g[i][j]=g[j][i]=1;
	$ for(j=i;j++<n;)if(!g[i][j])G[i].push_back(j),G[j].push_back(i);
	$ C[i]=-1;
	$ A+=C[i]<0&&!f(i,c+=2);
	A=A?-1:1e9;
	$ t[C[i]/2][C[i]%2]++;
	$ P=P<<t[i][0]|P<<t[i][1];
	$ A=min(A,P[i]?i*(i-1)/2+(n-i)*(n-i-1)/2:A);
	cout<<A;
}
