#include <bits/stdc++.h>
using namespace std;

using i64=int64_t;

#define rep(i,x,y) for(i64 i=i64(x),i##_max_for_repmacro=i64(y); i<i##_max_for_repmacro; ++i)
#define debug(x) #x << "=" << (x)
 
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif
 
const int inf=1.01e9;
const i64 inf64=4.01e18;
const double eps=1e-9;
 
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
        os << v << ",";
    }
    os << "]";
    return os;
}

class union_find{
	private:
	vector<int> parent,rank,gs;
    int size;
	public:
    int count_group;
    union_find()=default;
    union_find(int n){ init(n); }

    void init(int n){
		size=n;
		count_group=n;
		parent.resize(size);
		rank.assign(size,0);
        gs.assign(size,1);
		for(int i=0; i<size; ++i) parent[i]=i;
	}

	int find(int x){
		if(parent[x]==x) return x;
		else return parent[x]=find(parent[x]);
	}

	void unite(int x,int y){
		x=find(x);
		y=find(y);
		if(x==y) return;
		if(rank[x]<rank[y]){
			parent[x]=y;
            gs[y]+=gs[x];
		} else {
			parent[y]=x;
            gs[x]+=gs[y];
			if(rank[x]==rank[y]) ++rank[x];
		}
		--count_group;
	}

	bool is_same_group(int x,int y){
		return find(x)==find(y);
	}

    int group_size(int x){
        return gs[find(x)];
    };
};

void solve(){
    int N,M;
    cin >> N >> M;

    vector<int> A(M),B(M);
    vector<vector<bool>> e(N,vector<bool>(N));
    rep(i,0,M){
        cin >> A[i] >> B[i];
        --A[i];
        --B[i];
        e[A[i]][B[i]]=e[B[i]][A[i]]=true;
    }

    vector<vector<int>> comp(N);
    rep(i,0,N) rep(j,0,N){
        if(i==j or e[i][j]) continue;
        comp[i].push_back(j);
    }

    vector<int> col(N,2);
    function<bool(int,int)> dfs=[&](int u,int c){
        col[u]=c;
        for(int v:comp[u]){
            if(col[v]==2){
                if(!dfs(v,1-c)) return false;
            }else if(col[v]==col[u]) return false;
        }

        return true;
    };

    rep(i,0,N) if(col[i]==2 and !dfs(i,0)){
        cout << -1 << endl;
        return;
    }

    union_find uf(N);
    rep(i,0,N) rep(j,0,comp[i].size()) uf.unite(i,comp[i][j]);

    vector<int> all;
    rep(i,0,N) all.push_back(uf.find(i));

    sort(begin(all),end(all));
    all.erase(unique(begin(all),end(all)),end(all));

    unordered_map<int,int> mp;
    rep(i,0,all.size()) mp[all[i]]=i;

    const int count_group=all.size();
    vector<int> x(count_group),y(count_group);
    rep(i,0,N){
        int g=mp[uf.find(i)];
        if(col[i]==1) ++x[g];
        else ++y[g];
    }

    vector<vector<bool>> dp(count_group,vector<bool>(800));
    dp[0][x[0]]=dp[0][y[0]]=true;
    rep(i,0,count_group-1){
        rep(j,0,N+1){
            if(!dp[i][j]) continue;
            dp[i+1][j+x[i+1]]=dp[i+1][j+y[i+1]]=true;
        }
    }

    i64 ans=inf64;
    rep(i,0,N+1){
        if(!dp[count_group-1][i]) continue;
        ans=min(ans,i*(i-1)/2+(N-i)*(N-i-1)/2);
    }

    cout << ans << endl;
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    solve();
    return 0;
}


Measured memory_bytes: 3200