#include <iostream>
#include <fstream>
#include <iomanip>

#include <vector>
#include <set>
#include <bitset>
#include <map>
#include <deque>
#include <string>

#include <algorithm>
#include <numeric>
#include <random>

#include <cstdio>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>

using namespace std;

#define forn(i, n) for (ll i = 0; i < (ll) (n); ++i)
#define sz(a) static_cast<int>((a).size())
#define endl '\n'

using ll = long long;

const ll INF = static_cast<ll>(1e9) + 7;
const int MAXN = static_cast<int>(1e3) + 17;

int n, m;
int g[MAXN][MAXN], g1[MAXN][MAXN];
bool used[MAXN];
int color[MAXN];
int dp[MAXN][MAXN];

bool read() {
    if (!(cin >> n >> m))
        return false;

    forn (i, m) {
        int u, v;
        cin >> u >> v;
        g[u - 1][v - 1] = g[v - 1][u - 1] = 1;
    }

    return true;
}

bool bip = true;
int V = 0, E = 0;

void dfs1(int v) {
    used[v] = true;
    ++V;

    for (int i = 0; i < n; ++i)
        if (g[v][i]) {
            ++E;

            if (!used[i])
                dfs1(i);
        }
}

void dfs(int v, int col) {
    color[v] = col;
    used[v] = true;

    if (col == 0)
        ++V;
    else
        ++E;

    for (int i = 0; i < n; ++i)
        if (g1[v][i]) {
            if (!used[i]) {
                dfs(i, 1 - col);
            } else {
                if (color[i] == col)
                    bip = false;
            }
        }
}

void solve() {
    int cnt = 0;
    vector< pair<int, int> > vec;

    forn (i, n)
        if (!used[i]) {
            ++cnt;
            V = E = 0;
            dfs1(i);
            vec.push_back(make_pair(V, E / 2));
        }

    if (cnt > 2) {
        cout << -1 << endl;
        return ;
    }

    if (cnt == 2) {
        if (vec[0].first * (vec[0].first - 1) / 2 == vec[0].second
                && vec[1].first * (vec[1].first - 1) / 2 == vec[1].second) {
            cout << m << endl;
            return ;
        } else {
            cout << -1 << endl;
            return ;
        }
    }

    fill(used, used + n, false);

    forn (i, n)
        forn (j, n)
            if (i != j)
                g1[i][j] = 1 - g[i][j];

    vec.clear();

    forn (i, n)
        if (!used[i]) {
            V = E = 0;
            dfs(i, 0);
            vec.push_back(make_pair(V, E));
        }

    if (!bip) {
        cout << -1 << endl;
        return ;
    }

    dp[0][0] = true;

    for (int i = 0; i < sz(vec); ++i)
        for (int j = 0; j <= n; ++j)
            if (dp[i][j]) {
                if (j + vec[i].first <= n)
                    dp[i + 1][j + vec[i].first] = 1;

                if (j + vec[i].second <= n)
                    dp[i + 1][j + vec[i].second] = 1;
            }

    int ans = INF;

    for (int j = 0; j <= n; ++j)
        if (dp[sz(vec)][j])
            ans = min(ans, (j * (j - 1)) / 2 + (n - j) * (n - j - 1) / 2);

    cout << ans << endl;
}

int main() {
    cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::mt19937 rand('S' + 'E' + 'R' + 'E' + 'Z' + 'H' + 'K' + 'A');

#ifdef SEREZHKA
    freopen("file.in", "r", stdin);
#endif

    while (read())
        solve();

    return 0;
};



Measured memory_bytes: 11136