In the State of Takahashi in AtCoderian Federation, there are N cities, numbered 1, 2, ..., N.
M bidirectional roads connect these cities.
The i-th road connects City A_i and City B_i.
Every road connects two distinct cities.
Also, for any two cities, there is at most one road that directly connects them.
One day, it was decided that the State of Takahashi would be divided into two states, Taka and Hashi.
After the division, each city in Takahashi would belong to either Taka or Hashi.
It is acceptable for all the cities to belong Taka, or for all the cities to belong Hashi.
Here, the following condition should be satisfied:
 - Any two cities in the same state, Taka or Hashi, are directly connected by a road.
Find the minimum possible number of roads whose endpoint cities belong to the same state.
If it is impossible to divide the cities into Taka and Hashi so that the condition is satisfied, print -1.

-----Constraints-----
 - 2 \leq N \leq 700
 - 0 \leq M \leq N(N-1)/2
 - 1 \leq A_i \leq N
 - 1 \leq B_i \leq N
 - A_i \neq B_i
 - If i \neq j, at least one of the following holds: A_i \neq A_j and B_i \neq B_j.
 - If i \neq j, at least one of the following holds: A_i \neq B_j and B_i \neq A_j.

-----Input-----
Input is given from Standard Input in the following format:
N M
A_1 B_1
A_2 B_2
:
A_M B_M

-----Output-----
Print the answer.

-----Sample Input-----
5 5
1 2
1 3
3 4
3 5
4 5

-----Sample Output-----
4

For example, if the cities 1, 2 belong to Taka and the cities 3, 4, 5 belong to Hashi, the condition is satisfied.
Here, the number of roads whose endpoint cities belong to the same state, is 4.

Difficulty: competition

Starter code:

Solutions:
from collections import deque

N, M = list(map(int, input().split()))
adj = [[1 for _ in range(N + 1)] for _ in range(N + 1)]
for _ in range(M):
    a, b = list(map(int, input().split()))
    adj[a][b] = 0
    adj[b][a] = 0
adj_inv = [[] for _ in range(N + 1)]
for i in range(1, N+1):
    for j in range(i+1, N+1):
        if adj[i][j] == 1:
            adj_inv[i].append(j)
            adj_inv[j].append(i)

seen = [0] * (N+1)
num = []
for i in range(1, N+1):
    if seen[i] == 0:
        plus = 0
        minus = 0
        que = deque()
        que.append(i)
        seen[i] = 1
        plus += 1
        while que:
            v = que.pop()
            u_list = adj_inv[v]
            for u in u_list:
                if seen[u] == 0:
                    que.append(u)
                    seen[u] = -seen[v]
                    if seen[u] == 1:
                        plus += 1
                    else:
                        minus += 1
                else:
                    if seen[u] == seen[v]:
                        print((-1))
                        return
        num.append((min(plus, minus), max(plus, minus)))

min_sum = 0
add = []
for i in range(len(num)):
    min_sum += num[i][0]
    add.append(num[i][1] - num[i][0])

