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

E = [[] for _ in range(N+1)]

E_mat = [[0]*(N+1) for _ in range(N+1)]

for _ in range(M):

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

    E[a].append(b)

    E[b].append(a)

    E_mat[a][b] = 1

    E_mat[b][a] = 1

E_inv = [[] for _ in range(N+1)]

for v, e_mat in enumerate(E_mat[1:], 1):

    for u, e in enumerate(e_mat[1:], 1):

        if e==0 and v!=u:

            E_inv[v].append(u)

colors = [0] * (N+1)

def dfs(v, c):

    colors[v] = c

    cnts[c] += 1

    for u in E_inv[v]:

        if colors[u] == c:

            print((-1))

            exit()

        if colors[u] != 0:

            continue

        dfs(u, -c)

K = []

for v in range(1, N+1):

    cnts = [0, 0, 0]

    if colors[v] == 0:

        dfs(v, 1)

    K.append(cnts[1:])



dp = 1

for a, b in K:

    dp = dp<<a | dp<<b



dp = bin(dp)[:1:-1]

ans = 0

mi = float("inf")

for i, c in enumerate(dp):

    if c=="1":

        if mi > abs(N/2-i):

            mi = abs(N/2-i)

            ans = i



print((ans*(ans-1)//2 + (N-ans)*(N-ans-1)//2))

def main():

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

    E_mat = [[0]*(N+1) for _ in range(N+1)]

    for _ in range(M):

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

        E_mat[a][b] = 1

        E_mat[b][a] = 1

    E_inv = [[] for _ in range(N+1)]

    for v, e_mat in enumerate(E_mat[1:], 1):

        for u, e in enumerate(e_mat[1:], 1):

            if e==0 and v!=u:

                E_inv[v].append(u)

    colors = [0] * (N+1)

    

    def dfs(v, c):

        colors[v] = c

        cnts[c] += 1

        for u in E_inv[v]:

            if colors[u] == c:

                print((-1))

                exit()

            if colors[u] != 0:

                continue

            dfs(u, -c)

            

    K = []

    for v in range(1, N+1):

        cnts = [0, 0, 0]

        if colors[v] == 0:

            dfs(v, 1)

        K.append(cnts[1:])

    

    dp = 1

    for a, b in K:

        dp = dp<<a | dp<<b

    

    dp = bin(dp)[:1:-1]

    ans = 0

    mi = float("inf")

    for i, c in enumerate(dp):

        if c=="1":

            if mi > abs(N/2-i):

                mi = abs(N/2-i)

                ans = i

    

    print((ans*(ans-1)//2 + (N-ans)*(N-ans-1)//2))



main()

N, M = list(map(int, input().split()))
E = [[] for _ in range(N + 1)]
E_mat = [[0] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
    a, b = list(map(int, input().split()))
    E[a].append(b)
    E[b].append(a)
    E_mat[a][b] = 1
    E_mat[b][a] = 1
E_inv = [[] for _ in range(N + 1)]
for v, e_mat in enumerate(E_mat[1:], 1):
    for u, e in enumerate(e_mat[1:], 1):
        if e == 0 and v != u:
            E_inv[v].append(u)
colors = [0] * (N + 1)


def dfs(v, c):
    colors[v] = c
    cnts[c] += 1
    for u in E_inv[v]:
        if colors[u] == c:
            print((-1))
            exit()
        if colors[u] != 0:
            continue
        dfs(u, -c)


K = []
for v in range(1, N + 1):
    cnts = [0, 0, 0]
    if colors[v] == 0:
        dfs(v, 1)
    K.append(cnts[1:])
dp = 1
for a, b in K:
    dp = dp << a | dp << b
dp = bin(dp)[:1:-1]
ans = 0
mi = float("inf")
for i, c in enumerate(dp):
    if c == "1":
        if mi > abs(N / 2 - i):
            mi = abs(N / 2 - i)
            ans = i
print((ans * (ans - 1) // 2 + (N - ans) * (N - ans - 1) // 2))

def main():
    N, M = list(map(int, input().split()))
    E_mat = [[0] * (N + 1) for _ in range(N + 1)]
    for _ in range(M):
        a, b = list(map(int, input().split()))
        E_mat[a][b] = 1
        E_mat[b][a] = 1
    E_inv = [[] for _ in range(N + 1)]
    for v, e_mat in enumerate(E_mat[1:], 1):
        for u, e in enumerate(e_mat[1:], 1):
            if e == 0 and v != u:
                E_inv[v].append(u)
    colors = [0] * (N + 1)

    def dfs(v, c):
        colors[v] = c
        cnts[c] += 1
        for u in E_inv[v]:
            if colors[u] == c:
                print((-1))
                exit()
            if colors[u] != 0:
                continue
            dfs(u, -c)

    K = []
    for v in range(1, N + 1):
        cnts = [0, 0, 0]
        if colors[v] == 0:
            dfs(v, 1)
        K.append(cnts[1:])
    dp = 1
    for a, b in K:
        dp = dp << a | dp << b
    dp = bin(dp)[:1:-1]
    ans = 0
    mi = float("inf")
    for i, c in enumerate(dp):
        if c == "1":
            if mi > abs(N / 2 - i):
                mi = abs(N / 2 - i)
                ans = i
    print((ans * (ans - 1) // 2 + (N - ans) * (N - ans - 1) // 2))


main()

-N, M = list(map(int, input().split())) -E = [[] for _ in range(N + 1)] -E_mat = [[0] * (N + 1) for _ in range(N + 1)] -for _ in range(M): -    a, b = list(map(int, input().split())) -    E[a].append(b) -    E[b].append(a) -    E_mat[a][b] = 1 -    E_mat[b][a] = 1 -E_inv = [[] for _ in range(N + 1)] -for v, e_mat in enumerate(E_mat[1:], 1): -    for u, e in enumerate(e_mat[1:], 1): -        if e == 0 and v != u: -            E_inv[v].append(u) -colors = [0] * (N + 1) +def main(): +    N, M = list(map(int, input().split())) +    E_mat = [[0] * (N + 1) for _ in range(N + 1)] +    for _ in range(M): +        a, b = list(map(int, input().split())) +        E_mat[a][b] = 1 +        E_mat[b][a] = 1 +    E_inv = [[] for _ in range(N + 1)] +    for v, e_mat in enumerate(E_mat[1:], 1): +        for u, e in enumerate(e_mat[1:], 1): +            if e == 0 and v != u: +                E_inv[v].append(u) +    colors = [0] * (N + 1) + +    def dfs(v, c): +        colors[v] = c +        cnts[c] += 1 +        for u in E_inv[v]: +            if colors[u] == c: +                print((-1)) +                exit() +            if colors[u] != 0: +                continue +            dfs(u, -c) + +    K = [] +    for v in range(1, N + 1): +        cnts = [0, 0, 0] +        if colors[v] == 0: +            dfs(v, 1) +        K.append(cnts[1:]) +    dp = 1 +    for a, b in K: +        dp = dp << a | dp << b +    dp = bin(dp)[:1:-1] +    ans = 0 +    mi = float("inf") +    for i, c in enumerate(dp): +        if c == "1": +            if mi > abs(N / 2 - i): +                mi = abs(N / 2 - i) +                ans = i +    print((ans * (ans - 1) // 2 + (N - ans) * (N - ans - 1) // 2)) -def dfs(v, c): -    colors[v] = c -    cnts[c] += 1 -    for u in E_inv[v]: -        if colors[u] == c: -            print((-1)) -            exit() -        if colors[u] != 0: -            continue -        dfs(u, -c) - - -K = [] -for v in range(1, N + 1): -    cnts = [0, 0, 0] -    if colors[v] == 0: -        dfs(v, 1) -    K.append(cnts[1:]) -dp = 1 -for a, b in K: -    dp = dp << a | dp << b -dp = bin(dp)[:1:-1] -ans = 0 -mi = float("inf") -for i, c in enumerate(dp): -    if c == "1": -        if mi > abs(N / 2 - i): -            mi = abs(N / 2 - i) -            ans = i -print((ans * (ans - 1) // 2 + (N - ans) * (N - ans - 1) // 2)) +main()