#include <stdio.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    vector<vector<int>> vviRoad(n+1, vector<int>(n+1,0));
    for(int i = 0; i < m; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        vviRoad[a][b] = 1;
        vviRoad[b][a] = 1;
    }
    
    vector<int> viDiffer;    //分離すべき2グループの元の個数の差
    vector<int> viSearch(n+1,0);    //探索状態
    for(int i = 1; i <= n; i++){
        if(viSearch[i] == 1){
            continue;
        }
        vector<int> aviGroup[2];
        queue<int> aqiGroupTmp[2];
        char iCheck = 0;
        aqiGroupTmp[0].push(i);
        viSearch[i] = 1;
        while(!aqiGroupTmp[0].empty() || !aqiGroupTmp[1].empty()){
            if(iCheck == 0){
                int iSeed = aqiGroupTmp[0].front();
                aqiGroupTmp[0].pop();
                for(int j = 1; j <= n; j++){
                    if(viSearch[j] == 1){
                        continue;
                    }
                    if(vviRoad[iSeed][j] == 0){//iSeedとjが道でつながってなければ分離
                        aqiGroupTmp[1].push(j);
                        viSearch[j] = 1;
                    }
                }
                aviGroup[0].push_back(iSeed);
                if(aqiGroupTmp[0].empty()){
                    iCheck = 1;
                }
            }
            else if(iCheck == 1){
                int iSeed = aqiGroupTmp[1].front();
                aqiGroupTmp[1].pop();
                for(int j = 1; j <= n; j++){
                    if(viSearch[j] == 1){
                        continue;
                    }
                    if(vviRoad[iSeed][j] == 0){//iSeedとjが道でつながってなければ分離
                        aqiGroupTmp[0].push(j);
                        viSearch[j] = 1;
                    }
                }
                aviGroup[1].push_back(iSeed);
                if(aqiGroupTmp[1].empty()){
                    iCheck = 0;
                }
            }
        }
        if(!aviGroup[0].empty()){
            for(int j = 0; j < aviGroup[0].size() - 1; j++){
                for(int k = j + 1; k < aviGroup[0].size(); k++){
                    int a = aviGroup[0][j];
                    int b = aviGroup[0][k];
                    if(vviRoad[a][b] == 0){
                        printf("-1");
                        return 0;
                    }
                }
            }
        }
        if(!aviGroup[1].empty()){
            for(int j = 0; j < aviGroup[1].size() - 1; j++){
                for(int k = j + 1; k < aviGroup[1].size(); k++){
                    int a = aviGroup[1][j];
                    int b = aviGroup[1][k];
                    if(vviRoad[a][b] == 0){
                        printf("-1");
                        return 0;
                    }
                }
            }
        }
        int i0 = aviGroup[0].size();
        int i1 = aviGroup[1].size();
        viDiffer.push_back(abs(i1 - i0));
        //分離したグループの元の個数の差を記録
    }
    
//    DP  viDefferの元の和と差でなるべく0に近づける
    int iNum = viDiffer.size();
    vector<vector<int>> vviDP(iNum, vector<int>(n+1, 0)); //可能な値は高々n
    vviDP[0][viDiffer[0]] = 1;
    for(int i = 1; i < iNum; i++){
        for(int j = 0; j < n+1; j++){
            if(vviDP[i - 1][j] == 1){
                vviDP[i][j + viDiffer[i]] = 1;
                vviDP[i][abs(j - viDiffer[i])] = 1;
            }
        }
    }
    int iDiffer = 0;
    for(; iDiffer < n+1; iDiffer++){
        if(vviDP[iNum-1][iDiffer] == 1){//viDifferの元の和と差で表せる最小値をとる
            break;
        }
    }
    int i = (n + iDiffer) / 2;
    int j = (n - iDiffer) / 2;    //可能な最良の分け方
    printf("%d", (i * (i-1) + j * (j-1)) / 2);

    return 0;
}


Measured memory_bytes: 6800