Submission #47540369

---

Source Code Expand

from collections import deque

N,M=map(int,input().split())
dist=[[0]*N for i in range(N)]
for i in range(M):
    A,B=map(int,input().split())
    dist[A-1][B-1]=1
    dist[B-1][A-1]=1
gr=[set() for i in range(N)]
for i in range(N):
    for j in range(i+1,N):
        if dist[i][j]==0:
            gr[i].add(j)
            gr[j].add(i)
dp=[0]*(N*2)
dp[0]=1
now=[-1]*N
for i in range(N):
    wb=[1,0]
    if now[i]==-1:
        now[i]=0
        vert=deque([i])
        while len(vert)>0:
            pos=vert.pop()
            for i in gr[pos]:
                if now[i]!=-1 and now[i]!=1-now[pos]:
                    print(-1)
                    exit()
                if now[i]==-1:
                    now[i]=1-now[pos]
                    wb[now[i]]+=1
                    vert.append(i)
        for i in range(N,-1,-1):
            if dp[i]==1:
                dp[i]=0
                dp[i+wb[0]]=1
                dp[i+wb[1]]=1
ans=N*N
for i in range(N+1):
    if dp[i]==1:
        ans=min(ans,i*(i-1)//2+(N-i)*(N-i-1)//2)
print(ans)

Submission Info

Judge Result