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.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'import sys\ninput = sys.stdin.readline\n\ndef I(): return int(input())\ndef MI(): return list(map(int, input().split()))\ndef LI(): return list(map(int, input().split()))\nmod=10**9+7\n\n\n"""\nA,Bの2つのグループに分ける．各グループ内の全ての点へ最短距離が1となる.\n逆に，最短距離が1出なければ異なるグループに配属される.\n全点間距離はわーシャルフロイトで求める．\nこれは2-SATかな，a,bの距離が1ではない→a,bは違うグループに入る→(a∨b)∧(not_a ∨ not_b)\nこれを∧でつなげていけば良い．\n\nどちらに入っても良い点(全ての点との距離が1)，というのがある，これはA,Bの個数のバランスを見て，少ない方に入れていく．\nこれは2SATだと01のどちらでも良い値になってしまうので計算から予め避けておく.\n\n\nこれ以外にも気をつけるパターンがあって，\naとb,aとc\ndとe,dとf\nが同じ場所にならないという条件のとき，\naef-bcd\nのおように分けたいが\nad-bcef\nのようにも分けられてしまう．\n\nufとかで上手い感じに管理できるかな?\n"""\n\nfrom collections import defaultdict\nclass UnionFind:\n    def __init__(self, N: int):\n        """\n        N:要素数\n        root:各要素の親要素の番号を格納するリスト.\n             ただし, root[x] < 0 ならその頂点が根で-root[x]が木の要素数.\n        rank:ランク\n        """\n        self.N = N\n        self.root = [-1] * N\n        self.rank = [0] * N\n\n    def __repr__(self):\n        return \'\\n\'.join(\'{}: {}\'.format(r, self.members(r)) for r in self.roots())\n\n    def find(self, x: int):\n        """頂点xの根を見つける"""\n        if self.root[x] < 0:\n            return x\n        else:\n            while self.root[x] >= 0:\n                x = self.root[x]\n            return x\n\n    def union(self, x: int, y: int):\n        """x,yが属する木をunion"""\n        # 根を比較する\n        # すでに同じ木に属していた場合は何もしない.\n        # 違う木に属していた場合はrankを見てくっつける方を決める.\n        # rankが同じ時はrankを1増やす\n        x = self.find(x)\n        y = self.find(y)\n        if x == y:\n            return\n        elif self.rank[x] > self.rank[y]:\n            self.root[x] += self.root[y]\n            self.root[y] = x\n        else:\n            self.root[y] += self.root[x]\n            self.root[x] = y\n            if self.rank[x] == self.rank[y]:\n                self.rank[y] += 1\n\n    def same(self, x: int, y: int):\n        """xとyが同じグループに属するかどうか"""\n        return self.find(x) == self.find(y)\n\n    def count(self, x):\n        """頂点xが属する木のサイズを返す"""\n        return - self.root[self.find(x)]\n\n    def members(self, x):\n        """xが属する木の要素を列挙"""\n        _root = self.find(x)\n        return [i for i in range(self.N) if self.find == _root]\n\n    def roots(self):\n        """森の根を列挙"""\n        return [i for i, x in enumerate(self.root) if x < 0]\n\n    def group_count(self):\n        """連結成分の数"""\n        return len(self.roots())\n\n    def all_group_members(self):\n        """{ルート要素: [そのグループに含まれる要素のリスト], ...}のデフォルトディクトを返す"""\n        dd = defaultdict(list)\n        for i in range(N):\n            root=self.find(i)\n            dd[root].append(i)\n        return dd\n\n\nclass Scc_graph:\n\n    def __init__(self, N):\n        self.N = N\n        self.edges = []\n\n    def csr(self):\n        start = [0]*(self.N+1)\n        elist = [0]*len(self.edges)\n        for v, w in self.edges:\n            start[v+1] += 1\n        for i in range(1, self.N+1):\n            start[i] += start[i-1]\n        counter = start.copy()\n        for v, w in self.edges:\n            elist[counter[v]] = w\n            counter[v] += 1\n        self.start = start\n        self.elist = elist\n\n    def add_edge(self, v, w):\n        self.edges.append((v, w))\n\n    def scc_ids(self):\n        self.csr()\n        N = self.N\n        now_ord = group_num = 0\n        visited = []\n        low = [0]*N\n        order = [-1]*N\n        ids = [0]*N\n        parent = [-1]*N\n        stack = []\n        for i in range(N):\n            if order[i] == -1:\n                stack.append(~i)\n                stack.append(i)\n                while stack:\n                    v = stack.pop()\n                    if v >= 0:\n                        if order[v] == -1:\n                            low[v] = order[v] = now_ord\n                            now_ord += 1\n                            visited.append(v)\n                            for i in range(self.start[v], self.start[v+1]):\n                                to = self.elist[i]\n                                if order[to] == -1:\n                                    stack.append(~to)\n                                    stack.append(to)\n                                    parent[to] = v\n                                else:\n                                    low[v] = min(low[v], order[to])\n                    else:\n                        v = ~v\n                        if low[v] == order[v]:\n                            while True:\n                                u = visited.pop()\n                                order[u] = N\n                                ids[u] = group_num\n                                if u == v:\n                                    break\n                            group_num += 1\n                        if parent[v] != -1:\n                            low[parent[v]] = min(low[parent[v]], low[v])\n        for i, x in enumerate(ids):\n            ids[i] = group_num-1-x\n\n        return group_num, ids\n\n    def scc(self):\n        group_num, ids = self.scc_ids()\n        groups = [[] for _ in range(group_num)]\n        for i, x in enumerate(ids):\n            groups[x].append(i)\n        return groups\n\n\nclass Two_sat:\n    def __init__(self, N):\n        self.N = N\n        self.answer = []\n        self.scc = Scc_graph(2*N)\n\n    """\n    A[i]=a,A[j]=b\n    (a∨b)を追加したいとき，(f,g)=(1,1)\n    否定したものを入れたい時fやgを0に変更する\n    """\n    def add_clause(self, i, f, j, g):\n        # assert 0 <= i < self.N\n        # assert 0 <= j < self.N\n        self.scc.add_edge(2*i+(f == 0), 2*j+(g == 1))\n        self.scc.add_edge(2*j+(g == 0), 2*i+(f == 1))\n\n    def satisfiable(self):\n        _, ids = self.scc.scc_ids()\n        self.answer.clear()\n        for i in range(self.N):\n            if ids[2 * i] == ids[2 * i + 1]:\n                self.answer.clear()\n                return False\n            self.answer.append(ids[2*i] < ids[2*i+1])\n        return True\n\n# def warshall_floyd(d):\n#     #d[i][j]: iからjへの最短距離\n#     N=len(d)\n#     for k in range(N):\n#         for i in range(N):\n#             for j in range(N):\n#                 d[i][j] = min(d[i][j],d[i][k] + d[k][j])\n#     return d\n#################################################\n\n\nN,M=MI()\ninf = N+5\nd=[[inf]*N for _ in range(N)]\nfor i in range(N):\n    d[i][i]=0\n\nfor _ in range(M):\n    a,b=MI()\n    a-=1\n    b-=1\n    d[a][b]=1\n    d[b][a]=1\n\n# 距離が1か否かだけわかれば良いので，これいらない\n# d=warshall_floyd(d)\n\n# for i in range(N):\n#     print(d[i])\n\ndef calc(x):\n    return (x*(x-1))//2\n\nuf=UnionFind(N)\nfor i in range(N):\n    for j in range(i+1,N):\n        if d[i][j]>1:\n            uf.union(i,j)\n            # print(i,j)\n\nroots=uf.roots()\nNr=len(roots)\nG=[[]for _ in range(Nr)]\n\nfrom collections import defaultdict\ndd = defaultdict(int)\ncnt=0\nfor v in roots:\n    dd[v]=cnt\n    cnt+=1\n    \n# print(roots,Nr)\n\nfor i in range(N):\n    r=uf.find(i)\n    rnum=dd[r]\n    \n    # print(i,r,rnum)\n    G[rnum].append(i)\n\n\n\nallOK=0#A,Bどちらのグループに入れても問題ないもの\n\n"""\nとりあえず，連結成分毎に2SATする．\na個,b個(a<=b)\nのグループに分けられるとして，これをA,Bのグループにどうふり分けるか.\n= (a,b)2つの数字の組みが大量にあって，それらを振り分けて差が小さくなるように頑張れば良いはず\n\n両方にaを加算して，差分(b-a)を記憶しておき，あとでどっちに振り分けるか考える\n"""\nD=[]#A,Bグループの差\nS1=0\nS2=0\n\n\n\nfor g in G:\n    Ng=len(g)\n    if Ng==1:\n        allOK+=1\n        continue\n    \n    g.sort()\n    ts=Two_sat(Ng)\n    \n    # print(g)\n    \n    for i in range(Ng):\n        for j in range(i+1,Ng):\n            a=g[i]\n            b=g[j]\n            if d[a][b]!=1:\n                ts.add_clause(i,0,j,0)\n                ts.add_clause(i,1,j,1)\n            \n    if not ts.satisfiable():\n        print((-1))\n        return\n        \n    a=sum(ts.answer)\n    b=Ng-a\n    \n    S1+=min(a,b)\n    S2+=min(a,b)\n    \n    if a!=b:\n        D.append(abs(a-b))\n    \n    \n# あとはDをどう割り振るか．\n# これは，D内の数字を+/-のどちらか符号を選んで足していき，その結果を0に近づけたいという問題に帰着．数字が小さいのでdpでできる.\nNd=len(D)\n\ngeta=1000\ndp=[[0]*(geta*2+1) for _ in range(Nd+1)]\ndp[0][geta]=1\nfor i,num in enumerate(D):\n    for j in range(geta*2+1):\n        if dp[i][j]:\n            dp[i+1][j-num]=1\n            dp[i+1][j+num]=1\n            \ndiff=geta\nfor j in range(geta+1):\n    if dp[-1][j]:\n        diff=min(diff,\n                 abs(j-geta))\n        \n# print(D)\n# print(diff)\n\nSd=sum(D)\ns11=(Sd-diff)//2\ns12=Sd-s11\n\n\n# S1<=S2\nS1+=s11\nS2+=s12\n\nds=S2-S1\nif ds>allOK:\n    ans=calc(S2)+calc(S1+allOK)\nelse:\n    aa=N//2\n    bb=N-aa\n    ans=calc(aa)+calc(bb)\n    \n    \n# \nprint(ans)\n    \n\n\n\n\n\n\n\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: