Problem:
 Score : 700 points    Problem Statement 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 1 5 5
1 2
1 3
3 4
3 5
4 5      Sample Output 1 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 .       Sample Input 2 5 1
1 2      Sample Output 2 -1  In this sample, the condition cannot be satisfied regardless of which cities belong to each state.       Sample Input 3 4 3
1 2
1 3
2 3      Sample Output 3 3       Sample Input 4 10 39
7 2
7 1
5 6
5 8
9 10
2 8
8 7
3 10
10 1
8 10
2 3
7 4
3 9
4 10
3 4
6 1
6 7
9 5
9 7
6 9
9 4
4 6
7 5
8 3
2 5
9 2
10 7
8 6
8 9
7 3
5 3
4 5
6 3
2 10
5 10
4 2
6 2
8 4
10 6      Sample Output 4 21

Solution (Python):
from collections import deque

N, M = 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 = 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(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)

Solution (Python):
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)

Solution (Python):
import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7






N, M = list(map(int, sys.stdin.buffer.readline().split()))
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]

edges = set()
for a, b in AB:
    a -= 1
    b -= 1
    edges.add((a, b))
    edges.add((b, a))

graph = [[] for _ in range(N)]
for a, b in itertools.combinations(range(N), r=2):
    if (a, b) not in edges:
        graph[a].append(b)
        graph[b].append(a)

ok = True
pairs = []
seen = [False] * N
for v in range(N):
    if seen[v]:
        continue
    evens = {v}
    odds = set()
    stack = [(v, True)]
    while stack:
        v, v_is_even = stack.pop()
        next_set = odds if v_is_even else evens
        for u in graph[v]:
            if u in next_set:
                continue
            next_set.add(u)
            stack.append((u, not v_is_even))
    if len(evens) + len(odds) != len(evens | odds):
        ok = False
        break
    pairs.append((len(evens), len(odds)))
    for v in evens:
        seen[v] = True
    for v in odds:
        seen[v] = True


if not ok:
    print(-1)
    exit()


can_make = [[False] * (N + 1) for _ in range(len(pairs) + 1)]
can_make[0][0] = True
for pi, (a, b) in enumerate(pairs):
    for i in range(N + 1):
        if can_make[pi][i]:
            can_make[pi + 1][i + a] |= True
            can_make[pi + 1][i + b] |= True

ans = INF
for n in range(len(can_make[-1])):
    if can_make[-1][n]:
        m = N - n
        a = m * (m - 1) // 2
        b = n * (n - 1) // 2
        ans = min(ans, a + b)
print(ans)

Solution (Python):
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)

if __name__ == "__main__":
    main()

Solution (Python):
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)
                            sys.exit()
            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)

Solution (Python):
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)
    exit()

dp = [[False]*(n+1) for _ in range(len(num) + 1)]
dp[0][0] = True

for i in range(len(num)):
    a, b = num[i]
    for j in range(n+1):
        if j-a >= 0:
            dp[i+1][j] = dp[i][j-a] or dp[i+1][j]
        if j-b >= 0:
            dp[i+1][j] = dp[i][j-b] or dp[i+1][j]

ans = 10**20
for i, boolian in enumerate(dp[len(num)]):
    if boolian:
        tmp_ans = i * (i-1) // 2 + (n-i) * (n-i-1) // 2 
        ans = min(tmp_ans, ans)
print(ans)

Solution (Python):
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)

Solution (Python):
def main():
    N, M = map(int, input().split())
    E_mat = [[0]*(N+1) for _ in range(N+1)]
    for _ in range(M):
        a, b = 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()

Solution (Python):
N, M = 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 = 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)

Solution (Python):
from collections import defaultdict, deque
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
edges = [set(range(N)) for i in range(N)]
for i in range(N):
    edges[i].remove(i)
for _ in range(M):
    a, b = map(int, input().split())
    edges[a-1].remove(b-1)
    edges[b-1].remove(a-1)
size = defaultdict(lambda: [0, 0])
color = [-1]*N
def set_color(root):
    
    que = deque([root])
    color[root] = 0
    size[root][0]+=1
    while que:
        v = que.pop()
        for nv in edges[v]:
            if color[nv]<0:
                c = 1- color[v]
                color[nv] = c
                size[root][c]+=1
                que.append(nv)
            elif color[nv] == color[v]:
                print(-1)
                sys.exit()
for i in range(N):
    if color[i]<0:
        set_color(i)
S = set([0])
for a, b in size.values():
    S = set(s+b for s in S)|set(s+a for s in S)
ans = min(x*(x-1)//2+(N-x)*(N-x-1)//2 for x in S)            
print(ans)

Solution (Python):
from collections import defaultdict, deque
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
edges = [list(range(N)) for i in range(N)]
for i in range(N):
    edges[i].remove(i)
for _ in range(M):
    a, b = map(int, input().split())
    edges[a-1].remove(b-1)
    edges[b-1].remove(a-1)
size = defaultdict(lambda: [0, 0])
color = [-1]*N
def set_color(root):
    
    que = deque([root])
    color[root] = 0
    size[root][0]+=1
    while que:
        v = que.pop()
        for nv in edges[v]:
            if color[nv]<0:
                c = 1- color[v]
                color[nv] = c
                size[root][c]+=1
                que.append(nv)
            elif color[nv] == color[v]:
                print(-1)
                sys.exit()
for i in range(N):
    if color[i]<0:
        set_color(i)
S = set([0])
for a, b in size.values():
    S = set(s+b for s in S)|set(s+a for s in S)
ans = min(x*(x-1)//2+(N-x)*(N-x-1)//2 for x in S)            
print(ans)

Solution (Python):
from collections import deque

N, M = map(int, input().split())
adj = [[1 for _ in range(N + 1)] for _ in range(N + 1)]
for _ in range(M):
    a, b = 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)
                        exit()
        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)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import defaultdict


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


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

