#include "bits/stdc++.h"
using namespace std;
using ll     = long long;
using pii    = pair<int, int>;
using pll    = pair<ll, ll>;
using vi     = vector<int>;
using vl     = vector<ll>;
using vvi    = vector<vi>;
using vvl    = vector<vl>;
const ll INF = 1LL << 60;
const ll MOD = 1000000007;
template <class T>
bool chmax(T &a, const T &b) {
    return (a < b) ? (a = b, 1) : 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    return (b < a) ? (a = b, 1) : 0;
}
template <class C>
void print(const C &c, std::ostream &os = std::cout) {
    std::copy(std::begin(c), std::end(c), std::ostream_iterator<typename C::value_type>(os, " "));
    os << std::endl;
}

struct UnionFind {
    vector<int> rank, parent, size;

    // +1 for 1-indexed nodes
    UnionFind(int n) : rank(n + 1, 0), parent(n + 1), size(n + 1, 1) {
        iota(parent.begin(), parent.end(), 0); // parent is itself
    }
    int root(int x) {
        if (x != parent[x]) {
            parent[x] = root(parent[x]);
        }
        return parent[x];
    }
    bool isSame(int x, int y) { return root(x) == root(y); }
    bool unite(int x, int y) { return link(root(x), root(y)); }
    bool link(int x, int y) {
        if (x == y)
            return false;
        if (rank[x] > rank[y]) {
            parent[y] = x;
            size[x] += size[y];
        } else {
            parent[x] = y;
            size[y] += size[x];
            if (rank[x] == rank[y]) {
                rank[y]++;
            }
        }
        return true;
    }
    int getSize(int x) { return size[root(x)]; }
};

int main() {
    int n, m;
    cin >> n >> m;
    vector<set<int>> aux(n);
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        aux[a].insert(b);
        aux[b].insert(a);
    }
    vvi edges(n);
    UnionFind uf(n);
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (aux[i].count(j) == 0) {
                edges[i].push_back(j);
                edges[j].push_back(i);
                uf.unite(i, j);
            }
        }
    }
    vi col(n, 0);
    bool nibu                    = true;
    function<void(int, int)> dfs = [&](int c, int p) {
        for (auto &v : edges[c]) {
            if (v == p)
                continue;
            if (col[v] != 0) {
                if (col[v] == col[c]) {
                    nibu = false;
                    return;
                }
            } else {
                col[v] = -col[c];
                dfs(v, c);
            }
        }
    };
    for (int i = 0; i < n; ++i) {
        if (col[i] != 0)
            continue;
        col[i] = 1;
        dfs(i, -1);
    }
    if (!nibu) {
        cout << -1 << "\n";
        return 0;
    } else {
        set<int> roots;
        map<int, int> one, two;
        for (int i = 0; i < n; ++i) {
            int root = uf.root(i);
            roots.insert(root);
            if (col[i] == 1)
                one[root]++;
            else
                two[root]++;
        }
        bitset<700> dp = 0;
        dp[0]          = 1;
        for (auto &r : roots) {
            bitset<700> temp1, temp2;
            temp1 = dp << one[r];
            temp2 = dp << two[r];
            dp    = temp1 | temp2;
        }
        int maxi = 0;
        for (int i = 0; i < 700; ++i) {
            if (dp[i] == 1)
                chmax(maxi, i * (n - i));
        }
        cout << n * (n - 1) / 2 - maxi << "\n";
    }
    return 0;
}

Measured memory_bytes: 23296