# Original solution
from collections import deque


n, m = list(map(int, input().split()))
info = [list(map(int, input().split())) for i in range(m)]

matrix = [[0]*n for i in range(n)]
for i in range(m):
    a, b = info[i]
    a -= 1
    b -= 1
    matrix[a][b] = 1
    matrix[b][a] = 1

graph = [[] for i in range(n)]
for i in range(n):
    for j in range(i+1, n):
        if matrix[i][j] == 0:
            graph[i].append(j)
            graph[j].append(i)


def coloring(graph):
    n = len(graph)
    visited = [-1] * n
    ans = []
    for i in range(n):
        if visited[i] >= 0:
            continue
        visited[i] = 0
        q = deque([i]) 
        num = [1, 0]
        while q:
            _from = q.pop()
            for to in graph[_from]:
                if visited[to] == visited[_from]:
                    return [[-1, -1]]
                if visited[to] >= 0:
                    continue
                visited[to] = visited[_from] ^ 1
                num[visited[to]] += 1
                q.append(to)
        ans.append(num)
    return ans

num = coloring(graph)
if num[0][0] == -1:
    print((-1))
    exit()

dp = [[False]*(n+1) for _ in range(len(num) + 1)]
dp[0][0] = True

for i in range(len(num)):
    a, b = num[i]
    for j in range(n+1):
        if j-a >= 0:
            dp[i+1][j] = dp[i][j-a] or dp[i+1][j]
        if j-b >= 0:
            dp[i+1][j] = dp[i][j-b] or dp[i+1][j]

ans = 10**20
for i, boolian in enumerate(dp[len(num)]):
    if boolian:
        tmp_ans = i * (i-1) // 2 + (n-i) * (n-i-1) // 2 
        ans = min(tmp_ans, ans)
print(ans)

# Optimized solution
import sys
input = sys.stdin.readline


def is_bipartite(graph, s):
    """二部グラフ判定する"""
    n = len(graph)
    col = [-1] * n
    col[s] = 0
    stack = [s]
    used[s] = True
    while stack:
        v = stack.pop()
        for nxt_v in graph[v]:
            used[nxt_v] = True
            if col[nxt_v] == -1:
                col[nxt_v] = col[v] ^ 1
                stack.append(nxt_v)
            elif col[nxt_v] ^ col[v] == 0:
                return False
    return True

def color_bipartite(graph, s):
    """二部グラフを彩色する"""
    n = len(graph)
    col = [-1] * n
    col[s] = 0
    stack = [s]
    while stack:
        v = stack.pop()
        for nxt_v in graph[v]:
            if col[nxt_v] == -1:
                col[nxt_v] = col[v] ^ 1
                stack.append(nxt_v)
    return col


n, m = list(map(int, input().split()))
info = [list(map(int, input().split())) for i in range(m)]

graph = [set() for i in range(n)]
for a, b in info:
    a -= 1
    b -= 1
    graph[a].add(b)
    graph[b].add(a)

comp_graph = [[] for i in range(n)]
for a in range(n):
    for b in range(n):
        if b in graph[a] or a == b:
            continue
        comp_graph[a].append(b)
        

cnt0 = []
cnt1 = []
used = [False] * n
for i in range(n):
    if used[i]:
        continue
    used[i] = True
    if not is_bipartite(comp_graph, i):
        print((-1))
        exit()
    col = color_bipartite(comp_graph, i)
    cnt0.append(col.count(0))
    cnt1.append(col.count(1))

dp = [[False] * (n + 1) for i in range(len(cnt0) + 1)]
dp[0][0] = True
for i in range(len(cnt0)):
    wei0 = cnt0[i]
    wei1 = cnt1[i]
    for w in range(n + 1):
        if w + wei0 < n + 1:
            dp[i + 1][w + wei0] = (dp[i][w] or dp[i + 1][w + wei0])
        if w + wei1 < n + 1:
            dp[i + 1][w + wei1] = (dp[i][w] or dp[i + 1][w + wei1])

ans = 10 ** 18
for num in range(n + 1):
    if dp[-1][num]:
        c0 = num
        c1 = n - num
        res = c0 * (c0 - 1) // 2 + c1 * (c1 - 1) // 2
        ans = min(ans, res)
print(ans)