color = [None] * (1+N)
size = defaultdict(lambda: [0,0])

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

for x in rng:
    if color[x] is None:
        set_color(x,x,0)




se = {0}
for x,y in size.values():
    se = set(s + x for s in se) | set(s + y for s in se)

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

Solution (Python):
import sys
input = sys.stdin.readline
from collections import defaultdict


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


graph = [set(x for x in range(N) if x != y) for y in range(N)]
for _ in range(M):
    a,b = map(lambda x: int(x) - 1,input().split())
    graph[a].remove(b)
    graph[b].remove(a)

color = [None] * N
size = defaultdict(lambda: [0,0])

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

for x in range(N):
    if color[x] is None:
        set_color(x,x,0)




se = {0}
for x,y in size.values():
    se = set(s + x for s in se) | set(s + y for s in se)

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

Solution (Python):
import sys
input = sys.stdin.readline
from collections import defaultdict


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


graph = [set(x for x in range(N) if x != y) for y in range(N)]
for _ in range(M):
    a,b = map(lambda x: int(x) - 1,input().split())
    graph[a].remove(b)
    graph[b].remove(a)

color = [None] * N
size = defaultdict(lambda: [0,0])

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

for x in range(N):
    if color[x] is not None:
        continue
    set_color(x,x,0)

size




se = {0}
for x,y in size.values():
    se = set(s + x for s in se) | set(s + y for s in se)

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

Solution (Python):
import sys
def input():
	return sys.stdin.readline()[:-1]

n, m = map(int, input().split())
def calc(x, y):
	return x * (x-1) // 2 + y * (y-1) // 2

adj = [[True for _ in range(n)] for _ in range(n)]
for _ in range(m):
	a, b = map(int, input().split())
	adj[a-1][b-1] = False
	adj[b-1][a-1] = False
for i in range(n):
	adj[i][i] = False

parity = [-1 for _ in range(n)]
nibus = []

def dfs(x):
	global bip
	bip[parity[x]] += 1
	for i in range(n):
		if adj[x][i] == True:
			if parity[i] < 0:
				parity[i] = 1^parity[x]
				dfs(i)
			elif parity[i] == parity[x]:
				print(-1)
				sys.exit()
	return bip

for i in range(n):
	if parity[i] < 0:
		parity[i] = 0
		bip = [0, 0]
		nibus.append(dfs(i))

cand = {0}
for p, q in nibus:
	p_set, q_set = set(), set()
	for s in cand:
		p_set.add(s+p)
		q_set.add(s+q)
	cand = p_set|q_set

ans = n**2
for c in cand:
	ans = min(ans, calc(c, n-c))
print(ans)

Solution (Python):
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:
      global 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)
  exit()
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)

Solution (Python):
import sys
n, m = 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 = 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)
            sys.exit()

        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)

Solution (Python):




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)

Solution (Python):
import queue
N,M=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=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)
                    exit()
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)

Solution (Python):
import queue
N,M=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=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)
                    exit()
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)

Solution (Python):
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect
 
def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

N, M = reads()
orig_edges = set()
for _ in range(M):
  A, B = reads()
  A, B = A-1, B-1
  orig_edges.add((A, B))
  orig_edges.add((B, A))

edges = [[] for _ in range(N)]
for A, B in combinations(range(N), 2):
  if (A, B) not in orig_edges:
    edges[A].append(B)
    edges[B].append(A)

remain = set(range(N))
color = [-1] * N

def walk(u, c, ctr, remain):
  if u in remain:
    remain.remove(u)
  if color[u] >= 0:
    if color[u] != c:
      print(-1); exit()
    return ctr

  color[u] = c; ctr[c] += 1
  for v in edges[u]:
    walk(v, 1-c, ctr, remain)
  return ctr

ps = []
while len(remain) > 0:
  s = remain.pop()
  p = walk(s, 0, [0, 0], remain)
  ps.append(p)

dp = set([0])
for a, b in ps:
  d = b - a
  dp = {x - d for x in dp} | {x + d for x in dp}
m = min(abs(x) for x in dp)
a, b = (N + m) // 2, (N - m) // 2
print(a*(a-1)//2 + b*(b-1)//2)

Solution (Python):
from collections import deque
import sys
from operator import itemgetter
N,M = map(int,input().split())
table=[[1]*N for i in range(N)]
for i in range(N):
    table[i][i]=0
for i in range(M):
    a,b=map(int,input().split())
    table[a-1][b-1]=0
    table[b-1][a-1]=0
visit=[False]*N
color =[-1]*N
def f(i):
    q=deque()
    q.append(i)
    color[i]=0
    visit[i]=True
    r=[0,0]
    r[0]+=1
    while q:
        x= q.popleft()
        for j in range(N):
            if table[x][j]==0:
                continue
            if visit[j]:
                if (color[x]==color[j]):
                    print(-1)
                    sys.exit()
                continue
            q.append(j)
            color[j]=(color[x]+1)%2
            r[color[j]]+=1
            visit[j]=True
    return r
ans=[]
for i in range(N):
    if not visit[i]:
        ans.append(f(i))

dp=[set() for i in range(len(ans)+1)]
dp[0].add(0)
L=N//2+1
for i in range(1,len(ans)+1):
    for a in dp[i-1]:
        if a+ans[i-1][0]<L:
            dp[i].add(a+ans[i-1][0])
        if a+ans[i-1][1]<L:
            dp[i].add(a+ans[i-1][1])
    
s = max(dp[len(ans)])
def dou(k):
    return (k*(k-1))//2
print(dou(s) + dou(N-s))