#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
//#include <tuple>
#include <iomanip>
#include <cstring>

using namespace std;

typedef long long ll;
//typedef pair<int,int> Pint;
//typedef pair<ll, ll> P;
typedef pair<ll, pair<ll, ll> > P;
//typedef tuple<int,int,int> T;
typedef vector<ll> vec;
typedef vector<vec> mat;
#define rep(i, n) for(ll i = 0; i < (n); i++)
#define revrep(i, n) for(ll i = (n-1); i >= 0; i--)
#define pb push_back
#define f first
#define s second
const ll INFL = 1LL << 60;//10^18 = 2^60
const int INF = 1 << 30;//10^9
const ll MOD = 1e9 + 7;
//const ll MOD  = 998244353;
//vector<ll> dy = {0, 0, 1, -1, 1, 1, -1, -1, 0};
//vector<ll> dx = {1, -1, 0, 0, 1, -1, 1, -1, 0};

ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll pow_long(ll x, ll k){
  ll res = 1;
  while(k > 0){
    if(k % 2) res *= x;
    x *= x;
    k /= 2;
  }
  return res;
}
ll pow_mod(ll x, ll k){
  x %= MOD; x += MOD; x %= MOD;
  ll res = 1;
  while(k > 0){
    if(k % 2){
      res *= x; res %= MOD;
    }
    x *= x; x %= MOD;
    k /= 2;
  }
  return res;
}
ll inverse(ll x){return pow_mod(x, MOD - 2);};

//最大公約数
ll gcd(ll a, ll b){
    if(b == 0) return a;
    return gcd(b, a % b);
}

//最小公倍数
ll lcm(ll x, ll y){return x / gcd(x, y) * y;};

//コンビネーション
const int MAXcomb = 200010;
ll fac[MAXcomb], finv[MAXcomb], inv[MAXcomb];
//facはn!,finvは1/n!
//invは逆元
void COMinit(){
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i = 2; i < MAXcomb; i++){
        fac[i] = fac[i-1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;
        finv[i] = finv[i-1] * inv[i] % MOD;
    }
}
ll comb(int n, int k){
    if(n < k) return 0;
    if(n < 0 || k < 0) return 0;
    return fac[n] * finv[k] % MOD * finv[n-k] % MOD;
}

int N, M;
bool E[710][710];
int visited[710];
bool l = 1;
ll cnt = 1;
bool canmake[710][710][710];

void dfs(int now){
  rep(to, N){
    if(E[now][to] == 0) continue;
    if(visited[to] == 0){
      visited[to] = -visited[now];
      dfs(to);
    }else{
      if(visited[now] != -visited[to]) l = 0;
    }
  }
}

bool Bip(){
  rep(i, N){
    if(visited[i] != 0) continue;
    visited[i] = cnt;
    dfs(i);
    cnt++;
  }
  return l;
}

void solve(){
  if(Bip() == 0){
    cout << -1 << endl;
    return;
  }
  //二部グラフである

  ll V = 0;
  rep(i, N)rep(j, N)if(E[i][j]) V++;
  V /= 2;
  vector<pair<int, int>> Cnt(cnt, {0, 0});
  rep(i, N){
    if(visited[i] > 0) Cnt[abs(visited[i])-1].first++;
    else Cnt[abs(visited[i])-1].second++;
  }
  canmake[0][0][0] = 1;
  rep(c, cnt){
    rep(i, N+1)rep(j, N+1){
      if(canmake[c][i][j] == 0) continue;
      canmake[c+1][i+Cnt[c].first][j+Cnt[c].second] = 1;
      canmake[c+1][i+Cnt[c].second][j+Cnt[c].first] = 1;
    }
  }
  ll ans = INF;
  rep(i, N)rep(j, N){
    if(canmake[cnt][i][j] == 0) continue;
    ans = min(ans, M - (i * j - V));
  }
  cout << ans << endl;
}

int main(void){
  cin >> N >> M;
  rep(i, N)rep(j, N) E[i][j] = 1;
  rep(i, N) E[i][i] = 0;
  rep(i, M){
    ll A, B; cin >> A >> B; A--, B--;
    E[A][B] = 0;
    E[B][A] = 0;
  }
  solve();
}


Measured memory_bytes: 346368