#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <numeric>
#include <functional>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <memory>
#include <thread>
#include <tuple>

using namespace std;

struct ParityPCSZ {
  // assumption: every root node points itself.
  struct node_t {
    int parent;
    int size;
    char edge_parity;
    node_t() : size(1), edge_parity(0) {}
  };
  vector<node_t> nodes;

  ParityPCSZ() { }
  ParityPCSZ(int size) : nodes(size) {
    for (int i = 0; i < size; i++) {
      nodes[i].parent = i;
    }
  }

  // add more nodes
  void expand(int count) {
    int oldsize = nodes.size();
    nodes.resize(oldsize + count);
    for (int i = oldsize; i < oldsize + count; i++) {
      nodes[i].parent = i;
    }
  }

  void clear() {
    nodes.clear();
  }

  // find root node
  int find(int index) {
    int root = index;
    char sum = 0;
    while (root != nodes[root].parent) {
      sum ^= nodes[root].edge_parity;
      root = nodes[root].parent;
    }
    char partial = 0;
    while (root != nodes[index].parent) {
      int next = nodes[index].parent;
      char edge = nodes[index].edge_parity;
      nodes[index].edge_parity = partial ^ sum;
      nodes[index].parent = root;
      partial ^= edge;
      index = next;
    }
    return root;
  }

  // true if merge was successful
  bool merge(int first, int second, bool parity) {
    int r1 = find(first);
    int r2 = find(second);
    if (r1 == r2) {
      return false;
    }
    if (nodes[r1].size < nodes[r2].size) {
      // careful, first and second not swapped
      swap(r1, r2);
    }
    nodes[r1].size += nodes[r2].size;
    nodes[r2].parent = r1;
    nodes[r2].edge_parity = nodes[first].edge_parity ^ nodes[second].edge_parity ^ (parity ? 1 : 0);
    return true;
  }

  // 0, 1 if related, -1 if not related
  int parity_distance(int first, int second) {
    int root_first = find(first);
    int root_second = find(second);
    if (root_first != root_second) {
      return -1;
    }
    // assumption: nodes[first].parent == nodes[second].parent because of PC(Path Compression)
    return nodes[first].edge_parity ^ nodes[second].edge_parity;
  }

  // parity distance to root
  bool parity(int index) {
    find(index);
    // assumption: nodes[first].parent == root
    return !!nodes[index].edge_parity;
  }

  int group_size(int index) {
    return nodes[find(index)].size;
  }
};


int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  vector<vector<char>> matrix(n, vector<char>(n, 0));
  for (int i = 0; i < m; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    a--, b--;
    matrix[a][b] = 1;
    matrix[b][a] = 1;
  }

  ParityPCSZ parity(n);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
      if (matrix[i][j] == 0) {
        bool merged = parity.merge(i, j, 1);
        if (!merged && parity.parity_distance(i, j) != 1) {
          printf("-1\n");
          return 0;
        }
      }
    }
  }
  vector<int> diffs(n);
  for (int i = 0; i < n; i++) {
    int root = parity.find(i);
    if (parity.parity_distance(root, i) == 0) {
      diffs[root]++;
    }
    else {
      diffs[root]--;
    }
  }

  vector<int> items;
  for (int i = 0; i < n; i++) {
    int root = parity.find(i);
    if (i == root) {
      items.push_back(abs(diffs[root]));
    }
  }
  vector<int> dp(2*n + 1);
  vector<int> ndp(2*n + 1);
  int start = n;
  dp[start] = 1;
  for (int i = 0; i < items.size(); i++) {
    fill(ndp.begin(), ndp.end(), 0);
    for (int j = 0; j <= 2 * n; j++) {
      if (dp[j] == 0) continue;
      ndp[j + items[i]] = 1;
      ndp[j - items[i]] = 1;
    }
    ndp.swap(dp);
  }
  for (int i = 0; i <= n; i++) {
    if (dp[start + i]) {
      long long a = (n + i) / 2;
      long long b = n - a;
      printf("%lld\n", a * (a - 1) / 2 + b*(b - 1) / 2);
      break;
    }
  }
  return 0;
}


Measured memory_bytes: 768