#include <bits/stdc++.h>
#include <stdlib.h>
#include <time.h> 
 
using namespace std;
long long mod=1e9+7;
long long INF=1e7;
double EPS = 1e-12;
typedef long long int lld;
double tick(){static clock_t oldt;clock_t newt=clock();double diff=1.0*(newt-oldt)/CLOCKS_PER_SEC;oldt = newt;return diff;}
#define rep(i,a,n) for(long long int i = (a); i <= (n); ++i)
#define repI(i,a,n) for(int i = (a); i <= (n); ++i)
#define repD(i,a,n) for(long long int i = (a); i >= (n); --i)
#define repDI(i,a,n) for(int i = (a); i >= (n); --i)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define sc(a) scanf("%lld",&a)
#define sc2(a,b) scanf("%lld%lld",&a,&b)
#define sc3(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)
#define scd(a) scanf("%d",&a)
#define scd2(a,b) scanf("%d%d",&a,&b)
#define scd3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define scf(a) scanf("%lf",&a)
#define scf2(a,b) scanf("%lf%lf",&a,&b)
#define scf3(a,b,c) scanf("%lf%lf%lf",&a,&b,&c)
#define prL(a) printf("%lld\n",a)
#define prS(a) printf("%lld ",a)
#define prdL(a) printf("%d\n",a)
#define prdS(a) printf("%d ",a)
#define all(c) c.begin(), c.end()
#define sz(a) ((int)a.size())
#define Error(x) cout<< #x << " = " << (x) <<endl;
#define Error2(a,b) cout<<"( "<<#a<<" , "<<#b<<" ) = ( "<<(a)<<" , "<<(b)<<" )\n";
#define Error3(a,b,c) cout<<"("<<#a<<" , "<<#b<<" , "<<#c<<" ) = ( "<<(a)<<" , "<<(b)<<" , "<<(c)<<")\n";
#define Error4(a,b,c,d) cout<<"("<<#a<<" , "<<#b<<" , "<<#c<<" , "<<#d<<" ) = ( "<<(a)<<" , "<<(b)<<" , "<<(c)<<" , "<<(d)<<")\n";
#define errop(a) cout<<#a<<" = ( "<<((a).x)<<" , "<<((a).y)<<" )\n";
#define mset(a, v) memset(a, v, sizeof(a))
#define popcount __builtin_popcountll
 
typedef pair<lld,lld> PA;
 
lld powP(lld a,lld b){
    if(b==0) return 1%mod;
    lld k;
    k=powP(a,b/2);
    k=k*k%mod;
    if(b%2==0) return k;
    else return a*k%mod;
}
 
bool bitSet(lld n,lld i){
    if((n&(1LL<<i))!=0) return true;
    else return false;
}
 
lld findGcd(lld a,lld b){
    if(a==0) return b;
    else return findGcd(b%a,a);
}
 
#define lim 300010
#define lim2 200010
#define qqqqqq 210
// Ab :)
// inline lld sqr(lld x) { return x * x; }
// unordered_map<lld,lld>::iterator it;
// std::ios::sync_with_stdio(false);
// priority_queue<PA> Q;
// lld dp[1<<18];

vector<lld> V[lim];
// string S[lim];
lld A[lim],B[lim],C[lim];
map<lld,map<lld,lld> > M;
// map<lld,lld> M;
lld alpha, beta;
lld n;
void dfs(lld x, lld val) {
    if(A[x] == 0) {
        A[x] = val;
        alpha += (val == 1);
        beta += (val == 2);
    }
    else {
        if(A[x] != val) A[x] = -1;
        return ;
    }
    vector<lld> C(n+1,0);
    C[x] = 1;
    for(const auto &t : V[x]) {
        C[t] = 1;
    }
    rep(i,1,n) if(C[i] == 0) dfs(i, 3 - val);
}
bool dp[1003][1003];
inline lld diff(lld x, lld sum) {
    return abs(x - (sum - x));
}
int main(){
    lld T,i,p,j,l,e,r,b,c,k,m,q,a,d,w,x,y,u,v,z,t,curr,prev,sum,ans,pos,val,countA,indicator;
    sc2(n,m);
    // if(n == 2 and m == 0) {
    //     printf("0\n");
    //     return 0;
    // }
    rep(i,1,m) {
        sc2(a,b);
        V[a].pb(b);
        V[b].pb(a);
        M[a][b] = 1;
        M[b][a] = 1;
    }
    sum = 0;
    b = 0;
    rep(i,1,n) {
        if(A[i] == 0) {
            alpha = beta = 0;
            dfs(i,1);
            // Error2(alpha, beta);
            b++;
            B[b] = abs(alpha - beta);
            sum += B[b];
        }
    }
    rep(i,1,n) {
        if(A[i] == -1) {
            printf("-1\n");
            return 0;
        }
    }
    dp[0][0] = true;
    rep(i,1,b) rep(j,0,n) {
        dp[i][j] = dp[i-1][j];
        if(j - B[i] >= 0) dp[i][j] |= dp[i-1][j-B[i]];
    }
    x = n;
    rep(i,0,n) {
        if(dp[b][i]) {
            x = min(x, diff(i, sum));
        }
    }
    a = (n + x) / 2;
    b = a - x;
    prL(a*(a-1)/2 + b*(b-1)/2);
    return 0;
}

Measured memory_bytes: 50176