dp = [[0 for _ in range((N // 2) + 1)] for _ in range(len(add) + 1)]
dp[0][min_sum] = 1
for i in range(len(add)):
    for j in range(min_sum, (N // 2) + 1):
        if dp[i][j] == 1:
            if j + add[i] <= (N // 2):
                dp[i+1][j+add[i]] = 1
            dp[i+1][j] = 1

dp_last = dp[-1]
for i in range(len(dp_last)-1, -1, -1):
    if dp_last[i] == 1:
        N1 = i
        break

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


#!/usr/bin/env python3
# -*- coding: utf-8 -*-

class Graph:
    def __init__(self, nvert, edges):
        self.adj = [[False] * nvert for i in range(nvert)]
        for e in edges:
            u, v = e
            self.adj[u][v] = True
            self.adj[v][u] = True

    def __str__(self):
        return str(self.adj)

    # 節点数
    def nvertices(self):
        return len(self.adj)

    # 補グラフ
    def complement(self):
        nv = len(self.adj)
        g  = Graph(nv, [])
        for u in range(nv):
            for v in range(nv):
                if u == v: continue
                g.adj[u][v] = not self.adj[u][v]
                g.adj[v][u] = not self.adj[v][u]
        return g

    # 連結成分であるグラフのリスト
    def connectedcomps(self):
        self.visited = [False] * self.nvertices()
        ccs = []
        for v in range(self.nvertices()):
            if not self.visited[v]:
                vs = []
                self.__connectedcomp(v, vs)
                cc = self.inducedsubgraph(vs)
                ccs.append(cc)
        self.visited = None
        return ccs

    # vを含む連結成分 (節点のリスト)
    def __connectedcomp(self, v, vs):
        if self.visited[v]: return
        self.visited[v] = True
        vs.append(v)
        for u in range(self.nvertices()):
            if self.adj[v][u]:
                self.__connectedcomp(u, vs)

    # 誘導部分グラフ
    def inducedsubgraph(self, vs):
        n = len(vs)
        # [3, 1, 4] -> {3:0, 1:1, 4:2}
        m = {}
        for i in range(n):
            m[vs[i]] = i

        sg = Graph(n, [])
        for v in vs:
            for u in range(self.nvertices()):
                if self.adj[v][u]:
                    sg.adj[m[v]][m[u]] = True
                    sg.adj[m[u]][m[v]] = True
        return sg

    # 2部グラフならば2グループの各節点数の組。2部グラフでなければFalse
    # 組を返すときは(大,小)の順
    def isbipartite(self):
        self.color = [None] * self.nvertices()
        self.color[0] = 0
        if not self.__isbipartite(0):
            return False
        m = sum(1 for c in self.color if c == 0)
        n = sum(1 for c in self.color if c == 1)
        assert m + n == self.nvertices()
        return (max(m, n), min(m, n))

    def __isbipartite(self, v):
        for u in range(self.nvertices()):
            if self.adj[v][u]:
                if self.color[u] == None:
                    self.color[u] = 1 - self.color[v]
                    if not self.__isbipartite(u):
                        return False
                elif self.color[u] != 1 - self.color[v]:
                    return False
        return True


# 入力
N, M = [int(w) for w in input().split()]
edges = []
for i in range(M):
    a, b = [int(w) for w in input().split()]
    edges.append((a - 1, b - 1))

# 入力されたグラフの補グラフ g が2部グラフ
g = Graph(N, edges).complement()
ccs = g.connectedcomps()
bs  = [cc.isbipartite() for cc in ccs]
if not all(bs):
    print(-1)
    return

# (連結成分が複数ある場合),
# 2グループの節点数の差が最小となるような分け方を求める
diffs = [t[0] - t[1] for t in bs]
sums = {0}
for d in diffs:
    newsums = set()
    for s in sums:
        newsums.add(s + d)
    sums.update(newsums)

halfdiff = sum(diffs)/2
nearlyhalfdiff = min((abs(s - halfdiff), s) for s in sums)[1]

# 節点数の差を最小にすると，その差はdiffになる
diff = abs(sum(diffs) - 2 * nearlyhalfdiff)

# グループの節点数 (x, y)
x = (N - diff) // 2
y = N - x

# 完全グラフの辺数
x = x * (x - 1) // 2
y = y * (y - 1) // 2

print(x + y)

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

E = [[False]*N for _ in range(N)]

for n in range(N):
  E[n][n] = True

for _ in range(M):
  a,b = map(int,input().split())
  a,b = a-1,b-1
  E[a][b] = True
  E[b][a] = True


unvisited = set(range(N))
color = [None]*N
components = []

while unvisited:
  v0 = next(iter(unvisited))
  count = [0,0]

  stack = [(v0,False)]
  while stack:
    v,c = stack.pop()
    if color[v] is None:
      color[v] = c
      unvisited.discard(v)
      count[c] += 1
      for u,f in enumerate(E[v]):
        if not f:
          stack.append((u, not c))

    elif color[v] != c:
      print(-1)
      return

  components.append(count)

# DP
L = N//2+1
dp = [False]*L


dp[0] = True

for a,b in components:
  ndp = [False]*L
  for i,f in enumerate(dp):
    if f:
      if i+a < L:
        ndp[i+a] = True
      if i+b < L:
        ndp[i+b] = True
  dp = ndp

for i,f in zip(reversed(range(L)), reversed(dp)):
  if f:
    break
j = N - i

print(i*(i-1)//2 + j*(j-1)//2)

import queue
N,M=list(map(int,input().split()))
G=[[1 for i in range(N)] for i in range(N)]
H=[[] for i in range(N)]
for i in range(N):
    G[i][i]-=1
for i in range(M):
    a,b=list(map(int,input().split()))
    G[a-1][b-1]-=1
    G[b-1][a-1]-=1
for i in range(N):
    for j in range(N):
        if G[i][j]==1:
            H[i].append(j)
A=[[[],[]]]
k=0
q=queue.Queue()
reached=[0 for i in range(N)]
dist=[-1 for i in range(N)]
for i in range(N):
    if reached[i]==1:
        continue
    q.put(i)
    reached[i]=1
    dist[i]=0
    while(not(q.empty())):
        r=q.get()
        A[k][dist[r]].append(r)
        for p in H[r]:
            if reached[p]==0:
                q.put(p)
                dist[p]=(dist[r]+1)%2
                reached[p]=1
    k+=1
    A.append([[],[]])
for i in range(k):
    for j in range(2):
        for x in A[i][j]:
            for y in A[i][j]:
                if x==y:
                    continue
                if G[x][y]==1:
                    print((-1))
                    return
B=[]
for i in range(k):
    B.append((len(A[i][0]),len(A[i][1])))
dp=[[0 for i in range(N+1)] for i in range(k+1)]
dp[0][0]=1
for i in range(1,k+1):
    for j in range(N+1):
        if dp[i-1][j]==0:
            continue
        dp[i][j+B[i-1][0]]=1
        dp[i][j+B[i-1][1]]=1
delta=N
for i in range(N+1):
    if dp[k][i]==1:
        tmp=abs(N-2*i)
        if tmp<delta:
            delta=tmp
X=(N+delta)//2
Y=(N-delta)//2
print(((X*(X-1)+Y*(Y-1))//2))


N,M=list(map(int,input().split()))
ROAD=[None]*M

for i in range(M):
    ROAD[i]=tuple(sorted(list(map(int,input().split()))))
  
import itertools

NOROAD=list(itertools.combinations(list(range(1,N+1)),2))

NOROAD=set(NOROAD) - set(ROAD)

Group=[[i,[]] for i in range(N+1)]

def find(x):
    while Group[x][0] != x:
        x=Group[x][0]
    return x


for i in NOROAD:
    a,b=i
    #print(a,b)
    Group[a][1]+=[b]
    Group[b][1]+=[a]

    if find(a) != find(b):
        Group[find(a)][0]=min(find(a),find(b))
        Group[find(b)][0]=min(find(a),find(b))
        Group[a][0]=min(find(a),find(b))
        Group[b][0]=min(find(a),find(b))

GroupSORT=[[i,j[1]] for i,j in enumerate(Group)]
GroupSORT.sort(key=lambda x:len(x[1]))
NUMBERING=[[find(i),"none"] for i in range(N+1)]
CHECK=[0 for i in range(N+1)]

for i in range(N):
    if CHECK[find(GroupSORT[i][0])]==0:
        
        NUMBERING[GroupSORT[i][0]][1]=0
        CHECK[find(GroupSORT[i][0])]=1

CONDITION=1
#print(NUMBERING)


repeat_condition=1
while repeat_condition==1:

    repeat_condition=0

    for i in range(1,N+1):
        if NUMBERING[i][1]==0:
            for j in Group[i][1]:
                if NUMBERING[j][1]==0:
                    CONDITION=0
                    break
                elif NUMBERING[j][1]=="none":
                    NUMBERING[j][1]=1
                    repeat_condition=1

        if NUMBERING[i][1]==1:
            for j in Group[i][1]:
                if NUMBERING[j][1]==1:
                    CONDITION=0
                    break
                elif NUMBERING[j][1]=="none":
                    NUMBERING[j][1]=0
                    repeat_condition=1


import sys
if CONDITION==0:
    print((-1))
    return

NUMBERS=set()
for i in range(1,len(NUMBERING)):
    NUMBERS=NUMBERS|{NUMBERING[i][0]}

count=[]
for i in NUMBERS:
    count+=[(i,NUMBERING.count([i,0]),NUMBERING.count([i,1]))]

DP=[set() for i in range(len(count))]
DP[0]={count[0][1],count[0][2]}

for i in range(1,len(count)):
    for k in DP[i-1]:
        DP[i]=DP[i]|{k+count[i][1],k+count[i][2]}

DIVIDE=list(DP[len(count)-1])
#print(DIVIDE)
for i in range(len(DIVIDE)):
    DIVIDE[i]=abs(DIVIDE[i]-N/2)

x=int(min(DIVIDE)+N/2)

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


# import math
# n,k = list(map(int,input().split()))
# print(math.ceil((n-1)/(k-1)))

n,m = list(map(int,input().split()))
road = {}
whole = []
for i in range(1,n+1):
    whole.append(i)
    road[i] = set()
whole = set(whole)

for i in range(m):
    a,b = list(map(int, input().split()))
    road[a].add(b)
    road[b].add(a)

taka = []
hashi = []
used = set()
no = 0
for x in road:
    l = set()
    r = set()
    l1 = []
    r1 = []
    if x in used:
        continue
    else:
        l.add(x)
        l1.append(x)
        used.add(x)
        for y in whole - road[x]:
            if y not in used:
                r.add(y)
                r1.append(y)
                used.add(y)
    while l1 != [] or r1 != []:
        while r1 != []:
            t = r1.pop()
            for y in whole-road[t]-used-l:
                l.add(y)
                l1.append(y)
                used.add(y)
        while l1 != []:
            t = l1.pop()
            for y in whole-road[t]-used-r:
                    r.add(y)
                    r1.append(y)
                    used.add(y)
    r = list(r)
    l = list(l)

    for i in range(len(l)):
        for j in range(i+1,len(l)):
            if l[j] not in road[l[i]]:
                no = 1
                break
        if no == 1:break
    if no == 1:break
    for i in range(len(r)):
        for j in range(i+1,len(r)):
            if r[j] not in road[r[i]]:
                no = 1
                break
        if no == 1:break
    if no == 1:break

    taka.append(len(l))
    hashi.append(len(r))

if no == 1:print((-1))
else:
    res = [abs(taka[i]-hashi[i]) for i in range(len(taka))]
    res.sort(reverse=-1)
    delta = 0
    for x in res:
        if delta>0:delta-=x
        else:delta+=x
    left = (n+delta)/2
    right = (n-delta)/2
    result = int((left*(left-1)+right*(right-1))/2)
    print(result)




import sys
sys.setrecursionlimit(10**7)
n,m = map(int,input().split())
G = [[1]*n for i in range(n)]
for i in range(m):
  a,b = map(int,input().split())
  a -=1;b-=1
  G[a][b] = G[b][a] = 0
colors = [-1 for i in range(n)]
possible = True
ni = []
def dfs(x,y):
  colors[x] = y
  k[y] += 1
  for l in range(n):
    if l == x or G[x][l] == 0:
      continue
    if colors[l] == -1:
      dfs(l,1-y)
    elif colors[l] != 1-y:
      nonlocal possible
      possible = False
for i in range(n):
  k = [0,0]
  if colors[i] != -1:
    continue
  dfs(i,0)
  ni.append([k[0],k[1]])
if possible == False:
  print(-1)
  return
dp =[0]*701
dp[0] = 1
for i in ni:
  for j in range(700,-1,-1):
    if dp[j]:
      dp[j] = 0
      dp[j+i[0]] = 1
      dp[j+i[1]] = 1
ans = float("inf")
for i in range(0,701):
  if dp[i]:
    tmp = (n-i)*(n-i-1)//2 + i*(i-1)//2
    ans = min(tmp,ans)
print(ans)

# 問題の趣旨：できるだけ辺が少なくなるように2つの完全グラフに分けたい
# まず、2つの完全グラフに分けられるのかを調べる必要がある。
# これが不可能であれば-1を出力して即座に終了。
# 分けられる場合は、できるだけ街の数を均等にしたい。

# 以下のアルゴリズムを考える。
# まずお互い繋がっていない都市の組A,Bを選ぶ。
# すると、Aにしか繋がっていない街、Bにしか繋がっていない街、
# 両方に繋がっている街の3グループに分かれる。
# 最初の2グループについてはグループのサイズを保存しておく。
# 最後のグループが空でない場合は、このグループに対してまた同様の処理を行う。
# 街がなくなるか、両方に繋がっている街のグループが
# 完全グラフになった時点で終了。

# 上記のアルゴリズムにより、グループのサイズの列と最後に残った街の数が求められる。
# これをもとに、動的計画法で考えられる街の振り分け方を全て洗い出す。
# 最も均等に近く振り分けた場合について、完全グラフの辺数を計算して
# 出力すれば問題が解ける。

def main():
    from sys import stdin
    input = stdin.readline
    n, m = list(map(int, input().split()))
    ab = [list(map(int, input().split())) for _ in [0]*m]

    rest = n  # 残りの辺
    g = [set() for _ in [0]*n]
    [g[a-1].add(b-1) for a, b in ab]
    [g[b-1].add(a-1) for a, b in ab]
    s = set([i for i in range(n)])

    a_list, b_list = [], []
    while True:
        if m == rest*(rest-1)//2:
            break
        a = [-1, 10**10]
        for i in s:
            length = len(g[i])
            if length < a[1]:
                a = [i, length]
        a = a[0]
        b = [-1, 10**10]
        for i in s-g[a]-{a}:
            length = len(g[i])
            if length < b[1]:
                b = [i, length]
        b = b[0]
        a_set, b_set = {a}, {b}
        s.remove(a)
        s.remove(b)
        rest -= 2
        remain = set()  # 最後のグループ
        for i in s:
            flag_a = True
            for j in a_set:
                if j not in g[i]:
                    flag_a = False
                else:
                    g[i].remove(j)
                    g[j].remove(i)
                    m -= 1
            flag_b = True
            for j in b_set:
                if j not in g[i]:
                    flag_b = False
                else:
                    g[i].remove(j)
                    g[j].remove(i)
                    m -= 1
            if flag_a+flag_b == 0:
                print((-1))
                return
            elif flag_a*flag_b == 0:
                q = {i}
                flag = flag_a  # True→A、False→B
                while q:
                    qq = set()
                    while q:
                        i = q.pop()
                        if flag:
                            a_set.add(i)
                        else:
                            b_set.add(i)
                        for j in remain:
                            if j not in g[i]:
                                qq.add(j)
                            else:
                                g[i].remove(j)
                                g[j].remove(i)
                                m -= 1
                        for j in q:
                            g[i].remove(j)
                            g[j].remove(i)
                            m -= 1
                    for i in qq:
                        remain.remove(i)
                    flag ^= True
                    q = qq
            else:
                remain.add(i)
        for i in (a_set | b_set)-{a}-{b}:
            s.remove(i)
            rest -= 1

        a_list.append(len(a_set))
        b_list.append(len(b_set))

    k = len(a_list)
    dp = [False]*(n+1)
    dp[0] = True

    for i in range(k):
        a, b = a_list[i], b_list[i]
        dp2 = [False]*(n+1)
        for j in range(n-max(a, b)+1):
            dp2[j+a] |= dp[j]
            dp2[j+b] |= dp[j]
        dp = dp2

    ans = 10**10
    for j in range(rest+1):
        for i in range(n-j+1):
            if dp[i]:
                p = i+j
                q = n-p
                ans = min(ans, p*(p-1)//2+q*(q-1)//2)

    print(ans)


main()


import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(0,-1),(1,0),(0,1),(-1,0)]
ddn = [(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,-1),(-1,0),(-1,1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    a = [LI_() for _ in range(m)]
    ss = [set() for _ in range(n)]
    for b,c in a:
        ss[b].add(c)
        ss[c].add(b)
    ts = [set(list(range(n))) - set([_]) for _ in range(n)]
    for i in range(n):
        ts[i] -= ss[i]

    d = []
    u = set()
    for i in range(n):
        if i in u:
            continue
        ab = set([i])
        nb = set([i])
        ac = set()
        nc = set()
        f = True
        while f:
            f = False
            k = set()
            nc = set()
            for j in nb:
                nc |= ts[j]
            nc -= ac
            ac |= nc
            nb = set()
            for j in nc:
                nb |= ts[j]
            nb -= ab
            ab |= nb
            if nb:
                f = True
        if ab & ac:
            return -1
        d.append((len(ab),len(ac)))
        u |= ab
        u |= ac
    r = set([0])
    for b,c in d:
        t = set()
        for k in r:
            t.add(k+b)
            t.add(k+c)
        r = t
    rr = inf
    for t in r:
        nt = n - t
        if t == 0 or nt == 0:
            continue
        tr = t * (t-1) // 2
        tr += nt * (nt-1) // 2
        if rr > tr:
            rr = tr
    return rr


print(main())



from collections import deque
N, M = map(int, input().split())
G0 = [set([i]) for i in range(N)]

A = set(range(N))

for i in range(M):
    a, b = map(int, input().split())
    G0[a-1].add(b-1)
    G0[b-1].add(a-1)

G = [A - g for g in G0]

b = 1
c = [-1]*N
for i in range(N):
    if c[i] != -1:
        continue
    p = 0; s = 0
    que = deque([i])
    c[i] = 0
    while que:
        v = que.popleft()
        s += 1
        if c[v] == 0:
            p += 1
        for w in G[v]:
            if c[w] == -1:
                c[w] = c[v]^1
                que.append(w)
            elif c[w] == c[v]:
                print(-1)
                return
    b = (b << p) | (b << (s-p))

ans = 10**18
for i in range(N+1):
    if (b >> i) & 1:
        ans = min(ans, i*(i-1)//2 + (N-i)*(N-i-1)//2)
print(ans)

from collections import Counter
import numpy as np

class DisjointSet:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0]*size
    
    def find(self, x):
        stack = []
        parent = self.parent
        while parent[x] != x:
            stack.append(x)
            x = parent[x]
        for y in stack:
            parent[y] = x
        return x

    def union(self, x, y):
        xr, yr = self.find(x), self.find(y)
        
        if self.rank[xr] > self.rank[yr]:
            self.parent[yr] = xr
        elif self.rank[xr] < self.rank[yr]:
            self.parent[xr] = yr
        elif xr != yr:
            self.parent[yr] = xr
            self.rank[xr] += 1

def check_bipartiteness(n_vertices, edges):
    ds = DisjointSet(2*n_vertices)

    for a,b in edges:
        ds.union(a, b+n_vertices)
        ds.union(b, a+n_vertices)
    
    next_color = 0
    color = [-1]*(2*n_vertices)
    for v in range(n_vertices):
        ra = ds.find(v)
        rb = ds.find(v+n_vertices)
        if ra == rb:
            return None
        if color[ra] < 0:
            color[ra] = next_color
            color[rb] = next_color+1
            next_color += 2
        color[v] = color[ra]
        color[v+n_vertices] = color[rb]
    return color[:n_vertices]



n,m = list(map(int,input().split()))

mat = [[True]*t for t in range(n)]

for _ in range(m):
    a,b = list(map(int,input().split()))
    if a < b:
        a,b = b,a
    mat[a-1][b-1] = False

edges = ((a,b) for a in range(n) for b in range(a) if mat[a][b])

colors = check_bipartiteness(n, edges)
if colors is None:
    print((-1))
    return

cnt = Counter(colors)
dp = np.zeros(n,dtype=bool)
dp[0] = True

for i in range(n):
    a,b = cnt[i*2],cnt[i*2+1]
    if a == 0 and b == 0:
        break
    d = abs(a-b)
    if d == 0:
        continue
    ndp = np.zeros(n,dtype=bool)
    ndp[d:] = dp[:-d]
    ndp[:-d] |= dp[d:]
    ndp[:d] |= dp[d-1::-1]
    dp = ndp
x = list(dp).index(True)

a = (n-x)//2
b = n-a

print((a*(a-1)//2 + b*(b-1)//2))


import sys
input = sys.stdin.readline

N, M = map(int, input().split())
graph1 = [[False]*N for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    graph1[a-1][b-1] = True
    graph1[b-1][a-1] = True

graph = [[] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i!=j and not graph1[i][j]:
            graph[i].append(j)


checked = [-1]*N
Color = [None]*N

def bfs(start):
    q = [start]
    checked[start] = start
    Color[start] = 0
    color = 0
    Cs = [1, 0]
    while q:
        qq = []
        color ^= 1
        for p in q:
            for np in graph[p]:
                if checked[np] == -1:
                    checked[np] = start
                    Color[np] = color
                    qq.append(np)
                    Cs[color] += 1
                elif checked[np] == start and color != Color[np]:
                    return [-1, -1]
        q = qq
    return Cs

def main():
    Dif = []
    for i in range(N):
        if checked[i] == -1:
            a, b = bfs(i)
            if a == -1:
                print(-1)
                return
            Dif.append(abs(a-b))
    dp = [False]*(N+1)
    dp[0] = True
    for d in Dif:
        for j in reversed(range(d, N+1)):
            dp[j] = dp[j] or dp[j-d]

    min_dif = 10**15
    S = sum(Dif)
    for j in range(N+1):
        if dp[j]:
            min_dif = min(min_dif, abs(S-j*2))
    
    t1 = (N+min_dif)//2
    t2 = (N-min_dif)//2
    print(t1*(t1-1)//2 + t2*(t2-1)//2)

def __starting_point():
    main()
__starting_point()

import sys
input = sys.stdin.readline
from itertools import combinations
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(m)]
g2d = [[1 for i in range(n+1)] for j in range(n+1)]
for i in range(1,n+1):
  g2d[i][i] = 0
for a,b in ab:
  g2d[a][b] = 0
  g2d[b][a] = 0
graph = [[] for i in range(n+1)]
for i in range(1,n+1):
  for j in range(1,n+1):
    if g2d[i][j]:
      graph[i].append(j)
      graph[j].append(i)
vis = [-1]*(n+1)
oddeven = []
for i in range(1,n+1):
  if vis[i] == -1:
    stack = [i]
    vis[i] = 0
    odd = 0
    even = 1
    while stack:
      x = stack.pop()
      for y in graph[x]:
        if vis[y] == -1:
          vis[y] = vis[x]+1
          if vis[y]%2:
            odd += 1
          else:
            even += 1
          stack.append(y)
        elif (vis[y]-vis[x])%2 == 0:
          print(-1)
          return
    oddeven.append(abs(odd-even))
t = len(oddeven)
s = sum(oddeven)
dp = 1<<s
for x in oddeven:
  dp = (dp<<abs(x)) | (dp>>abs(x))
for i in range(s+1):
  if (dp&1<<(s-i))|(dp&1<<(s+i)):
    ex = i
    break
A,B = (n+ex)//2,(n-ex)//2
print(A*(A-1)//2+B*(B-1)//2)

# 問題の趣旨：できるだけ辺が少なくなるように2つの完全グラフに分けたい
# まず、2つの完全グラフに分けられるのかを調べる必要がある。
# これが不可能であれば-1を出力して即座に終了。
# 分けられる場合は、できるだけ街の数を均等にしたい。

# 以下のアルゴリズムを考える。
# まずお互い繋がっていない都市の組A,Bを選ぶ。
# すると、Aにしか繋がっていない街、Bにしか繋がっていない街、
# 両方に繋がっている街の3グループに分かれる。
# 最初の2グループについてはグループのサイズを保存しておく。
# 最後のグループが空でない場合は、このグループに対してまた同様の処理を行う。
# 街がなくなるか、両方に繋がっている街のグループが
# 完全グラフになった時点で終了。

# 上記のアルゴリズムにより、グループのサイズの列と最後に残った街の数が求められる。
# これをもとに、動的計画法で考えられる街の振り分け方を全て洗い出す。
# 最も均等に近く振り分けた場合について、完全グラフの辺数を計算して
# 出力すれば問題が解ける。

def main():
    from sys import stdin
    input = stdin.readline
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in [0]*m]

    rest = n  # 残りの辺
    g = [set() for _ in [0]*n]
    [g[a-1].add(b-1) for a, b in ab]
    [g[b-1].add(a-1) for a, b in ab]
    s = set([i for i in range(n)])

    a_list, b_list = [], []
    while True:
        if m == rest*(rest-1)//2:
            break
        a = [-1, 10**10]
        for i in s:
            length = len(g[i])
            if length < a[1]:
                a = [i, length]
        a = a[0]
        b = [-1, 10**10]
        for i in s-g[a]-{a}:
            length = len(g[i])
            if length < b[1]:
                b = [i, length]
        b = b[0]
        a_set, b_set = {a}, {b}
        s.remove(a)
        s.remove(b)
        rest -= 2
        remain = set()  # 最後のグループ
        for i in s:
            flag_a = True
            for j in a_set:
                if j not in g[i]:
                    flag_a = False
                else:
                    g[i].remove(j)
                    g[j].remove(i)
                    m -= 1
            flag_b = True
            for j in b_set:
                if j not in g[i]:
                    flag_b = False
                else:
                    g[i].remove(j)
                    g[j].remove(i)
                    m -= 1
            if flag_a+flag_b == 0:
                print(-1)
                return
            elif flag_a*flag_b == 0:
                q = {i}
                flag = flag_a  # True→A、False→B
                while q:
                    qq = set()
                    while q:
                        i = q.pop()
                        if flag:
                            a_set.add(i)
                        else:
                            b_set.add(i)
                        for j in remain:
                            if j not in g[i]:
                                qq.add(j)
                            else:
                                g[i].remove(j)
                                g[j].remove(i)
                                m -= 1
                        for j in q:
                            g[i].remove(j)
                            g[j].remove(i)
                            m -= 1
                    for i in qq:
                        remain.remove(i)
                    flag ^= True
                    q = qq
            else:
                remain.add(i)
        for i in (a_set | b_set)-{a}-{b}:
            s.remove(i)
            rest -= 1

        a_list.append(len(a_set))
        b_list.append(len(b_set))

    k = len(a_list)
    dp = [False]*(n+1)
    dp[0] = True

    for i in range(k):
        a, b = a_list[i], b_list[i]
        dp2 = [False]*(n+1)
        for j in range(n-max(a, b)+1):
            dp2[j+a] |= dp[j]
            dp2[j+b] |= dp[j]
        dp = dp2

    ans = 10**10
    for j in range(rest+1):
        for i in range(n-j+1):
            if dp[i]:
                p = i+j
                q = n-p
                ans = min(ans, p*(p-1)//2+q*(q-1)//2)
    print(ans)


main()

import sys
n, m = list(map(int, input().split()))
N = 2000
G = [[0] * N for i in range(N)]
dp = [[0] * N for i in range(N)]
col = [0] * N
cnt = [0] * 2
visit = [0] * N
for i in range(m):
    a, b = list(map(int, input().split()))
    a, b = a - 1, b - 1
    G[a][b], G[b][a] = 1, 1


def dfs(u, c):
    visit[u] = 1
    col[u] = c
    cnt[c] += 1

    for v in range(n):
        if v == u or G[u][v] == 1:
            continue

        if visit[v] == 1 and col[v] == c:
            return False

        if not visit[v] and not dfs(v, c ^ 1):
            return False

    return True


num = 0
dp[0][0] = 1
for i in range(n):
    if not visit[i]:
        num += 1

        cnt[0], cnt[1] = 0, 0

        if not dfs(i, 0):
            print((-1))
            return

        for j in range(n):
            for k in range(2):
                if j >= cnt[k]:
                    dp[num][j] |= dp[num - 1][j - cnt[k]]

ans = m
for i in range(n):
    if dp[num][i]:
        ans = min(ans, i * (i - 1) // 2 + (n - i) * (n - i - 1) // 2)

print(ans)




import queue
N,M=list(map(int,input().split()))
G=[[1 for i in range(N)] for i in range(N)]
H=[[] for i in range(N)]
for i in range(N):
    G[i][i]-=1
for i in range(M):
    a,b=list(map(int,input().split()))
    G[a-1][b-1]-=1
    G[b-1][a-1]-=1
for i in range(N):
    for j in range(N):
        if G[i][j]==1:
            H[i].append(j)
A=[[[],[]]]
k=0
q=queue.Queue()
reached=[0 for i in range(N)]
dist=[-1 for i in range(N)]
for i in range(N):
    if reached[i]==1:
        continue
    q.put(i)
    reached[i]=1
    dist[i]=0
    while(not(q.empty())):
        r=q.get()
        A[k][dist[r]].append(r)
        for p in H[r]:
            if reached[p]==0:
                q.put(p)
                dist[p]=(dist[r]+1)%2
                reached[p]=1
    k+=1
    A.append([[],[]])
for i in range(k):
    for j in range(2):
        for x in A[i][j]:
            for y in A[i][j]:
                if x==y:
                    continue
                if G[x][y]==1:
                    print((-1))
                    return
B=[]
for i in range(k):
    B.append((len(A[i][0]),len(A[i][1])))
dp=[[0 for i in range(N+1)] for i in range(k+1)]
dp[0][0]=1
for i in range(1,k+1):
    for j in range(N+1):
        if dp[i-1][j]==0:
            continue
        dp[i][j+B[i-1][0]]=1
        dp[i][j+B[i-1][1]]=1
delta=N
for i in range(N+1):
    if dp[k][i]==1:
        tmp=abs(N-2*i)
        if tmp<delta:
            delta=tmp
X=(N+delta)//2
Y=(N-delta)//2
print(((X*(X-1)+Y*(Y-1))//2))


import sys
import math

input = sys.stdin.readline
N, M = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(M)]
connected = [set() for _ in range(N)]
for a, b in AB:
    a -= 1
    b -= 1
    connected[a].add(b)
    connected[b].add(a)
for i in range(N):
    connected[i].add(i)

whole_set = set(range(N))
unconnected = [whole_set-connected[i] for i in range(N)]
assign = [-1] * N
ass_q = []
g = 0
for i in range(N):
    if len(unconnected[i]) != 0:
        assign[i] = g
        for j in unconnected[i]:
            assign[j] = (assign[i] + 1) % 2 + g
            ass_q.append(j)
        break
while len(ass_q) > 0:
    i = ass_q.pop()
    for j in unconnected[i]:
        if assign[j] == -1:
            assign[j] = (assign[i] + 1) % 2 + g
            ass_q.append(j)
        elif assign[j] == assign[i]:
            print((-1))
            return
    if len(ass_q) == 0:
        g += 2
        for i in range(N):
            if len(unconnected[i]) > 0 and assign[i] == -1:
                assign[i] = g
                for j in unconnected[i]:
                    assign[j] = (assign[i] + 1) % 2 + g
                    ass_q.append(j)
                break


groups = [(assign.count(g_), assign.count(g_+1)) for g_ in range(0, g, 2)]
ans = math.inf
not_assign = assign.count(-1)
for b in range(pow(2, len(groups))):
    taka, hashi = 0, 0
    for i in range(len(groups)):
        taka += groups[i][(b>>i)&1]
        hashi += groups[i][((~b)>>i)&1]
    for _ in range(not_assign):
        if taka < hashi:
            taka += 1
        else:
            hashi += 1
    ans = min(ans, (taka*(taka-1))//2 + (hashi*(hashi-1))//2)
print(ans)


# E
from collections import deque
import numpy as np

N, M = map(int, input().split())
G = dict()
for i in range(1, N+1):
    G[i] = dict()
    for j in range(1, N+1):
        if i != j:
            G[i][j] = 1
            
for _ in range(M):
    a, b = map(int, input().split())
    _ = G[a].pop(b)
    _ = G[b].pop(a)
    
res_con = []

done_list = [1] + [0]*N



core = 1

while core != 0:
    
    # BFS
    queue = deque([core])    
    res_flag = True
    
    size_a = 1
    size_b = 0

    done_list[core] = 1
    while len(queue) > 0:
        a = queue.popleft()
        for b in G[a].keys():
            if done_list[b] == done_list[a]:
                res_flag = False
                break
            elif done_list[b] == 0:
                done_list[b] = -1*done_list[a]
                if done_list[a] == 1:
                    size_b += 1
                else:
                    size_a += 1
                queue.append(b)
    
    res_con.append([size_a, size_b])
    
        
    if res_flag == False:
        break
        
    
    core = 0
    for i in range(1, N+1):
        if done_list[i] == 0:
            core = i
            break
            
# summarize
if res_flag == False:
    res = 0
else:
    res_can_s = np.array([0])
    for rr in res_con:
        a = rr[0]
        b = rr[1]
        res_can_s = np.unique(np.concatenate([res_can_s + a, res_can_s + b]))
    res = ((res_can_s*(res_can_s - 1) // 2) + ((N - res_can_s)*(N - res_can_s - 1) // 2)).min()

if res_flag == False:
    print(-1)
else:
    print(res)

import sys
readline = sys.stdin.readline

popcntsum = ((1<<1024) - 1)
Fa = [0] + [popcntsum//((1<<(1<<(i-1)))+1) for i in range(1,11)]
Fb = [0] + [Fa[i]<<(1<<(i-1)) for i in range(1,11)]
fila1 = Fa[1]
filb1 = Fb[1]
fila2 = Fa[2]
filb2 = Fb[2]
fila3 = Fa[3]
filb3 = Fb[3]
fila4 = Fa[4]
filb4 = Fb[4]
fila5 = Fa[5]
filb5 = Fb[5]
fila6 = Fa[6]
filb6 = Fb[6]
fila7 = Fa[7]
filb7 = Fb[7]
fila8 = Fa[8]
filb8 = Fb[8]
fila9 = Fa[9]
filb9 = Fb[9]
fila10 = Fa[10]
filb10 = Fb[10]
def popcount(x):
    x = (x&fila1) + ((x&filb1)>>1)
    x = (x&fila2) + ((x&filb2)>>2)
    x = (x&fila3) + ((x&filb3)>>4)
    x = (x&fila4) + ((x&filb4)>>8)
    x = (x&fila5) + ((x&filb5)>>16)
    x = (x&fila6) + ((x&filb6)>>32)
    x = (x&fila7) + ((x&filb7)>>64)
    x = (x&fila8) + ((x&filb8)>>128)
    x = (x&fila9) + ((x&filb9)>>256)
    x = (x&fila10) + ((x&filb10)>>512)
    return x


def check(S):
    if S == 0:
        return []
    if S < 0:
        return None
    G1 = [G[i]&S for i in range(N)]
    M = popcount(S)
    if M**2 == sum(G1[i] for i in range(N) if S&(1<<i)):
        return [(0, 1)]*M
    st = 0
    A = 0
    for i in range(N):
        if (1<<i) & S:
            st = i
            A = 1<<i
            break
    B = 0
    for i in range(N):
        if not (1<<i) & S:
            continue
        if not (G[st] & (1<<i)):
            B = 1<<i
            break
    T = (((1<<N)-1)^S)|A|B
    na = 1
    nb = popcount(B)
    T2 = None
    while T2 != T:
        T2 = T
        for i in range(N):
            if (1<<i) & T:
                continue
            fa = (na == popcount(G1[i]&A))
            fb = (nb == popcount(G1[i]&B))
            if fa and fb:
                continue
            if fa:
                A |= 1<<i
                T |= 1<<i
                na += 1
                continue
            if fb:
                B |= 1<<i
                T |= 1<<i
                nb += 1
                continue
            return None
    S2 = ((1<<N)-1) ^ T
    
    if na > nb:
        na, nb = nb, na
    ss = check(S2)
    if ss is None:
        return None
    return ss + [(na, nb)] 


N, M = map(int, readline().split())
G = [1<<i for i in range(N)]
for _ in range(M):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    G[a] |= 1<<b
    G[b] |= 1<<a
ss = check((1<<N)-1)
if ss is None:
    print(-1)
else:
    SA, SB = list(map(list, zip(*ss)))
    res = 1
    for sa, sb in zip(SA, SB):
        res = (res<<sa)|(res<<sb)
    ans = 10**9+7
    for i in range(N+1):
        if not (1<<i)&res:
            continue
        ans = min(ans, (i-1)*i//2 + (N-i-1)*(N-i)//2)
    print(ans)

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = list(map(int, input().split()))
mt = [[True]*n for _ in range(n)]
for i in range(m):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    mt[a][b] = False
    mt[b][a] = False
for i in range(n):
    mt[i][i] = False
ns = [[] for _ in range(n)]
for i in range(n):
    for j in range(n):
        if mt[i][j]:
            ns[i].append(j)
            
# 二部グラフ判定 bipertite
def is_bip(ns):
    cs = [None]*n
    vs = []
    for start in range(n):
        if cs[start] is not None:
            continue
        v0 = v1 = 0
        q = [start]
        cs[start] = 1
        v1 += 1
        while q:
            u = q.pop()
            c = cs[u]
            cc = int(not c)
            for v in ns[u]:
                if cs[v] is None:
                    cs[v] = cc
                    if cc==0:
                        v0 += 1
                    else:
                        v1 += 1
                    q.append(v)
                elif cs[v]==c:
#                     print(cs)
                    return False, None
        vs.append((v0,v1))
    return True, vs
res, vs = is_bip(ns)
if not res:
    ans = -1
else:
    dp = 1
    for v0,v1 in vs:
        dp = (dp<<v0) | (dp<<v1)
#         for i in range(n,-1,-1):
#             if i-v0>=0:
#                 dp[i] |= dp[i-v0]
#             if i-v1>=0:
#                 dp[i] |= dp[i-v1]
#             print(dp)
    ans = float("inf")
    for i in range(1,n+1):
        if dp>>i&1:
            ans = min(ans, i*(i-1)//2+(n-i)*(n-i-1)//2)
print(ans)

"""
E問題
繋がっている都市同士は同じ州にあっても違う州にあってもよい→考えにくい
→「繋がっていない都市は必ず違う州にある」のほうが考えやすい
→繋がっていない都市にすべて辺を張って二部グラフが構成できるかどうかで判定できそう？
（必要条件ではあるけど十分条件であるかどうかはわからない）
→この条件だと同じ州にあるなら必ず任意の二都市間は繋がっているので十分条件も満たしてそう！
（∵繋がっていない都市に辺を張った時同じ州内に辺を持たないため）

（繋がっていない都市に辺を張った）グラフが連結⇒都市の選び方は高々1通り
連結でないなら複数の選び方が存在する
→最小となるような選び方はどのように決めればよいか？
→それぞれの連結成分ごとに、片方にai都市、もう片方にbi都市振り分けられるとすると
L = [[a1, b1], [a2, b2], ... , [ak, bk]]
とできて、(sum(A)+sum(B) == n)
s = Σ[i = 1 to k](aiかbiのどちらかを選んで足す)　としたときに
もっともsがn//2に近くなるようにsを選べばよく、これはdpでO(nk)でできる
"""
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
import numpy as np

n, m = map(int, input().split())
G = [{i for i in range(n) if i != j} for j in range(n)]
for _ in range(m):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  G[a].remove(b)
  G[b].remove(a)

seen = [-1]*n
L = []
def is_bipartite(v, color):
  seen[v] = color
  L[-1][color] += 1
  for i in G[v]:
    if seen[i] != -1:
      if seen[i] == color:
        return False
    else:
      if not is_bipartite(i, color^1):
        return False
  return True

for i in range(n):
  if seen[i] == -1:
    L.append([0, 0])
    if not is_bipartite(i, 0):
      print(-1)
      break
else:
  dp = np.zeros((len(L)+1, n+1), dtype=bool)
  dp[0, 0] = True
  for i, ab in enumerate(L):
    a, b = ab
    dp[i+1, a:] |= dp[i, :n+1-a]
    dp[i+1, b:] |= dp[i, :n+1-b]
  temp = n//2
  dp = dp[-1].tolist()
  while not dp[temp]:
    temp += 1
  r = n - temp
  print(temp*(temp-1)//2 + r*(r-1)//2)

from collections import deque

N, M = list(map(int, input().split()))
adjL = [set(range(N)) for _ in range(N)]
for v in range(N):
    adjL[v].remove(v)
for _ in range(M):
    A, B = list(map(int, input().split()))
    A, B = A-1, B-1
    adjL[A].remove(B)
    adjL[B].remove(A)

def getSizes(adjList):
    def bfs(vSt):
        colors[vSt] = 1
        nums[1] += 1
        Q = deque([vSt])
        while Q:
            vNow = Q.popleft()
            color = colors[vNow]
            for v2 in adjList[vNow]:
                if colors[v2] == color:
                    return False
                elif colors[v2] == 0:
                    colors[v2] = -color
                    nums[-color] += 1
                    Q.append(v2)
        return True

    numV = len(adjList)
    colors = [0] * numV
    anss = []
    for vSt in range(numV):
        if colors[vSt] != 0: continue
        nums = {-1: 0, 1: 0}
        if not bfs(vSt):
            return []
        anss.append((nums[-1], nums[1]))
    return anss

sizes = getSizes(adjL)

if not sizes:
    print((-1))
else:
    bitset = 1<<N
    for A, B in sizes:
        bitset = (bitset>>A) | (bitset>>B)

    minDiff = N
    iMinDiff = -1
    for i in reversed(list(range(N+1))):
        if bitset & 1:
            diff = abs(i-N/2)
            if diff < minDiff:
                minDiff = diff
                iMinDiff = i
        bitset >>= 1

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


from collections import deque


n, m = 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)
    return

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)

from typing import List


class UnionFind:
    def __init__(self, n: int) -> None:
        '木の初期化をする'
        self.p = [-1] * n
        self.rank = [1]*n
        self.size = [1] * n

    def find(self, x: int) -> int:
        'x の親を返す'
        if self.p[x] == -1:
            return x
        else:
            self.p[x] = self.find(self.p[x])
            return self.p[x]

    def unite(self, x: int, y: int) -> bool:
        'rankの低い親を高い方のの親にする'
        if not self.same(x, y):
            x = self.find(x)
            y = self.find(y)
            if self.rank[x] > self.rank[y]:
                x, y = y, x
            elif self.rank[x] == self.rank[y]:
                self.rank[y] += 1
            self.p[x] = y
            self.size[y] += self.size[x]
            return True
        else:
            return False

    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)


n, m = list(map(int, input().split()))
path = [[1]*n for _ in range(n)]
for j in range(n):
    path[j][j] = 0
for i in range(m):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    path[a][b] = 0
    path[b][a] = 0

uf = UnionFind(2*n)

for i in range(n):
    for j in range(n):
        if path[i][j] == 1:
            uf.unite(i, j+n)
            uf.unite(i+n, j)

for i in range(n):
    if uf.same(i, i+n):
        print((-1))
        return

deltas: List[int] = []

view = [1]*n

for i in range(n):
    if view[i] == 0:
        continue
    delta = 0
    for j in range(n):
        if uf.same(i, j):
            view[j] = 0
            delta += 1
        elif uf.same(i, j+n):
            view[j] = 0
            delta -= 1
    delta = abs(delta)
    deltas.append(delta)
dp = [0]*(n+10)
dp[0] = 1
for delta in deltas:
    dpnxt = [0]*(n+10)
    for i in range(n+1):
        if i+delta <= n:
            dpnxt[i+delta] += dp[i]
        dpnxt[abs(i-delta)] += dp[i]
    dp = dpnxt.copy()

for i in range(n+1):
    if dp[i]:
        print(((n+i)//2*((n+i-1)//2)//2 + (n-i)//2*((n-i-1)//2)//2))
        return


from collections import deque
N, M = map(int, input().split())
G0 = [set([i]) for i in range(N)]

A = set(range(N))

for i in range(M):
    a, b = map(int, input().split())
    G0[a-1].add(b-1)
    G0[b-1].add(a-1)

G = [A - g for g in G0]

b = 1 << (N//2)
c = [-1]*N
for i in range(N):
    if c[i] != -1:
        continue
    p = 0; s = 0
    que = deque([i])
    c[i] = 0
    while que:
        v = que.popleft()
        s += 1
        if c[v] == 0:
            p += 1
        for w in G[v]:
            if c[w] == -1:
                c[w] = c[v]^1
                que.append(w)
            elif c[w] == c[v]:
                print(-1)
                return
    b = (b >> p) | (b >> (s-p))

p = N//2 - ((b & -b).bit_length()-1)
q = N - p
print(p*(p-1)//2 + q*(q-1)//2)

import sys
N,M=map(int,input().split())
data=[[0]*(N+1) for i in range(N+1)]
for i in range(M):
    A,B=map(int,input().split())
    data[A][B]=1
    data[B][A]=1
for i in range(1,N+1):
    data[i][i]=1
lst=[-1]*(N+1)
ddd=[]
for i in range(1,N+1):
    if lst[i]!=-1:
        continue
    else:
        lst[i]=0
        que=[i]
        count=[1,0]
        while que:
            h=[]
            for u in que:
                for j in range(1,N+1):
                    if data[u][j]==1:
                        continue
                    else:
                        if lst[j]==-1:
                            lst[j]=lst[u]^1
                            count[lst[j]]+=1
                            h.append(j)
                        elif lst[j]^lst[u]==0:
                            print(-1)
                            return
            que=h
        ddd.append(count)
dp=[0]*(N+1)
dp[0]=1
for u in ddd:
    v=u[0]
    h=[0]*(N+1)
    for i in range(v,N+1):
        if dp[i-v]==1:
            h[i]=1
    v=u[1]
    for i in range(v,N+1):
        if dp[i-v]==1:
            h[i]=1
    dp=h
ans=0
for i in range(N+1):
    if dp[i]==1:
        if abs(N-2*ans)>abs(N-2*i):
            ans=i
qqq=N-ans
if qqq==0 or ans==0:
    print(N*(N-1)//2)
else:
    print(ans*(ans-1)//2+qqq*(qqq-1)//2)


def main(n,m,ab):
    g=[set(j for j in range(n) if j!=i) for i in range(n)]
    for i,(a,b) in enumerate(ab):
        a,b=a-1,b-1
        g[a].discard(b)
        g[b].discard(a)
    xy=[]
    mi=set(range(n))
    seen=[-1]*n
    while mi:
        v=mi.pop()
        todo=[[v,-1]]
        seen[v]=0
        xyi=[0,0]
        xyi[0]+=1
        while todo:
            v,p=todo.pop()
            for nv in g[v]:
                if nv==p:continue
                if seen[nv]==-1:
                    seen[nv]=(seen[v]+1)%2
                    xyi[seen[nv]]+=1
                    mi.discard(nv)
                    todo.append([nv,v])
                elif seen[nv]!=(seen[v]+1)%2:return -1
        xy.append(xyi)
    abl=[0]*(n+1)
    abl[0]=1
    for x,y in xy:
        for i in range(n,-1,-1):
            if abl[i]>0:
                abl[i]=0
                abl[i+x]=1
                abl[i+y]=1
    ans=m
    for i,x in enumerate(abl):
        if x==0:continue
        j=n-i
        ans=min(ans,(i*(i-1))//2+(j*(j-1))//2)
    return ans

n,m=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(m)]
print(main(n,m,ab))

N,M=map(int,input().split())
edge=[set([]) for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    edge[a-1].add(b-1)
    edge[b-1].add(a-1)

cedge=[[] for i in range(N)]
for i in range(N):
    for j in range(N):
        if j not in edge[i] and j!=i:
            cedge[i].append(j)

ans=[]
def is_bipartgraph():
    color=[0]*N
    used=[False]*N
    for i in range(N):
        if not used[i]:
            stack=[(i,1)]
            black=0
            white=0
            while stack:
                v,c=stack.pop()
                if not used[v]:
                    color[v]=c
                    black+=(c==1)
                    white+=(c==-1)
                    used[v]=True
                    for nv in cedge[v]:
                        if color[nv]==color[v]:
                            return False
                        elif color[nv]==0:
                            stack.append((nv,-c))
            ans.append([black,white])
    return True

if is_bipartgraph():
    dp=[[False for i in range(0,N+1)] for j in range(len(ans))]
    a,b=ans[0]
    dp[0][a],dp[0][b]=True,True
    for i in range(1,len(ans)):
        a,b=ans[i]
        for j in range(0,N+1):
            test=False
            if j>=a:
                test=test|dp[i-1][j-a]
            if j>=b:
                test=test|dp[i-1][j-b]
            dp[i][j]=test
    ans=0
    for i in range(0,N+1):
        if dp[-1][i] and abs(ans-N/2)>abs(i-N/2):
            ans=i
    ans2=N-ans
    print(ans*(ans-1)//2+ans2*(ans2-1)//2)
else:
    print(-1)

def main():
    n, m = list(map(int, input().split()))
    ab = [list(map(int, input().split())) for _ in [0]*m]

    n_hozon = n
    g = [set() for _ in [0]*n]
    [g[a-1].add(b-1) for a, b in ab]
    [g[b-1].add(a-1) for a, b in ab]
    s = set([i for i in range(n)])

    # 題意：できるだけ辺が少なくなるように2つの完全グラフに分けたい
    # まず、2つの完全グラフに分けられるのかを調べる必要がある。
    # これが不可能であれば-1を出力して即座に終了。

    # 分けられるのであれば、できるだけ街の数を均等にしたい。
    # 以下のアルゴリズムを考える。
    # まずお互い繋がっていない都市の組A,Bを選ぶ。
    # すると、Aにしか繋がっていない街、Bにしか繋がっていない街、
    # 両方に繋がっている街の3グループに分かれる。
    # このうち、最後のグループについて、
    # 最初に戻って同様の処理を行う。
    # 街がなくなるか、両方に繋がっている街のグループが完全グラフに
    # なった時点で終了。

    # 上記のアルゴリズムにより、(A,B)の列と最後に残った街の数が求められる。
    # これをもとに、動的計画法で考えられる街の振り分け方を全て洗い出す。
    # 最も均等に近く振り分けた場合について、完全グラフの辺数を計算して
    # 出力すれば問題が解ける。
    a_list, b_list = [], []
    while True:
        #print(n, m)
        # print(s)
        # print(g)
        # 完全グラフかどうか
        #print(n, m, g, s)
        if m == n*(n-1)//2:
            break
        a = [-1, 10**10]
        for i in s:
            l = len(g[i])
            if l < a[1]:
                a = [i, l]
        a = a[0]
        b = [-1, 10**10]
        for i in s-g[a]-{a}:
            l = len(g[i])
            if l < b[1]:
                b = [i, l]
        b = b[0]
        #print(a, b)
        a_set, b_set = {a}, {b}
        s.remove(a)
        s.remove(b)
        n -= 2
        remain = set()
        for i in s:
            flag_a = True
            for j in a_set:
                if j not in g[i]:
                    flag_a = False
                else:
                    g[i].remove(j)
                    g[j].remove(i)
                    m -= 1
            flag_b = True
            for j in b_set:
                if j not in g[i]:
                    flag_b = False
                else:
                    g[i].remove(j)
                    g[j].remove(i)
                    m -= 1
            #print(i, flag_a, flag_b)
            if flag_a == flag_b == False:
                print((-1))
                return
            elif flag_a == False or flag_b == False:
                # print(remain)
                q = {i}
                flag = flag_a  # True→Aに入れる
                while q:
                    #print(q, "q")
                    qq = set()
                    while q:
                        i = q.pop()
                        if flag:
                            a_set.add(i)
                        else:
                            b_set.add(i)
                        for j in remain:
                            if j not in g[i]:
                                qq.add(j)
                            else:
                                g[i].remove(j)
                                g[j].remove(i)
                                m -= 1
                        for j in q:
                            g[i].remove(j)
                            g[j].remove(i)
                            m -= 1
                    for i in qq:
                        remain.remove(i)
                    flag ^= True
                    q = qq
            else:
                remain.add(i)
            # print(g)
        for i in (a_set | b_set)-{a}-{b}:
            s.remove(i)
            n -= 1

        a_list.append(len(a_set))
        b_list.append(len(b_set))

    m = n
    n = n_hozon
    k = len(a_list)

    if k == 1:
        dp = [False]*(n+1)
        a = a_list[0]
        b = b_list[0]
        ans = 10**10
        for i in range(m+1):
            ans = min(ans, (a+i)*(a+i-1)//2+(n-a-i)*(n-a-i-1)//2)
        print(ans)
        return

    dp = [False]*(n+1)
    dp[0] = True

    for i in range(k):
        a, b = a_list[i], b_list[i]
        maxab = max(a, b)
        dp2 = [False]*(n+1)
        for j in range(n-maxab+1):
            dp2[j+a] |= dp[j]
            dp2[j+b] |= dp[j]
        dp = dp2

    dp2 = [False]*(n+1)
    for j in range(m+1):
        for i in range(n-j+1):
            dp2[i+j] |= dp[i]
    ans = 10**10

    for i in range(n+1):
        if dp2[i] is False:
            continue
        j = n-i
        ans = min(ans, i*(i-1)//2+j*(j-1)//2)
    print(ans)


main()


# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,m = list(map(int,readline().split()))

# 補グラフ
g = [[1]*n for _ in range(n)]
for i in range(n): g[i][i] = 0

for _ in range(m):
    a,b = list(map(int,readline().split()))
    g[a-1][b-1] = g[b-1][a-1] = 0

used = [-1]*n
dp = 1
ok = 1
for i in range(n):
    if used[i]==-1:
        used[i] = 0
        st = [i]
        a = b = 0
        while st:
            v = st.pop()
            c = used[v]
            if c: a += 1
            else: b += 1
            for k in range(n):
                if g[v][k] == 1:
                    if used[k] == -1:
                        used[k] = 1-c
                        st.append(k)
                    elif used[k] == c:
                        ok = 0
                        break
    
        dp = (dp<<a)|(dp<<b)
        #print(a,b)
        if not ok:
            dp = 0
            break

#print(bin(dp)[2:][::-1])

ans = -1
for i in range(n//2+1):
    if dp>>i&1:
        ans = i*(i-1)//2 + (n-i)*(n-i-1)//2

print(ans)


import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

n,m = map(int, input().split())
G = [[1]*n for i in range(n)]
for i in range(n):
    G[i][i] = 0
for i in range(m):
    a,b = map(int, input().split())
    a,b = a-1,b-1
    G[a][b] = 0
    G[b][a] = 0

from collections import deque

used = [0]*n
tmp = []

def bfs(start):
    if used[start]:
        return True
    d = {-1:0, 1:0}
    que = deque()
    que.append((start, 1))
    while que:
        cur, flag = que.popleft()
        if used[cur] == flag:
            continue
        elif used[cur]:
            return False
        used[cur] = flag
        d[flag] += 1
        for to in range(n):
            if G[cur][to] and used[to] == 0:
                que.append((to, -flag))
    tmp.append(list(d.values()))
    return True

if not all(bfs(i) for i in range(n)):
    print(-1)
else:
    s = set([0])
    target = (n+1)//2
    for l in tmp:
        t = set()
        for a in l:
            for b in s:
                if a+b <= target:
                    t.add(a+b)
        s = t
    k = max(s)
    l = n-k
    ans = k*(k-1)//2 + l*(l-1)//2
    print(ans)

def dfs(links, fixed, s):
    q = [(s, 0)]
    cnt = [0, 0]
    while q:
        v, c = q.pop()
        if fixed[v] > -1:
            if fixed[v] != c:
                return False
            continue
        fixed[v] = c
        cnt[c] += 1
        for u in links[v]:
            q.append((u, c ^ 1))
    return (max(cnt), min(cnt))


def is_bipartite(n, links):
    fixed = [-1] * n
    l, r = 0, 0
    can = []
    for i in range(n):
        if fixed[i] > -1:
            continue
        cnt = dfs(links, fixed, i)
        if cnt == False:
            return -1
        can.append(cnt)

    can.sort(reverse=True)
    for cnt in can:
        j = 0 if cnt[0] > cnt[1] else 1
        if l > r:
            j ^= 1
        l += cnt[j]
        r += cnt[j ^ 1]
    return (l * (l - 1) + r * (r - 1)) // 2


n, m = list(map(int, input().split()))
links = [set(range(n)) - {i} for i in range(n)]
for _ in range(m):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    links[a].remove(b)
    links[b].remove(a)
print((is_bipartite(n, links)))


N,M=list(map(int,input().split()))
edge=[set([]) for i in range(N)]
for i in range(M):
    a,b=list(map(int,input().split()))
    edge[a-1].add(b-1)
    edge[b-1].add(a-1)

cedge=[[] for i in range(N)]
for i in range(N):
    for j in range(N):
        if j not in edge[i] and j!=i:
            cedge[i].append(j)

ans=[]
def is_bipartgraph():
    color=[0]*N
    used=[False]*N
    for i in range(N):
        if not used[i]:
            stack=[(i,1)]
            black=0
            white=0
            while stack:
                v,c=stack.pop()
                color[v]=c
                black+=(not used[v])*(c==1)
                white+=(not used[v])*(c==-1)
                used[v]=True
                for nv in cedge[v]:
                    if color[nv]==color[v]:
                        return False
                    elif color[nv]==0:
                        stack.append((nv,-c))
            ans.append([black,white])
    return True

if is_bipartgraph():
    dp=[[False for i in range(0,N+1)] for j in range(len(ans))]
    a,b=ans[0]
    dp[0][a],dp[0][b]=True,True
    for i in range(1,len(ans)):
        a,b=ans[i]
        for j in range(0,N+1):
            test=False
            if j>=a:
                test=test|dp[i-1][j-a]
            if j>=b:
                test=test|dp[i-1][j-b]
            dp[i][j]=test
    ans=0
    for i in range(0,N+1):
        if dp[-1][i] and abs(ans-N/2)>abs(i-N/2):
            ans=i
    ans2=N-ans
    print((ans*(ans-1)//2+ans2*(ans2-1)//2))
else:
    print((-1))


import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class UnionFind:
    def __init__(self, n):
        self.state = [-1] * n
        self.size_table = [1] * n
        # cntはグループ数
        # self.cnt = n

    def root(self, u):
        v = self.state[u]
        if v < 0: return u
        self.state[u] = res = self.root(v)
        return res

    def merge(self, u, v):
        ru = self.root(u)
        rv = self.root(v)
        if ru == rv: return
        du = self.state[ru]
        dv = self.state[rv]
        if du > dv: ru, rv = rv, ru
        if du == dv: self.state[ru] -= 1
        self.state[rv] = ru
        # self.cnt -= 1
        self.size_table[ru] += self.size_table[rv]
        return

    # グループの要素数
    def size(self, u):
        return self.size_table[self.root(u)]

def ng():
    for u in range(n):
        for v in range(n):
            if v == u: continue
            if to[u][v]: continue
            if uf.root(u)==uf.root(v):return True
    return False

n,m=MI()
to=[[False]*n for _ in range(n)]
for _ in range(m):
    u,v=MI1()
    to[u][v]=to[v][u]=True

uf=UnionFind(n)
uncon=[-1]*n
for u in range(n):
    pv=-1
    for v in range(n):
        if v==u:continue
        if to[u][v]:continue
        if pv==-1:pv=v
        else:uf.merge(pv,v)
    uncon[u]=pv

#print(uf.state)
#print(uf.size_table)
#print(uncon)

if ng():
    print(-1)
    return

fin=[False]*n
free=0
ss=[]
for u in range(n):
    if uncon[u]==-1:
        free+=1
        continue
    r0=uf.root(u)
    if fin[r0]:continue
    r1=uf.root(uncon[u])
    fin[r0]=fin[r1]=True
    ss.append(abs(uf.size_table[r0]-uf.size_table[r1]))
cur=1<<1000
for s in ss:cur=cur<<s|cur>>s
cur>>=1000
d=(cur&-cur).bit_length()-1
d=max(0,d-free)
s0=(n-d)//2
s1=n-s0
print(s0*(s0-1)//2+s1*(s1-1)//2)


n,m,*A=map(int,open(0).read().split())
g=[[1]*n for _ in [0]*n]
for a,b in zip(A[::2],A[1::2]):
    g[a-1][b-1]=g[b-1][a-1]=0
U=[1]*n
D=1
def dfs(v):
    nonlocal D
    R[U[v]]+=1
    for k in range(n):
        if g[v][k]*(k-v):
            D *= U[k]!=U[v]
            if U[k]>0:
                U[k]=~U[v]
                dfs(k)
for i in range(n):
    if U[i]>0:
        R=[0,0];U[i]=0
        dfs(i);
        D=(D<<R[0])|(D<<R[1])
a=-1
for i in range(n//2+1):
    if D>>i&1:a=(i*(i-1)+(n-i)*(n-i-1))//2
print(a)

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

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
e = [set([x for x in range(1, N + 1) if i != x]) for i in range(N + 1)]
for _ in range(M):
  u, v = map(int, input().split())
  e[u].discard(v)
  e[v].discard(u)

cl = [0] * (N + 1)
dp = [0] * (N + 1)
dp[0] = 1
for x in range(1, N + 1):
  if cl[x]: continue
  s = [x]
  qs = []
  cl[x] = 1
  while len(s):
    p = s.pop()
    qs.append(p)
    for q in e[p]:
      if cl[q]:
        if cl[q] % 2 == cl[p] % 2:
          print(-1)
          return
        continue
      cl[q] = cl[p] % 2 + 1
      s.append(q)
  predp = dp[: ]
  for i in range(N, -1, -1):
    if dp[i] == 0: continue
    u = 0
    v = 0
    for q in qs:
      u += cl[q] % 2
      v += cl[q] % 2 == 0
    dp[i] -= predp[i]
    dp[i + u] += 1
    dp[i + v] += 1
  #print(dp)
res = N * (N - 1) // 2
for i in range(1, N + 1):
  if dp[i] == 0: continue
  u = i * (i - 1) // 2
  v = (N - i) * (N - i - 1) // 2
  res = min(res, u + v)
print(res)

import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return list(map(int, input().split()))
def LI(): return list(map(int, input().split()))
mod=10**9+7


"""
A,Bの2つのグループに分ける．各グループ内の全ての点へ最短距離が1となる.
逆に，最短距離が1出なければ異なるグループに配属される.
全点間距離はわーシャルフロイトで求める．
これは2-SATかな，a,bの距離が1ではない→a,bは違うグループに入る→(a∨b)∧(not_a ∨ not_b)
これを∧でつなげていけば良い．

どちらに入っても良い点(全ての点との距離が1)，というのがある，これはA,Bの個数のバランスを見て，少ない方に入れていく．
これは2SATだと01のどちらでも良い値になってしまうので計算から予め避けておく.


これ以外にも気をつけるパターンがあって，
aとb,aとc
dとe,dとf
が同じ場所にならないという条件のとき，
aef-bcd
のおように分けたいが
ad-bcef
のようにも分けられてしまう．

ufとかで上手い感じに管理できるかな?
"""

from collections import defaultdict
class UnionFind:
    def __init__(self, N: int):
        """
        N:要素数
        root:各要素の親要素の番号を格納するリスト.
             ただし, root[x] < 0 ならその頂点が根で-root[x]が木の要素数.
        rank:ランク
        """
        self.N = N
        self.root = [-1] * N
        self.rank = [0] * N

    def __repr__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

    def find(self, x: int):
        """頂点xの根を見つける"""
        if self.root[x] < 0:
            return x
        else:
            while self.root[x] >= 0:
                x = self.root[x]
            return x

    def union(self, x: int, y: int):
        """x,yが属する木をunion"""
        # 根を比較する
        # すでに同じ木に属していた場合は何もしない.
        # 違う木に属していた場合はrankを見てくっつける方を決める.
        # rankが同じ時はrankを1増やす
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        elif self.rank[x] > self.rank[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def same(self, x: int, y: int):
        """xとyが同じグループに属するかどうか"""
        return self.find(x) == self.find(y)

    def count(self, x):
        """頂点xが属する木のサイズを返す"""
        return - self.root[self.find(x)]

    def members(self, x):
        """xが属する木の要素を列挙"""
        _root = self.find(x)
        return [i for i in range(self.N) if self.find == _root]

    def roots(self):
        """森の根を列挙"""
        return [i for i, x in enumerate(self.root) if x < 0]

    def group_count(self):
        """連結成分の数"""
        return len(self.roots())

    def all_group_members(self):
        """{ルート要素: [そのグループに含まれる要素のリスト], ...}のデフォルトディクトを返す"""
        dd = defaultdict(list)
        for i in range(N):
            root=self.find(i)
            dd[root].append(i)
        return dd


class Scc_graph:

    def __init__(self, N):
        self.N = N
        self.edges = []

    def csr(self):
        start = [0]*(self.N+1)
        elist = [0]*len(self.edges)
        for v, w in self.edges:
            start[v+1] += 1
        for i in range(1, self.N+1):
            start[i] += start[i-1]
        counter = start.copy()
        for v, w in self.edges:
            elist[counter[v]] = w
            counter[v] += 1
        self.start = start
        self.elist = elist

    def add_edge(self, v, w):
        self.edges.append((v, w))

    def scc_ids(self):
        self.csr()
        N = self.N
        now_ord = group_num = 0
        visited = []
        low = [0]*N
        order = [-1]*N
        ids = [0]*N
        parent = [-1]*N
        stack = []
        for i in range(N):
            if order[i] == -1:
                stack.append(~i)
                stack.append(i)
                while stack:
                    v = stack.pop()
                    if v >= 0:
                        if order[v] == -1:
                            low[v] = order[v] = now_ord
                            now_ord += 1
                            visited.append(v)
                            for i in range(self.start[v], self.start[v+1]):
                                to = self.elist[i]
                                if order[to] == -1:
                                    stack.append(~to)
                                    stack.append(to)
                                    parent[to] = v
                                else:
                                    low[v] = min(low[v], order[to])
                    else:
                        v = ~v
                        if low[v] == order[v]:
                            while True:
                                u = visited.pop()
                                order[u] = N
                                ids[u] = group_num
                                if u == v:
                                    break
                            group_num += 1
                        if parent[v] != -1:
                            low[parent[v]] = min(low[parent[v]], low[v])
        for i, x in enumerate(ids):
            ids[i] = group_num-1-x

        return group_num, ids

    def scc(self):
        group_num, ids = self.scc_ids()
        groups = [[] for _ in range(group_num)]
        for i, x in enumerate(ids):
            groups[x].append(i)
        return groups


class Two_sat:
    def __init__(self, N):
        self.N = N
        self.answer = []
        self.scc = Scc_graph(2*N)

    """
    A[i]=a,A[j]=b
    (a∨b)を追加したいとき，(f,g)=(1,1)
    否定したものを入れたい時fやgを0に変更する
    """
    def add_clause(self, i, f, j, g):
        # assert 0 <= i < self.N
        # assert 0 <= j < self.N
        self.scc.add_edge(2*i+(f == 0), 2*j+(g == 1))
        self.scc.add_edge(2*j+(g == 0), 2*i+(f == 1))

    def satisfiable(self):
        _, ids = self.scc.scc_ids()
        self.answer.clear()
        for i in range(self.N):
            if ids[2 * i] == ids[2 * i + 1]:
                self.answer.clear()
                return False
            self.answer.append(ids[2*i] < ids[2*i+1])
        return True

# def warshall_floyd(d):
#     #d[i][j]: iからjへの最短距離
#     N=len(d)
#     for k in range(N):
#         for i in range(N):
#             for j in range(N):
#                 d[i][j] = min(d[i][j],d[i][k] + d[k][j])
#     return d
#################################################


N,M=MI()
inf = N+5
d=[[inf]*N for _ in range(N)]
for i in range(N):
    d[i][i]=0

for _ in range(M):
    a,b=MI()
    a-=1
    b-=1
    d[a][b]=1
    d[b][a]=1

# 距離が1か否かだけわかれば良いので，これいらない
# d=warshall_floyd(d)

# for i in range(N):
#     print(d[i])

def calc(x):
    return (x*(x-1))//2

uf=UnionFind(N)
for i in range(N):
    for j in range(i+1,N):
        if d[i][j]>1:
            uf.union(i,j)
            # print(i,j)

roots=uf.roots()
Nr=len(roots)
G=[[]for _ in range(Nr)]

from collections import defaultdict
dd = defaultdict(int)
cnt=0
for v in roots:
    dd[v]=cnt
    cnt+=1
    
# print(roots,Nr)

for i in range(N):
    r=uf.find(i)
    rnum=dd[r]
    
    # print(i,r,rnum)
    G[rnum].append(i)



allOK=0#A,Bどちらのグループに入れても問題ないもの

"""
とりあえず，連結成分毎に2SATする．
a個,b個(a<=b)
のグループに分けられるとして，これをA,Bのグループにどうふり分けるか.
= (a,b)2つの数字の組みが大量にあって，それらを振り分けて差が小さくなるように頑張れば良いはず

両方にaを加算して，差分(b-a)を記憶しておき，あとでどっちに振り分けるか考える
"""
D=[]#A,Bグループの差
S1=0
S2=0



for g in G:
    Ng=len(g)
    if Ng==1:
        allOK+=1
        continue
    
    g.sort()
    ts=Two_sat(Ng)
    
    # print(g)
    
    for i in range(Ng):
        for j in range(i+1,Ng):
            a=g[i]
            b=g[j]
            if d[a][b]!=1:
                ts.add_clause(i,0,j,0)
                ts.add_clause(i,1,j,1)
            
    if not ts.satisfiable():
        print((-1))
        return
        
    a=sum(ts.answer)
    b=Ng-a
    
    S1+=min(a,b)
    S2+=min(a,b)
    
    if a!=b:
        D.append(abs(a-b))
    
    
# あとはDをどう割り振るか．
# これは，D内の数字を+/-のどちらか符号を選んで足していき，その結果を0に近づけたいという問題に帰着．数字が小さいのでdpでできる.
Nd=len(D)

geta=1000
dp=[[0]*(geta*2+1) for _ in range(Nd+1)]
dp[0][geta]=1
for i,num in enumerate(D):
    for j in range(geta*2+1):
        if dp[i][j]:
            dp[i+1][j-num]=1
            dp[i+1][j+num]=1
            
diff=geta
for j in range(geta+1):
    if dp[-1][j]:
        diff=min(diff,
                 abs(j-geta))
        
# print(D)
# print(diff)

Sd=sum(D)
s11=(Sd-diff)//2
s12=Sd-s11


# S1<=S2
S1+=s11
S2+=s12

ds=S2-S1
if ds>allOK:
    ans=calc(S2)+calc(S1+allOK)
else:
    aa=N//2
    bb=N-aa
    ans=calc(aa)+calc(bb)
    
    
# 
print(ans)
    









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

I = [[0 for _ in range(N)] for _ in range(N)]
for _ in range(M):
  a, b = list(map(int,input().split()))
  a -= 1
  b -= 1
  I[a][b] = 1
  I[b][a] = 1
for a in range(N):
  I[a][a] = 1
# 0を辺とするグラフが二部グラフか否か判定
#print(*I, sep="\n")  
  
# 各連結成分の頂点数
R = []
B = []

vis = set()

def dfs(s, c):# 0を辺とするグラフが二部グラフか否かを、始点s, 初期色cのBFSで判定
  adj = I[s]
  tmp = True
  r_ct = 0
  b_ct = 0
  clr[s] = c
  for p in range(N):
    if adj[p] == 1: # 隣接してない
      continue
    if p in vis: 
      if clr[p] != 1-c:
        #print(s, p)
        return False
      continue
    else:
      vis.add(p)
      if not dfs(p, 1-c):
        return False
  return True
  
  
  
# 二部グラフかいなかと、各連結成分の色ごとの数を判定
vis = set()
ans = 0
used_edge = 0
for s in range(N):
  if s in vis: continue
  R.append(0)
  B.append(0)
  clr = {}
  vis.add(s)
  if not dfs(s, 0):
    print((-1)); return;
  #print(clr)
  for p in clr:
    if clr[p] == 0:
      R[-1] += 1
    else:
      B[-1] += 1
  for p in clr:
    for q in clr:
      if p != q and I[p][q] == 1: 
        used_edge += 1
        if clr[p] == clr[q]:
          ans += 1
  #print(ans)
        
#print(R)
#print(B)
      
# 最大値 : a_i*b_jの非対角和の半分で、a_iの和がN/2に最も近い場合
DP = 1
for i in range(len(R)):
  DP = (DP << R[i]) | (DP << B[i])

i = 0
ex = []
while DP > 0:
  if DP % 2 == 1:
    ex.append(i)
  i += 1
  DP >>= 1
#print(ex)  
ex.sort(key = lambda x: abs(2*x-N))
#print(ex[0])
tmp = ex[0] * (N - ex[0])
for i in range(len(R)):
  tmp -= R[i]*B[i]
#print(used_edge)
#print(tmp)
#print(2*M - used_edge)
ans //= 2
ans += (2*M - used_edge)//2 - tmp
  
print(ans)
  
  

  
  


import sys
input = sys.stdin.readline

N, M = map(int, input().split())
G = [set() for _ in range(N)]
for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    G[A].add(B)
    G[B].add(A)

G_comp = [[] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i != j and j not in G[i]:
            G_comp[i].append(j)

color = [-1] * N
A = []
dp = set([0])
for i in range(N):
    if color[i] != -1:
        continue
    cnt = [1, 0]
    color[i] = 0
    stack = [i]
    while stack:
        v = stack.pop()
        for u in G_comp[v]:
            if color[u] == -1:
                color[u] = 1 - color[v]
                stack.append(u)
                cnt[color[u]] += 1
            if color[u] == color[v]:
                print(-1)
                return
    ndp = set()
    for a in dp:
        ndp.add(a + cnt[0])
        ndp.add(a + cnt[1])
    dp = ndp
ans = float('inf')
for a in dp:
    ans = min(ans, a * (a - 1) // 2 + (N - a) * (N - a - 1) // 2)
print(ans)