// Slower C++ solution:
#include <bits/stdc++.h>



#include <ext/pb_ds/assoc_container.hpp>

#include <ext/pb_ds/tree_policy.hpp>



#define sf scanf

#define pf printf

#define pb push_back

#define mp make_pair

#define PI ( acos(-1.0) )

#define mod 1000000007LL

#define IN freopen("C.in","r",stdin)

#define OUT freopen("output.txt","w",stdout)

#define FOR(i,a,b) for(i=a ; i<=b ; i++)

#define DBG pf("Hi\n")

#define MEM(ara,val) memset(ara,val,sizeof(ara))

#define INF 1000000000

#define i64 long long int

#define eps (1e-8)

#define xx first

#define yy second

#define ln 17

#define off 2



using namespace __gnu_pbds;

using namespace std ;



typedef tree< i64, null_type, less<i64>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

typedef pair<i64, i64> pii;



#define maxn 700



int g[maxn+5][maxn+5] ;



int col[maxn+5] , cnt[2] , n ;



bool dfs(int u ,int c)

{

//    printf("dfs %d %d\n",u,c) ;

    int ret = 1 ;

    cnt[c]++ ; col[u] = c ;

    for(int i=1 ; i<=n ; i++)

    {

        if(!g[u][i] || u==i) continue ;

        int v = i ;

        if( col[v]!=-1 && col[v]==c )

        {

  //          printf("false %d %d\n",u,v) ;

            ret = false ;

        }

        if( col[v]==-1 ) ret &= dfs(v,c^1) ;

    }

    return ret ;

}



int dp[705][705] ;



int main()

{

    MEM(col,-1) ;

    MEM(g,1) ;



    int i , j , k , m ;



    scanf("%d %d",&n,&m) ;



    for(i=1 ; i<=m ; i++)

    {

        int u , v ;

        scanf("%d %d",&u,&v) ;

        g[u][v] = 0 ;

        g[v][u] = 0 ;

    }

    int yes = 1 ;

    dp[0][0] = 1 ;

    for(i=1 ; i<=n ; i++)

    {

        if( col[i]==-1 )

        {

            cnt[0]= cnt[1] = 0 ;

            yes &= dfs(i,0) ;

            for(j=0 ; j+cnt[0]<=n ; j++) dp[i][j+cnt[0]] |= dp[i-1][j] ;

            for(j=0 ; j+cnt[1]<=n ; j++) dp[i][j+cnt[1]] |= dp[i-1][j] ;

        }

        else for(j=0 ; j<=n ; j++) dp[i][j] = dp[i-1][j] ;

    }

    int ans = (n*(n-1))/2 ;



    for(i=0 ; i<=n ; i++)

    {

        if( dp[n][i] ) ans = min( ans, (n*(n-1))/2 - (n-i)*i ) ;

    }



    if(!yes) printf("-1\n") ;

    else printf("%d\n",ans) ;



    return 0 ;

}


// Faster C++ solution for the same problem (measured speedup: 2.9995675527415955x):
#include <bits/stdc++.h>

using namespace std;

#define rep(i,a,n) for (int i = a; i<n; i++)

#define per(i,a,n) for (int i = n-1; i>=a; i--)

#define pb push_back

#define mp make_pair

#define all(now) (now).begin(),(now).end()

#define fi first

#define se second

#define SZ(now) ((int)(now).size())

typedef vector<int> VI;

typedef long long ll;

typedef pair<int,int> PII;

const ll mod = 1000000007;

inline int read(int &n){char c=getchar();int x=0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+(c-'0');c=getchar();}return n = x*f;}

ll powmod(ll a,ll b,ll mod) {ll res = 1; a%=mod; assert(b>=0); for(;b; b>>=1){if(b&1)res = res*a%mod; a = a*a%mod;}return res;}

ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

// head

const int N = 7e2+7;

int T,n,m;

bool f[N][N], g[N][N];

int col[N], ans = 0x7fffffff, now, num[3];

inline int Get(int x){ return x*(x-1)>>1;}

bool dfs(int x, int c)

{

    col[x] = c, num[c]++;

    rep(i,1,n+1) if(!g[x][i]) {

        if(!col[i] && !dfs(i,3-c))

            return 0;

        else if(col[i]==c)

            return 0;

    }

    return 1;

}

int main()

{

    //ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    cin >> n >> m;

    rep(i,1,m+1){

        int u, v;

        scanf("%d%d", &u, &v);

        g[u][v] = 1, g[v][u] = 1;

    }

    f[0][0] = 1;

    rep(i, 1, n + 1) g[i][i] = 1;

    rep(i,1,n+1) if(!col[i]) {

        num[1] = num[2] = 0;

        if(!dfs(i,1)){

            puts("-1");

            return 0;

        }



        now++;

        rep(j, 0, n + 1) if (f[now - 1][j]) 

            f[now][j + num[1]] = f[now][j + num[2]] = 1;

    }

    rep(i, 0, n + 1) if (f[now][i]) 

        // ans = min(ans, i * (i - 1) / 2 + (n - i) * (n - i - 1) / 2);

        ans=min(ans,Get(i)+Get(n-i));

    printf("%d\n", ans);

    return 0;

}