import std.algorithm;
import std.array;
import std.ascii;
import std.bigint;
import std.complex;
import std.container;
import std.conv;
import std.functional;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

auto readInts() {
  return array(map!(to!int)(readln().strip().split()));
}

auto readInt() {
  return readInts()[0];
}

auto readLongs() {
  return array(map!(to!long)(readln().strip().split()));
}

auto readLong() {
  return readLongs()[0];
}

void readlnTo(T...)(ref T t) {
  auto s = readln().split();
  assert(s.length == t.length);
  foreach (ref ti; t) {
    ti = s[0].to!(typeof(ti));
    s = s[1 .. $];
  }
}

class UnionFindTree {
public:
  this(size_t n) {
    parent = iota(n).array();
    rank = new size_t[](n);
  }

  size_t find(size_t n) {
    if (n == parent[n]) {
      return n;
    } else {
      parent[n] = find(parent[n]);
      return parent[n];
    }
  }

  void unite(size_t n, size_t m) {
    auto p1 = find(n);
    auto p2 = find(m);
    if (n == m) {
      return;
    }
    if (rank[p1] < rank[p2]) {
      swap(p1, p2);
    }
    if (rank[p1] == rank[p2]) {
      ++rank[p1];
    }
    parent[p2] = p1;
  }

private:
  size_t[] parent;
  size_t[] rank;
}

unittest {
  auto uft = new UnionFindTree(10);
  foreach (i; iota(10)) {
    assert(uft.find(i) == i);
  }
  foreach (i; iota(10).filter!(a => a % 3 == 0).drop(1)) {
    uft.unite(i, i - 3);
  }
  foreach (i; iota(10).filter!(a => a % 3 == 0)) {
    assert(uft.find(0) == uft.find(i));
  }
  foreach (i; iota(10).filter!(a => a % 3 != 0)) {
    assert(uft.find(0) != uft.find(i));
  }
}

//内部では1-based, 使うときは0-based
class BinaryIndexedTree(T, alias F = "a + b") if (is(typeof(binaryFun!F))) {
  alias f = binaryFun!F;
public:
  this(in size_t n, in T T0 = T.init) {
    t.length = n + 1;
    t[] = T0;
  }

  void add(in size_t idx, in T v)
  in {
    assert(idx < t.length - 1);
  }
  body {
    one_based_add(idx + 1, v);
  }

  T accumulate(size_t idx) {
    return one_based_accumulate(idx + 1);
  }

private:
  T[] t;

  //1-based
  void one_based_add(size_t idx, in ref T v) {
    if (idx >= t.length) {
      return;
    }
    t[idx] = f(t[idx], v);
    one_based_add(idx + (idx & (-idx)), v);
  }

  T one_based_accumulate(size_t idx) {
    if (idx == 0) {
      return t[0];
    } else {
      return f(one_based_accumulate(idx - (idx & (-idx))), t[idx]);
    }
  }
}

unittest {
  auto bit = new BinaryIndexedTree!(long)(10);
  foreach (i; iota(10)) {
    assert(bit.accumulate(i) == 0);
  }
  bit.add(5, 3);
  foreach (i; iota(5)) {
    assert(bit.accumulate(i) == 0);
  }
  foreach (i; iota(5, 10)) {
    assert(bit.accumulate(i) == 3);
  }

  bit.add(7, 2);

  foreach (i; iota(5)) {
    assert(bit.accumulate(i) == 0);
  }
  foreach (i; iota(5, 7)) {
    assert(bit.accumulate(i) == 3);
  }
  foreach (i; iota(7, 10)) {
    assert(bit.accumulate(i) == 5);
  }
}

unittest {
  auto bit = new BinaryIndexedTree!(long, "a*b")(10, 1);
  foreach (i; iota(10)) {
    assert(bit.accumulate(i) == 1);
  }
  bit.add(5, 3);
  foreach (i; iota(5)) {
    assert(bit.accumulate(i) == 1);
  }
  foreach (i; iota(5, 10)) {
    assert(bit.accumulate(i) == 3);
  }

  bit.add(7, 2);

  foreach (i; iota(5)) {
    assert(bit.accumulate(i) == 1);
  }
  foreach (i; iota(5, 7)) {
    assert(bit.accumulate(i) == 3);
  }
  foreach (i; iota(7, 10)) {
    assert(bit.accumulate(i) == 6);
  }
}

