//#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") //Optimization flags
//#pragma GCC option("arch=native","tune=native","no-zero-upper") //Enable AVX
//#pragma GCC target("avx2")  //Enable AVX
#include<bits/stdc++.h>
using namespace std;

#define all(a) begin(a),end(a)
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define sz(x) (int)(x).size()
#define F first
#define S second
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
 
const int mod=998244353;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int mul(int a,int b){
  return ((a)*1ll*(b))%mod;
}
 
void add(int &a,int b){
  a+=b;
  if(a>=mod)a-=mod;
}
 
int sub(int a,int b){
  a-=b;
  if(a<0){
    a+=mod;
  }
  return a;
}
 
int powz(int a,int b){
  int res=1;
  while(b){
    if(b&1){
      res=mul(res,a);
    }
    b/=2;
    a=mul(a,a);
  }
  return res;
}
 
template <typename A, typename B>
istream& operator>>(istream& input,pair<A,B>& x) {
  input>>x.F>>x.S;
  return input;
}
 
template <typename A>
istream& operator>>(istream& input,vector<A>& x) {
  for(auto& i:x)
    input>>i;
  return input;
}
 
template<typename A>
ostream& operator<<(ostream& output,vector<A>& x) {
  for(auto& i:x)
    output<<i<<' ';
  return output;
}
 
const int N=500002;

vi adj[N];
vi adj2[N];
int n;

vector<bool>vis;
vector<int>lef,rig;
int col[705];

bool dfs(int u,int c){
  col[u]=c+1;
  bool flag=true;
  for(auto i:adj[u]){
    if(col[i]==0){
      flag&=dfs(i,c^1);
    }
    if(col[i]==col[u]){
      return false;
    }
  }
  return flag;
}

bool bipartite(){
  bool flag=true;
  for(int i=0;i<n;i++){
    if(col[i]==0){
      flag&=dfs(i,0);
    }
  }
  return flag;
}

bool dp[2][705];

void dfs_2col(int u,int col=0){
  vis[u]=true;
  if(col==0){
    lef.pb(u);
  }
  else{
    rig.pb(u);
  }
  for(auto i:adj[u]){
    if(!vis[i]){
      dfs_2col(i,col^1);
    }
  }
}

void solve(){
  int m;
  cin>>n>>m;
  set<pii>st;
  for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
      st.insert({i,j});
    }
  }
  set<pii>st2;
  for(int i=0;i<m;i++){
    int x,y;
    cin>>x>>y;
    x--;y--;
    st.erase({min(x,y),max(x,y)});
    st2.insert({min(x,y),max(x,y)});
  }
  for(auto i:st){
    adj[i.F].pb(i.S);
    adj[i.S].pb(i.F);
  }
  if(bipartite()==false){
    cout<<-1;
    return;
  }
  ll ans=0;
  vis.resize(n);
  vector<pair<int,int>>zz;
  for(int i=0;i<n;i++){
    if(!vis[i]){
      lef.clear();
      rig.clear();
      dfs_2col(i);
      for(auto j:lef){
	for(auto k:rig){
	  if(st2.find({min(j,k),max(j,k)})!=st2.end()){
	    ans++;
	  }
	}
      }
      zz.pb({lef.size(),rig.size()});
    }
  }
  dp[0][0]=true;
  for(int i=0;i<zz.size();i++){
    for(int j=0;j<=n-zz[i].F;j++){
      dp[1][j+zz[i].F]|=dp[0][j];
    }
    for(int j=0;j<=n-zz[i].S;j++){
      dp[1][j+zz[i].S]|=dp[0][j];
    }
    for(int j=0;j<=n;j++){
      dp[0][j]=dp[1][j];
      dp[1][j]=false;
    }
  }
  ll optans=0;
  for(int i=0;i<=n;i++){
    if(dp[0][i]==false){
      continue;
    }
    ll lef=i*(n-i);
    for(int j=0;j<zz.size();j++){
      lef-=(zz[j].F)*(zz[j].S);
    }
    optans=max(optans,lef);
  }
  debug(optans,m,ans);
  cout<<m-ans-optans;
}
 
signed main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int tc=1;
  //cin>>tc;
  for(int _=0;_<tc;_++){
    // cout<<"Case #"<<_+1<<": ";
    solve();
    if(_!=tc-1){
      cout<<'\n';
    }
  }
}


Measured memory_bytes: 38016