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



Sample input:
5 5
1 2
1 3
3 4
3 5
4 5


Sample output:
4

Submission status: Accepted

Solution code:
"""
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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:

"""
Writer:SPD_9X2
https://atcoder.jp/contests/arc099/tasks/arc099_c

なるべく均等に分けるのが正解
制約を受けるのはv-uの辺が存在しない場合
補グラフで考えると、辺がある2点は同じ側に属してはいけない、という問題になる

→2部グラフにならない連結成分がある場合-1

あとは、連結成分ごとにどちらに属すかを決め、その差を最小化すればよい
→dpで見つけられる！

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

AB = []
olis = [ [1] * N for i in range(N) ]
for i in range(N):
    olis[i][i] = 0

for i in range(M):

    A,B = map(int,input().split())
    A -= 1
    B -= 1
    olis[A][B] = 0
    olis[B][A] = 0

non_visit = [True] * N
state = [None] * N
dif = []
ns = [0,0]

#2部グラフ探索

def dfs(p,nst):

    if non_visit[p]:
        non_visit[p] = False
        state[p] = nst
        ns[nst] += 1
        
        for j in range(N):
            if p!=j and olis[p][j] == 1:
                dfs(j,nst^1)
    
    elif nst != state[p]:
        print (-1)
        sys.exit()

    return;

for i in range(N):

    ns = [0,0]

    if non_visit[i]:
        dfs(i,0)
        #print (i)
        dif.append(abs(ns[0]-ns[1]))

dp = [False] * 1500
dp[0] = True

for i in dif:

    ndp = [False] * 1500

    for j in range(1500):

        if dp[j]:
            ndp[(j-i)%1500] = True
            ndp[(j+i)%1500] = True

    dp = ndp

for i in range(N):

    if dp[i] or dp[-1*i]:

        for j in range(N):

            if abs(N-j - j) == i:
                x = j
                y = N-j

                print (x*(x-1)//2 + y*(y-1)//2)
                sys.exit()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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

# MOD = 998244353


# つながってないところに辺を張る
# 二部グラフになるか
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()
# pairs をどう分割するか
# どっちかを選んで作れる数を列挙する
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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# 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)