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)
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)
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)

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)

-from collections import deque +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 + -matrix = [[0] * n for i in range(n)] -for i in range(m): -    a, b = info[i] +graph = [set() for i in range(n)] +for a, b in info: -    matrix[a][b] = 1 -    matrix[b][a] = 1 -graph = [[] for i in range(n)] +    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 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)] +    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)] -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) +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)