Submission #6354124

---

Source Code Expand

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 Info

Judge Result