#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define EB emplace_back
#define MP make_pair
#define all(o) (o).begin(), (o).end()
#define mset(m,v) memset(m,v,sizeof(m))
#define fr(i,n) for(lli i=0;i<n;++i)
#define rep(i,a,b) for(lli i=a;i<=b;++i)
#define remin(a,b) (a=min((a),(b)))
#define remax(a,b) (a=max((a),(b))) 
#define endl '\n'
typedef long long int lli;    typedef long double ld;
typedef pair< lli,lli > ii;   typedef vector<lli> vi;
typedef vector<ii> vii;       typedef vector<vi> graph;
lli MOD=1000000007;           long double EPS=1e-9;
#define debarr(a,n) cout<<#a<<" : ";for(int i=0;i<n;i++) cerr<<a[i]<<" "; cerr<<endl;
#define debmat(mat,row,col) cout<<#mat<<" :\n";for(int i=0;i<row;i++) {for(int j=0;j<col;j++) cerr<<mat[i][j]<<" ";cerr<<endl;}
#define pr(...) dbs(#__VA_ARGS__, __VA_ARGS__)
template <class S, class T>ostream& operator <<(ostream& os, const pair<S, T>& p) {return os << "(" << p.first << ", " << p.second << ")";}
template <class T>ostream& operator <<(ostream& os, const vector<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class T>ostream& operator <<(ostream& os, const unordered_set<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class S, class T>ostream& operator <<(ostream& os, const unordered_map<S, T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class T>ostream& operator <<(ostream& os, const set<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class T>ostream& operator <<(ostream& os, const multiset<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class S, class T>ostream& operator <<(ostream& os, const map<S, T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class T> void dbs(string str, T t) {cerr << str << " : " << t << "\n";}
template <class T, class... S> void dbs(string str, T t, S... s) {int idx = str.find(','); cerr << str.substr(0, idx) << " : " << t << ","; dbs(str.substr(idx + 1), s...);}
template <class T> void prc(T a, T b) {cerr << "["; for (T i = a; i != b; ++i) {if (i != a) cerr << ", "; cerr << *i;} cerr << "]\n";}
lli binpow(lli b,lli p,lli mod){lli ans=1;for(;p;p>>=1){if(p&1)ans=ans*b%mod;b=b*b%mod;}return ans;}
 
 
void pre(){
 
}
 
lli n,m;
vi vis;
graph g;
bool pos=1;
 
int aa,bb;
 
void dfs(int nn,int cc){
	vis[nn]=cc;
	if(cc==1)aa++;
	else bb++;
	for(auto v:g[nn]){
		if(!vis[v]){
			dfs(v,3^cc);
		}
		else{
			if(vis[v]+vis[nn]!=3)pos=0;
		}
	}
}	
 
void solve(){
	cin>>n>>m;
	g.resize(n+1);
	map<ii,int> mp;
	fr(i,m){
		int a,b;
		cin>>a>>b;
		if(a>b)swap(a,b);
		mp[MP(a,b)]=1;
	}
	rep(i,1,n){
		rep(j,i+1,n){
			if(mp.find(MP(i,j))==mp.end()){
				g[i].EB(j);
				g[j].EB(i);
			}
		}
	}
	vis.assign(n+1,0);
	vii vals;
	rep(i,1,n){
		if(!vis[i]){
			aa=0;
			bb=0;
			dfs(i,1);
			vals.EB(MP(aa,bb));
		}
	}
	if(!pos){
		cout<<-1<<endl;return;
	}
	bitset<701> dp;
	dp.set(0);
	fr(i,vals.size()){
		dp=dp<<vals[i].S|dp<<vals[i].F;
	}
	lli ans=MOD*MOD;
	rep(i,0,n){
		if(dp[i]){	
			remin(ans,i*(i-1)/2+(n-i)*(n-i-1)/2);
		}
	}
	if(ans<MOD*MOD)cout<<ans<<endl;
	else cout<<-1<<endl;
}
 
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	pre();
	int t=1;
	//cin>>t;
	for(int i=1;i<=t;i++){
		//cout<<"Case #"<<i<<": ";
		solve();
	}
}


Measured memory_bytes: 15616