//最大流、O(|V||E|^2)
template Flow_Dinic() {
  class Edge {
  public:
    this(long to, long capacity) {
      this.to = to;
      this.capacity = capacity;
    }

    long to;
    long capacity;
    Edge reverse;
  }

  //gを残余グラフにする
  void residualise(ref Edge[][] g) {
    foreach (u; iota(g.length)) {
      foreach (e; g[u]) {
        if (e.capacity != 0) {
          e.reverse = new Edge(u, 0);
          e.reverse.reverse = e;
          g[e.to] ~= e.reverse;
        }
      }
    }
  }

  const long INF = long.max / 2;

  //gは残余グラフ
  //gは計算の結果書き換わる
  long solve(Edge[][] g, long s, long t) {
    long ret;
    while (true) {
      auto level = new long[](g.length);
      level[] = INF;
      auto q = DList!long(s);
      level[s] = 0;
      //level graph
      auto lg = new Edge[][](g.length, 0);
      while (!q.empty()) {
        auto u = q.front();
        q.removeFront();
        if (u == t) {
          break;
        }
        foreach (e; g[u]) {
          if (e.capacity > 0 && level[e.to] >= level[u] + 1) {
            level[e.to] = level[u] + 1;
            q.insertBack(e.to);
            lg[u] ~= e;
          }
        }
      }
      if (level[t] == INF) {
        break;
      }
      auto iter = new long[](g.length);
      long dfs(long u, long c_min) {
        if (u == t) {
          return c_min;
        }
        foreach (i; iota(iter[u], lg[u].length)) {
          iter[u] = i;
          long f = dfs(lg[u][i].to, min(c_min, lg[u][i].capacity));
          if (f > 0) {
            lg[u][i].capacity -= f;
            lg[u][i].reverse.capacity += f;
            return f;
          }
        }
        return 0;
      }

      while (true) {
        long f = dfs(s, INF);
        if (f == 0) {
          break;
        }
        ret += f;
      }
    }
    return ret;
  }
}

enum real eps = 1e-10;

enum long mod = 1_000_000_000 + 7;

void main() {
  long n, m;
  readlnTo(n, m);
  auto g_ = new bool[][](n, n);
  foreach (i; iota(m)) {
    long a, b;
    readlnTo(a, b);
    --a;
    --b;
    g_[a][b] = true;
    g_[b][a] = true;
  }
  auto g = new bool[][](n, n);
  foreach (i; iota(n)) {
    foreach (j; iota(n)) {
      g[i][j] = !g_[i][j];
    }
  }
  foreach (i; iota(n)) {
    g[i][i] = false;
  }
  long[][] c;
  auto memo = new long[](n);
  memo[] = -1;
  Tuple!(long[], bool) dfs(long i, long d, long prev) {
    if (memo[i] != -1) {
      if (abs(memo[i] - d) % 2 == 1) {
        return tuple([0L, 0L], false);
      } else {
        return tuple([0L, 0L], true);
      }
    } else {
      auto ret = [1L, 0L];
      memo[i] = d;
      foreach (j; iota(n)) {
        if (j == i || j == prev) {
          continue;
        }
        if (!g[i][j]) {
          continue;
        }
        auto tmp = dfs(j, d + 1, i);
        if (!tmp[1]) {
          return tmp;
        }
        ret[0] += tmp[0][1];
        ret[1] += tmp[0][0];
      }
      return tuple(ret, true);
    }
  }

  foreach (i; iota(n)) {
    if (memo[i] != -1) {
      continue;
    }
    auto tmp = dfs(i, 0, -1);
    if (!tmp[1]) {
      writeln(-1);
      return;
    }
    c ~= tmp[0];
  }
  auto dp = new bool[][](c.length + 1, n + 1);
  dp[0][0] = true;
  foreach (i; iota(c.length)) {
    foreach (j; iota(n)) {
      if (dp[i][j]) {
        foreach (ci; c[i]) {
          if (j + ci <= n) {
            dp[i + 1][j + ci] = true;
          }
        }
      }
    }
  }
  long ans = long.max;

  foreach (i; iota(n + 1)) {
    if (dp[$ - 1][i]) {
      ans = min(ans, i * (i - 1) / 2 + (n - i) * (n - i - 1) / 2);
    }
  }
  writeln(ans);
}


Measured memory_bytes: 8828