//実装が重そうな問題はある程度考えてから書く
//初期化を忘れずに（特に二分探索とか）
//コーナーケースを考えて（特に場合分けとか）
//不可解すぎるバグは配列外参照（配列の長さ）を検討
#include <bits/stdc++.h>
#define YES "YES"
#define NO "NO"
#define YESNO OUT(three(solve(),YES,NO))
#define ECHO OUT(solve())
#define three(A,B,C) ((A)?(B):(C))
#define FOR(i,a,b)  for(LL i=(a);i< (LL)(b);i++)
#define EFOR(i,a,b) for(LL i=(a);i<=(LL)(b);i++)
#define RFOR(i,a,b) for(LL i=(a);i>=(LL)(b);i--)
#define REP(i,b) FOR(i,zero,b)
#define EREP(i,b) EFOR(i,zero,b)
#define RREP(i,b) RFOR(i,b,zero)
#define ALL(c) c.begin(),c.end()
#define UNIQUE(c) sort(ALL(c));c.erase(unique(ALL(c)),c.end())
#define MAX(c) (*max_element(ALL(c)))
#define MIN(c) (*min_element(ALL(c)))
#define MP make_pair
#define FI first
#define SE second
#define SI(x) (LL(x.size()))
#define PB push_back
#define DEBUG(a) OUT(a)
#define DEBUG2(a,b) OUT2(a,b)
#define cat cout << __LINE__ << endl
#define OUT(a) cout << (a) << endl
#define OUT2(a,b) cout << (a) <<" "<<(b) << endl
#define int LL
#define zero 0LL
using namespace std;
template<typename T> inline void maximize(T &a,T b){a=max(a,b);}
template<typename T> inline void minimize(T &a,T b){a=min(a,b);}
template<typename T> inline bool middle(T a,T b,T c){return b<=a && a<=c;}
typedef long long LL;
typedef double ld;
typedef LL ut;
typedef vector<ut> VI;
typedef vector<VI> VII;
typedef pair<ut,ut> pr;
typedef pair<ut,pr> ppr;
typedef vector<pr> Vpr;
typedef vector<ppr> Vppr;
typedef priority_queue<pr,Vpr,greater<pr> > PQ;
inline void outputVI(VI x){REP(i,SI(x)){cout << three(i," ","") << x[i];}OUT("");}
const int SIZE1=5*1e5+1000;
const int SIZE2=5010;
const int SIZE3=400;
const int SIZE=2000;
const LL p=7+1e9;
const LL INF=1LL<<60;
const long double EPS=1e-7;
string s;
ut N,M,K,X,L,Y;
// ut A,B,C,D,E,F,G,H,I,J,O,P,Q,R,T,U;
VI edges[SIZE];
LL vals[SIZE],nums[SIZE],maps[SIZE2][SIZE2],answer=zero;
VI v[SIZE];
////////////////////////////////////////////////////////////////////////////////////////////
class UnionFind{
 
	vector<int> unions,talls,sents,dists,sizes;
	int size;
public:
	UnionFind(){}
	UnionFind(int size):size(size){
		init();
	}
	void init(){
	 	unions=vector<int>(size);
	 	talls=vector<int>(size);
	 	sents=vector<int>(size);
	 	dists=vector<int>(size);
	 	sizes=vector<int>(size);
		FOR(i,0,size){
			unions[i]=i;
			sents[i]=0;
			sizes[i]=1;
//			ns[i].PB(pr(0,1));
			talls[i]=1;
		}
	}
	int find(int x,int t=0){
		if(unions[x]==x || sents[x]>t) return x;
		return find(unions[x],t);
 
	}
	int minisize(int x){
		if(x==unions[x]) return sizes[x];
		return minisize(find(x));
	}
	bool isFriend(int a,int b,int t=0){
		return find(a,t)==find(b,t);	
	}
	void unite(int a,int b,int t=0){
		if(isFriend(a,b,t)) return;
		a=find(a,t);
		b=find(b,t);
		if(talls[a]<talls[b]) unite(b,a,t);
		else{
 			sizes[a]+=sizes[b];
			sents[b]=t;
			talls[a]=max(talls[a],talls[b]+1);
			unions[b]=a;
			dists[b]=1;
//			ns[a].PB(pr(t,ns[b].back().second+ns[a].back().second));
		}
	}
};
////////////////////////////////////////////////////////////////////////////////////////////
int sizes[SIZE],types[SIZE];
bool exist[SIZE][SIZE];
int type[SIZE];
UnionFind uf;
void init(){
	
}
int now=2;
bool used[SIZE];
int proc(int i){
	if(uf.find(i)!=i) return 0;
	if(used[i]) return 0;
	if(type[i]==0){
		type[i]=now;
		now+=2;
	}
	used[i]=true;
//	cout << i <<" " << type[i]<< endl;
	for(auto next:v[i]){
	//	cout << next << endl;
		EFOR(j,1,N){
			if(next==j) continue;
			if(!exist[next][j]){
		//		cout << next <<" " << j << endl;
				if(type[uf.find(j)]==type[i]) return -1;
				if(type[uf.find(j)]==0){
					type[uf.find(j)]=type[i]^1;
					proc(uf.find(j));
				}
			}
		}
	}
	return 0;
}
bool able[SIZE*2][SIZE];
LL solve(){
	cin >> N >> M;
	uf=UnionFind(N+1);
	REP(i,M){
		int a,b;
		cin >> a >> b;
		exist[a][b]=true;
		exist[b][a]=true;
	}
	EFOR(i,1,N){
		int last=-1;
		EFOR(j,1,N){
			if(i==j) continue;
			if(!exist[i][j]){
				if(last!=-1){
					uf.unite(last,j);
			//		cout << last <<" " << j<<endl;
				}
				last=j;
			}
			
		}
	}
	EFOR(i,1,N){
		v[uf.find(i)].PB(i);
	}
	EFOR(i,1,N){
	//	cout << i <<" " << v[i].size()<<endl;
		if(proc(i)==-1) return -1;
	}
	EFOR(i,1,N){
		if(uf.find(i)==i){
		//	cout << uf.minisize(i) << " " << type[i] << endl;
			sizes[type[i]]+=uf.minisize(i);
			
		}
		
	}
	int ansA=0,ansB=0;
	able[0][0]=1;
	for(int k=0;k<now;k+=2)
	REP(i,1000){
		able[k+2][i+sizes[k]]|=able[k][i];
		able[k+2][i+sizes[k+1]]|=able[k][i];
	}
	REP(i,N/2+1){
		if(able[now][i]) ansA=i;
	}
	ansB=N-ansA;
	return ansA*(ansA-1)/2+ansB*(ansB-1)/2;
}
signed main(){
	int ans=solve();
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 10624