#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <cassert>
using namespace std;

class Graph {
    int n, max_color;
    vector<int> color;
    bool is_bip = true;
    map<int, int> visited;
    vector<vector<int>> blacks, whites;
    
    void dfs(int v, int c) {
        if (color[v] != -1) {
            if (color[v] != c) is_bip = false;
            return;
        }
        color[v] = c;
        visited.erase(v);
        for (int i: adj[v]) {
            dfs(i, c + 1 - c % 2 * 2);
        }
    }
    
public:
    vector<vector<int>> adj;
    vector<vector<int>> adj_matrix;
    
    Graph(int n) {
        this->n = n;
        adj = vector<vector<int>>(n);
    }
    
    void use_adj_matrix() {
        adj_matrix = vector<vector<int>>(n, vector<int>(n));
    }
    
    void addEdge(int a, int b) {
        assert(0 <= a && a < n);
        assert(0 <= b && b < n);
        if (adj_matrix.size()) {
            adj_matrix[a][b] = 1;
            adj_matrix[b][a] = 1;
        }
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    
    bool is_bipartite() {
        for (int i = 0; i < n; i++) {
            visited[i] = 1;
        }
        color = vector<int>(n, -1);
        max_color = 0;
        while (visited.size()) {
            int v = (*visited.begin()).first;
            dfs(v, max_color);
            max_color += 2;
        }
        return is_bip;
    }
    
    bool is_connected() {
        color = vector<int>(n, -1);
        dfs(0, 0);
        for (int i = 0; i < n; i++) {
            if (color[i] == -1) {
                return false;
            }
        }
        return true;
    }
    
    vector<vector<int>> get_blacks() {
        blacks = vector<vector<int>>(max_color / 2);
        for (int i = 0; i < n; i++) {
            if (color[i] % 2 == 0) {
                blacks[color[i] / 2].push_back(i);
            }
        }
        return blacks;
    }
    
    vector<vector<int>> get_whites() {
        whites = vector<vector<int>>(max_color / 2);
        for (int i = 0; i < n; i++) {
            if (color[i] % 2 == 1) {
                whites[color[i] / 2].push_back(i);
            }
        }
        return whites;
    }
};

using VI = vector<int>;
map<int, int> sum;
int main() {
    int n, m;
    cin >> n >> m;
    vector<VI> adj(n, vector<int>(n));
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        adj[a][b] = 1;
        adj[b][a] = 1;
    }
    Graph g(n);
    g.use_adj_matrix();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (adj[i][j] == 0) {
                g.addEdge(i, j);
            }
        }
    }
    
    if (!g.is_bipartite()) {
        cout << -1 << endl;
        return 0;
    }
    
    vector<VI> blacks = g.get_blacks();
    vector<VI> whites = g.get_whites();

    VI diff;
    int bwsum = 0;
    int bsum = 0, wsum = 0;
    for (int i = 0; i < blacks.size(); i++) {
        bsum += blacks[i].size();
        wsum += whites[i].size();
        diff.push_back(int(blacks[i].size()) - int(whites[i].size()));
        bwsum += diff.back();
    }
    
    sum[0] = 1;
    VI add;
    for (int i = 0; i < blacks.size(); i++) {
        add.clear();
        for (auto& k: sum) {
            add.push_back(diff[i] + k.first);
        }
        for (int a: add) {
            sum[a] = 1;
        }
    }
    
    int u;
    int min = 1e9;
    for (auto& k: sum) {
        int a = bsum - k.first;
        int b = wsum + k.first;
        if (abs(b - a) < min) {
            min = abs(b - a);
            u = a;
        }
    }
    int v = n - u;
    cout << u * (u - 1) / 2 + v * (v - 1) / 2 << endl;
}


Measured memory_bytes: 7040