#include<bits/stdc++.h>
using namespace std;
const int N=1505;
int n,m,u,v,ans;
bool mp[N][N],dp[N][N];
int col[N],cnt[5];
void dfs(int x,int c){
    col[x]=c;
    cnt[c]++;
    for(int i=1;i<=n;++i){
        if(!mp[x][i]) continue;
        if(!col[i]) dfs(i,c^1);
        else if(col[i]==c){
            puts("-1");
            exit(0);
        }
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%d%d",&u,&v);
        mp[u][v]=mp[v][u]=1;
    }
    for (int i=1;i<=n;++i)
    	for (int j=1;j<=n;++j)
    		if (i!=j) mp[i][j]^=1;
    dp[0][0]=1;
    int tot1=0;
    for(int i=1;i<=n;++i){
        if(col[i]) continue;
        cnt[2]=cnt[3]=0;
        dfs(i,2);
        ++tot1;
        for(int j=0;j<=n;++j){
        	if (j>=cnt[2]) dp[tot1][j]|=dp[tot1-1][j-cnt[2]];
        	if (j>=cnt[3]) dp[tot1][j]|=dp[tot1-1][j-cnt[3]];
        }
    }
    ans=0x7fffffff;
    for(int i=0;i<=n;i++)
        if(dp[tot1][i])
            ans=min(ans,i*(i-1)/2+(n-i)*(n-i-1)/2);
    printf("%d\n",ans);
    return 0;
}