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: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

class BipartiteMatching:
    def __init__(self, V):
        self.V = V
        self.G = [[] for _ in range(V)]

    def add_edge(self, u, v):
        self.G[u].append(v)
        self.G[v].append(u)

    def dfs(self, u):
        self.used[u] = True
        for v in self.G[u]:
            w = self.match[v]
            if w < 0 or (not self.used[w] and self.dfs(w)):
                self.match[u] = v
                self.match[v] = u
                return True
        return False

    def bipartite_matching(self):
        res = 0
        self.match = [-1] * self.V
        for v in range(self.V):
            if self.match[v] == -1:
                self.used = [False] * self.V
                if self.dfs(v):
                    res += 1
        return res

N, M = map(int, input().split())
G = [set() for _ in range(N)]
for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    G[A].add(B)
    G[B].add(A)

G_comp = [[] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i != j and j not in G[i]:
            G_comp[i].append(j)

color = [-1] * N
A = []
dp = set([0])
for i in range(N):
    if color[i] != -1:
        continue
    bm = BipartiteMatching(N)
    cnt = 1
    color[i] = 0
    stack = [i]
    while stack:
        v = stack.pop()
        for u in G_comp[v]:
            if color[u] == -1:
                color[u] = 1 - color[v]
                stack.append(u)
                bm.add_edge(u, v)
                cnt += 1
            if color[u] == color[v]:
                print(-1)
                exit()
    s = bm.bipartite_matching()
    ndp = set()
    for a in dp:
        ndp.add(a + s)
        ndp.add(a + cnt - s)
    dp = ndp
ans = float('inf')
for a in dp:
    ans = min(ans, a * (a - 1) // 2 + (N - a) * (N - a - 1) // 2)
print(ans)

Submission status: Wrong Answer

Solution code:
print(-1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

class BipartiteMatching:
    def __init__(self, V):
        self.V = V
        self.G = [[] for _ in range(V)]

    def add_edge(self, u, v):
        self.G[u].append(v)
        self.G[v].append(u)

    def dfs(self, u):
        self.used[u] = True
        for v in self.G[u]:
            w = self.match[v]
            if w < 0 or (not self.used[w] and self.dfs(w)):
                self.match[u] = v
                self.match[v] = u
                return True
        return False

    def bipartite_matching(self):
        res = 0
        self.match = [-1] * self.V
        for v in range(self.V):
            if self.match[v] == -1:
                self.used = [False] * self.V
                if self.dfs(v):
                    res += 1
        return res

N, M = map(int, input().split())
G = [set() for _ in range(N)]
for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    G[A].add(B)
    G[B].add(A)

G_comp = [[] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i != j and j not in G[i]:
            G_comp[i].append(j)

color = [-1] * N
ans = 0
A = []
B = []
for i in range(N):
    if color[i] != -1:
        continue
    bm = BipartiteMatching(N)
    cnt = 1
    color[i] = 0
    stack = [i]
    while stack:
        v = stack.pop()
        for u in G_comp[v]:
            if color[u] == -1:
                color[u] = 1 - color[v]
                stack.append(u)
                bm.add_edge(u, v)
                cnt += 1
            if color[u] == color[v]:
                print(-1)
                exit()
    s = bm.bipartite_matching()
    A.append(cnt - 2 * s)
dp = set([0])
for i in range(len(A)):
    ndp = set()
    for j in dp:
        ndp.add(abs(j + A[i]))
        ndp.add(abs(j - A[i]))
    dp = ndp
d = min(dp)
a = (N + d) // 2
b = (N - d) // 2
ans = a * (a - 1) // 2 + b * (b - 1) // 2
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class UnionFind:
    def __init__(self, n):
        self.state = [-1] * n
        self.size_table = [1] * n
        # cntはグループ数
        # self.cnt = n

    def root(self, u):
        v = self.state[u]
        if v < 0: return u
        self.state[u] = res = self.root(v)
        return res

    def merge(self, u, v):
        ru = self.root(u)
        rv = self.root(v)
        if ru == rv: return
        du = self.state[ru]
        dv = self.state[rv]
        if du > dv: ru, rv = rv, ru
        if du == dv: self.state[ru] -= 1
        self.state[rv] = ru
        # self.cnt -= 1
        self.size_table[ru] += self.size_table[rv]
        return

    # グループの要素数
    def size(self, u):
        return self.size_table[self.root(u)]

def ng():
    for u in range(n):
        for v in range(n):
            if v == u: continue
            if to[u][v]: continue
            if uf.root(u)==uf.root(v):return True
    return False

n,m=MI()
to=[[False]*n for _ in range(n)]
for _ in range(m):
    u,v=MI1()
    to[u][v]=to[v][u]=True

uf=UnionFind(n)
uncon=[-1]*n
for u in range(n):
    pv=-1
    for v in range(n):
        if v==u:continue
        if to[u][v]:continue
        if pv==-1:pv=v
        else:uf.merge(pv,v)
    uncon[u]=pv

#print(uf.state)
#print(uf.size_table)
#print(uncon)

if ng():
    print(-1)
    exit()

fin=[False]*n
free=0
ss=[]
for u in range(n):
    if uncon[u]==-1:
        free+=1
        continue
    r0=uf.root(u)
    if fin[r0]:continue
    r1=uf.root(uncon[u])
    fin[r0]=fin[r1]=True
    ss.append(abs(uf.size_table[r0]-uf.size_table[r1]))
#print(free,ss)
cur=1
for s in ss:cur=cur<<s|cur>>s
d=(cur&-cur).bit_length()-1
d=max(0,d-free)
s0=(n-d)//2
s1=n-s0
print(s0*(s0-1)//2+s1*(s1-1)//2)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
adjList = [[0] * n for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    adjList[a][b] = 1
    adjList[b][a] = 1
def applyComp(a):
    for i in range(len(a)):
        for j in range(len(a[i])):
            a[i][j] = 1 - a[i][j]
applyComp(adjList)

visited = [0] * n
def dfs(u, parent=-1, color=1):
    #print(u, color)
    if visited[u]:
        if visited[u] != color:
            return None
        else:
            return 0, 0
    visited[u] = color
    oneCount = 0
    twoCount = 0
    if color == 1:
        oneCount += 1
    else:
        twoCount += 1
    for v in range(n):
        if u == v or parent == v:
            continue
        if adjList[u][v]:
            p = dfs(v, u, 3 - color)
            if p is None:
                return None
            oneCount += p[0]
            twoCount += p[1]
    return oneCount, twoCount
connSize = []
for i in range(n):
    if visited[i]:
        continue
    p = dfs(i)
    if p is None:
        print(-1)
        exit()
    connSize.append(p)
dp = [False] * (n + 1)
dp[0] = True
for c1, c2 in connSize:
    for i in range(n, -1, -1):
        if dp[i]:
            dp[i+c1] = True
            dp[i+c2] = True
sz1 = n // 2
while dp[sz1] == False:
    sz1 -= 1
sz2 = n - sz1
print(sum(sz * (sz - 1) // 2 for sz in [sz1, sz2]))

Submission status: Wrong Answer

Solution code:
import sys
from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """5 5
1 2
1 3
3 4
3 5
4 5"""
        output = """4"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """5 1
1 2"""
        output = """-1"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """4 3
1 2
1 3
2 3"""
        output = """3"""
        self.assertIO(input, output)
    def test_入力例_4(self):
        input = """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"""
        output = """21"""
        self.assertIO(input, output)



from itertools import combinations
def spl(target:set,connections:list):
    Agroup = set()
    Bgroup = set()
    v = 0
    for i in target:
        v = i
        break

    for i in target:
        if i in connections[v]:
            Agroup.add(i)
        else:
            Bgroup.add(i)
    Bcon= set(target)
    for i in Bgroup:
        Bcon &= connections[i]
    

    if not Bgroup.issubset(Bcon):
        print(-1)
        return
    
    bconwith0 = Bcon - Bgroup

    Agroup -= bconwith0

    Acon= set(target)
    for i in Agroup:
        Acon &= connections[i]

    if not Agroup.issubset(Acon):
        print(-1)
        return

    while len(bconwith0) != 0:
        ns = set()
        for i in bconwith0:
            if i in Acon:
                if i in Bcon:
                    ns.add(i)
                else:
                    Agroup.add(i)
                    Acon &= connections[i]
            else:
                if i in Bcon:
                    Bgroup.add(i)
                    Bcon &= connections[i]
                else:
                    print(-1)
                    return
        
        if bconwith0.__len__() == ns.__len__():
            break
        bconwith0= ns

    return(Agroup,Bgroup,bconwith0)

def c2 (x):
    return x*(x-1)//2

def validation(target:set,connections):
    for i,j in combinations(target,2):
        if not i in connections[j]:
            return True
    return False
def validation2(taregt:set,valied_set:set,connections):
    for i in taregt:
        for j in valied_set:
            if not i in connections[j]:
                raise

def resolve():
    N,M = map(int,input().split())

    connections = [set([i]) for i in range(N)]
    for i in range(M):
        A,B = map(int,input().split())
        connections[A-1].add(B-1)
        connections[B-1].add(A-1)
    
    free  = set(range(N))
    lst = []
    while len(free) !=0:
        res =spl(free,connections)
        if res==None:

            return
        i,j,k = res

        if validation(i,connections):
            print(-1)
            raise

        if validation(j, connections):
            print(-1)
            raise
        validation2(k,j,connections)
        validation2(k,i,connections)

        lst.append((len(i),len(j),k))

        if len(free) == len(k):
            
            break
        free= lst[-1][2]
    free = lst[-1][2]

    dpt = set([(0,0)])
    for i,j,k in  lst:
        ndp= set()

        for k,l in dpt:
            ndp.add((i+k,j+l))
            ndp.add((j+k,i+l))
        dpt = ndp
    freec = lst[-1][2].__len__()
    if validation(lst[-1][2],connections):
        print(-1)
        return

    dpt = list(dpt)
    dpt.sort(reverse=True)
    mn = float("inf")
    for i,j in dpt:
        if i > j:
            i,j = j,i
        if i+freec > j:
            i = N//2
            j = (N+1)//2
        else:
            i += freec
        if i+j != N:
            raise
        mn = min(mn,c2(i)+c2(j))


    print(mn)

if __name__ == "__main__":
    resolve()
    #unittest.main()

Submission status: Wrong Answer

Solution code:
from itertools import combinations
def spl(target:set,connections:list):
    Agroup = set()
    Bgroup = set()
    v = 0
    for i in target:
        v = i
        break

    for i in target:
        if i in connections[v]:
            Agroup.add(i)
        else:
            Bgroup.add(i)
    Bcon= set(target)
    for i in Bgroup:
        Bcon &= connections[i]
    

    if not Bgroup.issubset(Bcon):
        print(-1)
        return
    
    bconwith0 = Bcon - Bgroup

    Agroup -= bconwith0

    Acon= set(target)
    for i in Agroup:
        Acon &= connections[i]

    if not Agroup.issubset(Acon):
        print(-1)
        return

    while len(bconwith0) != 0:
        ns = set()
        for i in bconwith0:
            if i in Acon:
                if i in Bcon:
                    ns.add(i)
                else:
                    Agroup.add(i)
                    Acon &= connections[i]
            else:
                if i in Bcon:
                    Bgroup.add(i)
                    Bcon &= connections[i]
                else:
                    print(-1)
                    return
        
        if bconwith0.__len__() == ns.__len__():
            break
        bconwith0= ns

    return(Agroup,Bgroup,bconwith0)

def c2 (x):
    return x*(x-1)//2

def validation(target:set,connections):
    for i,j in combinations(target,2):
        if not i in connections[j]:
            return True
    return False
def validation2(taregt:set,valied_set:set,connections):
    for i in taregt:
        for j in valied_set:
            if not i in connections[j]:
                raise

def resolve():
    N,M = map(int,input().split())

    connections = [set([i]) for i in range(N)]
    for i in range(M):
        A,B = map(int,input().split())
        connections[A-1].add(B-1)
        connections[B-1].add(A-1)
    
    free  = set(range(N))
    lst = []
    while len(free) !=0:
        res =spl(free,connections)
        if res==None:

            return
        i,j,k = res

        validation(i,connections)
        validation(j, connections)
        validation2(k,j,connections)
        validation2(k,i,connections)

        lst.append((len(i),len(j),k))

        if len(free) == len(k):
            
            break
        free= lst[-1][2]
    free = lst[-1][2]

    dpt = set([(0,0)])
    for i,j,k in  lst:
        ndp= set()

        for k,l in dpt:
            ndp.add((i+k,j+l))
            ndp.add((j+k,i+l))
        dpt = ndp
    freec = lst[-1][2].__len__()
    if validation(lst[-1][2],connections):
        print(-1)
        return

    dpt = list(dpt)
    dpt.sort(reverse=True)
    mn = float("inf")
    for i,j in dpt:
        if i > j:
            i,j = j,i
        if i+freec > j:
            i = N//2
            j = (N+1)//2
        else:
            i += freec
        if i+j != N:
            raise
        mn = min(mn,c2(i)+c2(j))


    print(mn)

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
from itertools import combinations
def spl(target:set,connections:list):
    Agroup = set()
    Bgroup = set()
    v = 0
    for i in target:
        v = i
        break

    for i in target:
        if i in connections[v]:
            Agroup.add(i)
        else:
            Bgroup.add(i)
    Bcon= set(target)
    for i in Bgroup:
        Bcon &= connections[i]
    

    if not Bgroup.issubset(Bcon):
        print(-1)
        return
    
    bconwith0 = Bcon - Bgroup

    Agroup -= bconwith0

    Acon= set(target)
    for i in Agroup:
        Acon &= connections[i]

    if not Agroup.issubset(Acon):
        print(-1)
        return

    while len(bconwith0) != 0:
        ns = set()
        for i in bconwith0:
            if i in Acon:
                if i in Bcon:
                    ns.add(i)
                else:
                    Agroup.add(i)
                    Acon &= connections[i]
            else:
                if i in Bcon:
                    Bgroup.add(i)
                    Bcon &= connections[i]
                else:
                    print(-1)
                    return
        
        if bconwith0.__len__() == ns.__len__():
            break
        bconwith0= ns

    return(Agroup,Bgroup,bconwith0)

def c2 (x):
    return x*(x-1)//2

def validation(target:set,connections):
    for i,j in combinations(target,2):
        if not i in connections[j]:
            return True
    return False
def validation2(taregt:set,valied_set:set,connections):
    for i in taregt:
        for j in valied_set:
            if not i in connections[j]:
                raise

def resolve():
    N,M = map(int,input().split())

    connections = [set([i]) for i in range(N)]
    for i in range(M):
        A,B = map(int,input().split())
        connections[A-1].add(B-1)
        connections[B-1].add(A-1)
    
    free  = set(range(N))
    lst = []
    while len(free) !=0:
        res =spl(free,connections)
        if res==None:

            return
        i,j,k = res

        validation(i,connections)
        validation(j, connections)
        validation2(k,j,connections)
        validation2(k,i,connections)

        lst.append((len(i),len(j),k))

        if len(free) == len(k):
            
            break
        free= lst[-1][2]
    free = lst[-1][2]
    if validation(free,connections):
        print(-1)
        return
    dpt = set([(0,0)])
    for i,j,k in  lst:
        ndp= set()

        for k,l in dpt:
            ndp.add((i+k,j+l))
            ndp.add((j+k,i+l))
        dpt = ndp
    freec = lst[-1][2].__len__()

    dpt = list(dpt)
    dpt.sort(reverse=True)
    mn = float("inf")
    for i,j in dpt:
        if i > j:
            i,j = j,i
        if i+freec > j:
            i = N//2
            j = (N+1)//2
        else:
            i += freec
        if i+j != N:
            raise
        mn = min(mn,c2(i)+c2(j))


    print(mn)

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
from itertools import combinations
def spl(target:set,connections:list):
    Agroup = set()
    Bgroup = set()
    v = 0
    for i in target:
        v = i
        break

    for i in target:
        if i in connections[v]:
            Agroup.add(i)
        else:
            Bgroup.add(i)
    Bcon= set(target)
    for i in Bgroup:
        Bcon &= connections[i]
    

    if not Bgroup.issubset(Bcon):
        print(-1)
        return
    
    bconwith0 = Bcon - Bgroup

    Agroup -= bconwith0

    Acon= set(target)
    for i in Agroup:
        Acon &= connections[i]

    if not Agroup.issubset(Acon):
        print(-1)
        return

    while len(bconwith0) != 0:
        ns = set()
        for i in bconwith0:
            if i in Acon:
                if i in Bcon:
                    ns.add(i)
                else:
                    Agroup.add(i)
                    Acon &= connections[i]
            else:
                if i in Bcon:
                    Bgroup.add(i)
                    Bcon &= connections[i]
                else:
                    print(-1)
                    return
        
        if bconwith0.__len__() == ns.__len__():
            break
        bconwith0= ns

    return(Agroup,Bgroup,bconwith0)

def c2 (x):
    return x*(x-1)//2

def validation(target:set,connections):
    for i,j in combinations(target,2):
        if not i in connections[j]:
            return True
    return False
def validation2(taregt:set,valied_set:set,connections):
    for i in taregt:
        for j in valied_set:
            if not i in connections[j]:
                raise

def resolve():
    N,M = map(int,input().split())

    connections = [set([i]) for i in range(N)]
    for i in range(M):
        A,B = map(int,input().split())
        connections[A-1].add(B-1)
        connections[B-1].add(A-1)
    
    free  = set(range(N))
    lst = []
    while len(free) !=0:
        res =spl(free,connections)
        if res==None:

            return
        i,j,k = res

        validation(i,connections)
        validation(j, connections)
        validation2(k,j,connections)
        validation2(k,i,connections)

        lst.append((len(i),len(j),k))

        if free.__len__() == lst[-1][2].__len__():
            break
        free= lst[-1][2]
    if validation(free,connections):
        print(-1)
        return
    dpt = set([(0,0)])
    for i,j,k in  lst:
        ndp= set()

        for k,l in dpt:
            ndp.add((i+k,j+l))
            ndp.add((j+k,i+l))
        dpt = ndp
    freec = lst[-1][2].__len__()

    dpt = list(dpt)
    dpt.sort(reverse=True)
    mn = float("inf")
    for i,j in dpt:
        if i > j:
            i,j = j,i
        if i+freec > j:
            i = N//2
            j = (N+1)//2
        else:
            i += freec
        if i+j != N:
            raise
        mn = min(mn,c2(i)+c2(j))


    print(mn)

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
from itertools import combinations
def spl(target:set,connections:list):
    Agroup = set()
    Bgroup = set()
    v = 0
    for i in target:
        v = i
        break

    for i in target:
        if i in connections[v]:
            Agroup.add(i)
        else:
            Bgroup.add(i)
    Bcon= set(target)
    for i in Bgroup:
        Bcon &= connections[i]
    

    if not Bgroup.issubset(Bcon):
        print(-1)
        return
    
    bconwith0 = Bcon - Bgroup

    Agroup -= bconwith0

    Acon= set(target)
    for i in Agroup:
        Acon &= connections[i]

    if not Agroup.issubset(Acon):
        print(-1)
        return

    while len(bconwith0) != 0:
        ns = set()
        for i in bconwith0:
            if i in Acon:
                if i in Bcon:
                    ns.add(i)
                else:
                    Agroup.add(i)
                    Acon &= connections[i]
            else:
                if i in Bcon:
                    Bgroup.add(i)
                    Bcon &= connections[i]
                else:
                    print(-1)
                    return
        
        if bconwith0.__len__() == ns.__len__():
            break
        bconwith0= ns
    return(Agroup,Bgroup,bconwith0)

def c2 (x):
    return x*(x-1)//2

def validation(target:set,connections):
    for i,j in combinations(target,2):
        if not i in connections[j]:
            raise
def validation2(taregt:set,valied_set:set,connections):
    for i in taregt:
        for j in valied_set:
            if not i in connections[j]:
                raise

def resolve():
    N,M = map(int,input().split())

    connections = [set([i]) for i in range(N)]
    for i in range(M):
        A,B = map(int,input().split())
        connections[A-1].add(B-1)
        connections[B-1].add(A-1)
    
    free  = set(range(N))
    lst = []
    while len(free) !=0:
        res =spl(free,connections)
        if res==None:

            return
        i,j,k = res

        validation(i,connections)
        validation(j, connections)
        validation2(k,j,connections)
        validation2(k,i,connections)

        lst.append((len(i),len(j),k))

        if free.__len__() == lst[-1][2].__len__():
            break
        free= lst[-1][2]
    dpt = set([(0,0)])
    for i,j,k in  lst:
        ndp= set()

        for k,l in dpt:
            ndp.add((i+k,j+l))
            ndp.add((j+k,i+l))
        dpt = ndp
    freec = lst[-1][2].__len__()

    dpt = list(dpt)
    dpt.sort(reverse=True)
    mn = float("inf")
    for i,j in dpt:
        if i > j:
            i,j = j,i
        if i+freec > j:
            i = N//2
            j = (N+1)//2
        else:
            i += freec
        if i+j != N:
            raise
        mn = min(mn,c2(i)+c2(j))


    print(mn)

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
from itertools import combinations
def spl(target:set,connections:list):
    Agroup = set()
    Bgroup = set()

    for i in target:
        if i in connections[0]:
            Agroup.add(i)
        else:
            Bgroup.add(i)
    Bcon= set(target)
    for i in Bgroup:
        Bcon &= connections[i]
    

    if not Bgroup.issubset(Bcon):
        print(-1)
        return
    
    bconwith0 = Bcon - Bgroup

    Agroup -= bconwith0

    Acon= set(target)
    for i in Agroup:
        Acon &= connections[i]

    if not Agroup.issubset(Acon):
        print(-1)
        return

    while len(bconwith0) != 0:
        ns = set()
        for i in bconwith0:
            if i in Acon:
                if i in Bcon:
                    ns.add(i)
                else:
                    Agroup.add(i)
                    Acon &= connections[i]
            else:
                if i in Bcon:
                    Bgroup.add(i)
                    Bcon &= connections[i]
                else:
                    print(-1)
                    return
        
        if bconwith0.__len__() == ns.__len__():
            break
        bconwith0= ns
    return(Agroup,Bgroup,bconwith0)

def c2 (x):
    return x*(x-1)//2

def validation(target:set,connections):
    for i,j in combinations(target,2):
        if not i in connections[j]:
            raise
def validation2(taregt:set,valied_set:set,connections):
    for i in taregt:
        for j in valied_set:
            if not i in connections[j]:
                raise

def resolve():
    N,M = map(int,input().split())

    connections = [set([i]) for i in range(N)]
    for i in range(M):
        A,B = map(int,input().split())
        connections[A-1].add(B-1)
        connections[B-1].add(A-1)
    
    free  = set(range(N))
    lst = []
    while len(free) !=0:
        res =spl(free,connections)
        if res==None:

            return
        i,j,k = res

        validation(i,connections)
        validation(j, connections)
        validation2(k,j,connections)
        validation2(k,i,connections)

        lst.append((len(i),len(j),k))

        if free.__len__() == lst[-1][2].__len__():
            break
        free= lst[-1][2]
    dpt = set([(0,0)])
    for i,j,k in  lst:
        ndp= set()

        for k,l in dpt:
            ndp.add((i+k,j+l))
            ndp.add((j+k,i+l))
        dpt = ndp
    freec = lst[-1][2].__len__()

    dpt = list(dpt)
    dpt.sort(reverse=True)
    mn = float("inf")
    for i,j in dpt:
        if i > j:
            i,j = j,i
        if i+freec > j:
            i = N//2
            j = (N+1)//2
        else:
            i += freec
        if i+j != N:
            raise
        mn = min(mn,c2(i)+c2(j))


    print(mn)

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
def spl(target:set,connections:list):
    Agroup = set()
    Bgroup = set()

    for i in target:
        if i in connections[0]:
            Agroup.add(i)
        else:
            Bgroup.add(i)
    Bcon= set(target)
    for i in Bgroup:
        Bcon &= connections[i]
    

    if not Bgroup.issubset(Bcon):
        print(-1)
        return
    
    bconwith0 = Bcon - Bgroup

    Agroup -= bconwith0

    Acon= set(target)
    for i in Agroup:
        Acon &= connections[i]

    if not Agroup.issubset(Acon):
        print(-1)
        return

    while len(bconwith0) != 0:
        ns = set()
        for i in bconwith0:
            if i in Acon:
                if i in Bcon:
                    ns.add(i)
                else:
                    Agroup.add(i)
                    Acon &= connections[i]
            else:
                if i in Bcon:
                    Bgroup.add(i)
                    Bcon &= connections[i]
                else:
                    print(-1)
                    return
        
        if bconwith0.__len__() == ns.__len__():
            break
        bconwith0= ns
    return(Agroup,Bgroup,bconwith0)

def c2 (x):
    return x*(x-1)//2

def resolve():
    N,M = map(int,input().split())

    connections = [set([i]) for i in range(N)]
    for i in range(M):
        A,B = map(int,input().split())
        connections[A-1].add(B-1)
        connections[B-1].add(A-1)
    
    free  = set(range(N))
    lst = []
    while len(free) !=0:
        res =spl(free,connections)
        if res==None:

            return
        i,j,k = res
        lst.append((len(i),len(j),k))

        if free.__len__() == lst[-1][2].__len__():
            break
        free= lst[-1][2]
    dpt = set([(0,0)])
    for i,j,_ in  lst:
        ndp= set()
        for k,l in dpt:
            ndp.add((i+k,j+l))
            ndp.add((j+k,i+l))
        dpt = ndp
    freec = lst[-1][2].__len__()

    dpt = list(dpt)
    dpt.sort(reverse=True)
    mn = float("inf")
    for i,j in dpt:
        if i > j:
            i,j = j,i
        if i+freec > j:
            i = N//2
            j = (N+1)//2
        else:
            i += freec
        if i+j != N:
            raise
        mn = min(mn,c2(i)+c2(j))


    print(mn)

if __name__ == "__main__":
    resolve()