#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// #include <ext/pb_ds/detail/standard_policies.hpp>
// using namespace __gnu_pbds;
using namespace std;
// template <typename T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,
//     tree_order_statistics_node_update>;
 
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimization ("unroll-loops")
typedef long long int ll;
typedef long double ld;
const ll N = 2e5+9;
// const ll m = 1e9 + 7;
const ll inf= 1e14;
const ll mod =998244353;
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define pii pair<ll,ll>
#define pld pair<ld,ld>
ll powm(ll a, ll b) { a = a%mod;ll res = 1; while (b) { if (b & 1) res = (res * a) % mod; a = (a * a) % mod; b >>= 1; } return res; }
bool adj[709][709];
ll st[709];
ll n;
void bfs(ll v,ll c){
    st[v] = c;
    queue<ll> q;
    q.push(v);
    while(!q.empty()){
        int u = q.front();q.pop();
        // cout<<u<<": ";
        ll ts = st[u];
        ll ns;
        if(ts%2){
            ns = ts+1;
        }
        else{
            ns = ts-1;
        }
        for(int s = 0;s<n;s++){
            if(s==u || !adj[u][s])continue;
            if(st[s] == 0){
                st[s] = ns;
                // cout<<s<<" ";
                q.push(s);
            }
            else if(st[s] == ts){
                // cout<<u<<"H"<<s<<" ";
                st[s] = inf;
            }
        }

        // cout<<'\n';
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout); 
    #endif  
    ll q = 1;
    // cin>>t;
    memset(adj,0,sizeof(adj));
    memset(st,0,sizeof(st));
    while(q--){
        
        ll m;cin>>n>>m;
        for(int i = 0;i<n;i++){
            for(int j = 0;j<n;j++){
                if(i==j)continue;
                adj[i][j] = 1;
            }
        }
        std::vector<pii> ed;
        for(int i = 0;i<m;i++){
            pii b;cin>>b.x>>b.y;b.x--;b.y--;
            adj[b.x][b.y] = 0;
            adj[b.y][b.x] = 0;
            ed.pb(b);
        }
        // for(int i = 0;i<n;i++){
        //     for(int j = 0;j<n;j++){
        //         cout<<adj[i][j];
        //     }
        //     cout<<'\n';
        // }
        ll c = 1;
        for(int i = 0;i<n;i++){
            if(st[i]==0){
                bfs(i,c);c+=2;

            }
        }

        bool po = 1;
        for(int i = 0;i<n;i++){
            if(st[i]==inf){
                po = 0;
            }
            // cout<<st[i]<<" ";
        }
        // cout<<'\n';
        if(po){
            ll ct[c][2];
            memset(ct,0,sizeof(ct));
            for(int i = 0;i<n;i++){
                ct[(st[i]+1)/2][st[i]%2]++;
            }
            // for(int i =0;i<c;i++){
            //     cout<<ct[i][0]<<" "<<ct[i][1]<<'\n';
            // }
            std::vector<ll> v;
            for(int i = 1;i<c;i++){
                if(abs(ct[i][0]-ct[i][1]))
                v.pb(abs(ct[i][0]-ct[i][1]));
            }
            ll su = 0;
            for(int i = 0;i<v.size();i++){
                // cout<<v[i]<<" ";
                su+=v[i];
            }
            // cout<<'\n';
            ll dp[v.size()][su+1];
            memset(dp,0,sizeof(dp));
            for(int i = 0;i<v.size();i++){
                if(i==0){
                    dp[i][v[i]] = 1;
                }
                else{
                    for(int j = 0;j<=su;j++){
                        if(dp[i-1][j]){
                            dp[i][j+v[i]] = 1;
                            dp[i][abs(j-v[i])] = 1;
                        }

                    }
                }
            }
            ll dif;
            for(int i = 0;i<=su;i++){
                if(dp[v.size()-1][i]){
                    dif= i;
                    break;
                }
            }
            ll a = (n+dif)/2;
            ll b = n-a;
            ll ans = (a*(a-1))/2;
            ans+=(b*(b-1))/2;
            cout<<ans<<'\n';
        }
        else{
            cout<<-1<<'\n';
        }

    }
}

Measured memory_bytes: 11552