import sys

input = sys.stdin.readline

from collections import defaultdict



# 切り離す必要があるものを辺として、二部グラフの判定

N,M = list(map(int,input().split()))



# 補グラフ

graph = [set(x for x in range(N) if x != y) for y in range(N)]

for _ in range(M):

    a,b = [int(x) - 1 for x in input().split()]

    graph[a].remove(b)

    graph[b].remove(a)



color = [None] * N

size = defaultdict(lambda: [0,0])



def set_color(root,x,c):

    size[root][c] += 1

    color[x] = c

    for y in graph[x]:

        if color[y] is None:

            set_color(root,y,1-c)

        elif color[y] == color[x]:

            print((-1))

            exit()



for x in range(N):

    if color[x] is None:

        set_color(x,x,0)



# 二部グラフになるべく平均的に分けたい

# 可能なサイズの集合を持つ



se = {0}

for x,y in list(size.values()):

    se = set(s + x for s in se) | set(s + y for s in se)



answer = min(x*(x-1)//2+(N-x)*(N-x-1)//2 for x in se)

print(answer)
import sys

input = sys.stdin.readline

from collections import defaultdict



# 切り離す必要があるものを辺として、二部グラフの判定

N,M = list(map(int,input().split()))



# 補グラフ

rng = list(range(1,N+1))

graph = [None] + [set(x for x in rng if x != y) for y in rng]

for _ in range(M):

    a,b = list(map(int,input().split()))

    graph[a].remove(b)

    graph[b].remove(a)



color = [None] * (1+N)

size = defaultdict(lambda: [0,0])



def set_color(root,x,c):

    size[root][c] += 1

    color[x] = c

    for y in graph[x]:

        if color[y] is None:

            set_color(root,y,1-c)

        elif color[y] == color[x]:

            print((-1))

            exit()



for x in rng:

    if color[x] is None:

        set_color(x,x,0)



# 二部グラフになるべく平均的に分けたい

# 可能なサイズの集合を持つ



se = {0}

for x,y in list(size.values()):

    se = set(s + x for s in se) | set(s + y for s in se)



answer = min(x*(x-1)//2+(N-x)*(N-x-1)//2 for x in se)

print(answer)
import sys

input = sys.stdin.readline
from collections import defaultdict

# 切り離す必要があるものを辺として、二部グラフの判定
N, M = list(map(int, input().split()))
# 補グラフ
graph = [set(x for x in range(N) if x != y) for y in range(N)]
for _ in range(M):
    a, b = [int(x) - 1 for x in input().split()]
    graph[a].remove(b)
    graph[b].remove(a)
color = [None] * N
size = defaultdict(lambda: [0, 0])


def set_color(root, x, c):
    size[root][c] += 1
    color[x] = c
    for y in graph[x]:
        if color[y] is None:
            set_color(root, y, 1 - c)
        elif color[y] == color[x]:
            print((-1))
            exit()


for x in range(N):
    if color[x] is None:
        set_color(x, x, 0)
# 二部グラフになるべく平均的に分けたい
# 可能なサイズの集合を持つ
se = {0}
for x, y in list(size.values()):
    se = set(s + x for s in se) | set(s + y for s in se)
answer = min(x * (x - 1) // 2 + (N - x) * (N - x - 1) // 2 for x in se)
print(answer)

import sys

input = sys.stdin.readline
from collections import defaultdict

# 切り離す必要があるものを辺として、二部グラフの判定
N, M = list(map(int, input().split()))
# 補グラフ
rng = list(range(1, N + 1))
graph = [None] + [set(x for x in rng if x != y) for y in rng]
for _ in range(M):
    a, b = list(map(int, input().split()))
    graph[a].remove(b)
    graph[b].remove(a)
color = [None] * (1 + N)
size = defaultdict(lambda: [0, 0])


def set_color(root, x, c):
    size[root][c] += 1
    color[x] = c
    for y in graph[x]:
        if color[y] is None:
            set_color(root, y, 1 - c)
        elif color[y] == color[x]:
            print((-1))
            exit()


for x in rng:
    if color[x] is None:
        set_color(x, x, 0)
# 二部グラフになるべく平均的に分けたい
# 可能なサイズの集合を持つ
se = {0}
for x, y in list(size.values()):
    se = set(s + x for s in se) | set(s + y for s in se)
answer = min(x * (x - 1) // 2 + (N - x) * (N - x - 1) // 2 for x in se)
print(answer)

-graph = [set(x for x in range(N) if x != y) for y in range(N)] +rng = list(range(1, N + 1)) +graph = [None] + [set(x for x in rng if x != y) for y in rng] -    a, b = [int(x) - 1 for x in input().split()] +    a, b = list(map(int, input().split())) -color = [None] * N +color = [None] * (1 + N) -for x in range(N): +for x in rng: