#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define fi first
#define se second
#define mp make_pair
#define itrfor(itr,A) for(auto itr = A.begin(); itr !=A.end();itr++)
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;
typedef long long llong;
char moji[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
char moji2[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
char moji3[10]={'0','1','2','3','4','5','6','7','8','9'};
#define Sort(a) sort(a.begin(),a.end());
#define Reverse(a) reverse(a.begin(),a.end());
#define print(a) cout << a << endl;
#define MOD llong(1e9+7)
#define MAX int(2 * 1e5 +5)
#define debug(x)  cout << #x << " = " << (x) << endl;
#define pi acos(-1.0)
#define int llong
#define INF llong(1e18 + 3)
template<class T> bool chmax(T &a,  T b) {if(a<b){a=b; return 1;} return 0;}
template<class T> bool chmin(T &a,  T b) {if(a>b){a=b; return 1;} return 0;}
bool Add(int &a,int b){a = (a + b) % MOD;}
void myprint(int* A,int A_num){
   REP(i,A_num) cout << A[i] << " ";
   cout << endl;
}


const int n_max = 705;
int n,m;
bool G[n_max][n_max];
int color[n_max];
int kazu[n_max][2];
bool renketu[n_max];

bool dfs(int v, int c,int id){
    color[v] = c;
    kazu[id][c] ++;
    REP(i,n){
        if(i == v) continue;
        if(G[v][i] == false and color[i] == -1){
            if(dfs(i, 1 - c,id) == false) return false;
        }
        else if(G[v][i] == false and color[i] != -1){
            if(color[i] != 1 - c) return false;
        }
    }
    return true;
}

bool dfs2(int v){
    renketu[v] = true;
    REP(i,n) if(G[v][i] and renketu[i] == false) dfs2(i);
}


signed main(){
    cin >> n >> m;
    REP(i,n) REP(j,n) G[i][j] = false;
    REP(i,m){
        int a,b;
        cin >> a >> b;
        a --;
        b --;
        G[a][b] = true;
        G[b][a] = true;
    }

    REP(i,n) renketu[i] = false;
    dfs2(0);
    REP(i,n){
        if(renketu[i] == false){
            int cnt = 0;
            REP(k,n){
                if( renketu[k] == false){
                    cnt ++;
                    FOR(j,k+1,n){
                        if(renketu[j]== false and G[k][j] == false){
                            cout << -1 << endl;
                            return 0;
                        }
                    }
                }

            }
            cout << cnt * (cnt - 1) / 2 + (n - cnt) * (n - cnt - 1) / 2 << endl;
            return 0;
        }
    }

    REP(i,n) color[i] = - 1;
    int id = 0;
    REP(i,n){
        if(color[i] == -1){
            kazu[id][0] = 0;
            kazu[id][1] = 0;
            if(dfs(i,0,id) == false){
                cout << - 1 << endl;
                return 0;
            }
            id ++;
        }
    }


    bool dp[n_max][n_max];
    REP(i,n) REP(j,n) dp[i][j] = false;
    dp[0][0] = true;

    REP(i,id){
        REP(j,n){
            REP(k,2){
                if(dp[i][j] == false or j + kazu[i][k] >= n) continue;
                dp[i+1][j + kazu[i][k]] = true;
            }
        }
    }
    int ans = INF;
    REP(i,n){
        if(dp[id][i]) chmin(ans, i * (i - 1) / 2 + (n - i) * (n - i - 1) / 2);
    }
    cout << ans << endl;

}

Measured memory_bytes: 1280