Problem: There are N persons called Person 1 through Person N.  You are given M facts that "Person A_i and Person B_i are friends." The same fact may be given multiple times.  If X and Y are friends, and Y and Z are friends, then X and Z are also friends. There is no friendship that cannot be derived from the M given facts.  Takahashi the evil wants to divide the N persons into some number of groups so that every person has no friend in his/her group.  At least how many groups does he need to make?

Submission attempts (in order):

def main():
    from itertools import chain
    import sys
    input = sys.stdin.readline

    def gcd(x, y):
        if y == 0:
            return x
        return gcd(y, x % y)
    
    def prime_set(N):
        
        if N < 4:
            return ({}, {}, {2}, {2, 3})[N]
        Nsq = int(N ** 0.5 + 0.5) + 1
        primes = {2, 3} | set(chain(range(5, N + 1, 6), range(7, N + 1, 6)))
        for i in range(5, Nsq, 2):
            if i in primes:
                primes -= set(range(i * i, N + 1, i * 2))
        return list(primes)

    def factorization(n, prime_set):
        l = []
        tmp = n
        nsq = int(n ** 0.5 + 0.5) + 1
        for i in prime_set:
            if  i > nsq: 
                break 
            if tmp%i == 0:
                while tmp%i == 0:
                    tmp //= i
                l.append(i)
        if tmp != 1:
            l.append(tmp)
        if l == []:
            if n != 1:
                l.append(n)
        return l
    n = int(input())
    A = [int(x) for x in input().split()]
    len_A = len(A)
    
    g = 0
    for a in A:
        g = gcd(g, a)
    
    num = 10**6+1
    primes = prime_set(num)
    
    prime_list = [0] * (num+1)
    pairwise_f = True
    ll = list()
    for a in A:
        l = []
        tmp = a
        
        for i in primes:
            if  i*i > a:
                break 
            if tmp%i == 0:
                while tmp%i == 0:
                    tmp //= i
                prime_list[i] += 1
                l.append(i)
        if tmp != 1:
            prime_list[tmp] += 1
            l.append(tmp)
        if l == []:
            if a != 1:
                prime_list[n] += 1
                l.append(a)
        set_prime_list = set(prime_list)
        if len_A > 10**5:
            if set_prime_list != set([0]) and set_prime_list != set([0, 1]):
                pairwise_f = False
                break
    
    if set_prime_list != set([0]) and set_prime_list != set([0, 1]):
        pairwise_f = False
    if pairwise_f:
        print('pairwise coprime')
    elif g == 1:
        print('setwise coprime')
    else:
        print('not coprime')

if __name__ == '__main__':
    main()

def main():
    n, m = map(int, input().split())
    g = [[] for i in [0]*(n+1)]
    for _ in range(m):
        a, b = map(int, input().split())
        g[a].append(b)
        g[b].append(a)

    def bfs(n, m, adj):
        visited = [0 for i in [0]*(n+1)]
        ans = 1
        for i in range(n+1):
            if visited[i]:
                continue
            Q = deque([i])
            temp = 1
            while Q:
                q = Q.popleft()
                visited[q] = 1
                link = adj[q]
                for j in link:
                    if visited[j]:
                        continue
                    visited[j] = 1
                    temp += 1
                    Q.append(j)
            ans = max(ans, temp)
        print(ans)  
    bfs(n, m, g)
 
if __name__=="__main__":
    main()

from collections import deque
from copy import deepcopy

def main():
 
    n, m = map(int, input().split())
    adj = [[] for _ in range(n)]
    for i in range(m):
        a, b = map(lambda x: int(x) - 1, input().split())
        print(a, b)
        adj[a].append(b)
        adj[b].append(a)
    print(adj)

    dist = [-1] * n
    q = deque([0])
    dist[0] = 0
    dl = 0
    while q:
        v = q.popleft()
        d = dist[v]
        for w in adj[v]:
            if dist[w] > -1:
                continue
            dist[w] = d + 1
            q.append(w)
    dl = sum([1 for i in dist if i >= 0])
    print(dl)
    def search_index(l, x, default=False):
        return l.index(x) if x in l else default
    print(search_index(dist, -1))

    dist_0 = deepcopy(dist)
    next = 1
    while next:
        next = search_index(dist_0, -1)
        print('next', next)
        if next == False:
            break
        q = deque([next])
        dist = [-1] * n
        dist[next] = 0
        while q:
            v = q.popleft()
            d = dist[v]
            for w in adj[v]:
                if dist[w] > -1:
                    continue
                dist[w] = d + 1
                q.append(w)
                sum_d = sum([1 for i in dist if i >= 0])
        if dl[0] < sum_d:
            dl = sum_d
        dist_0[next] = 0
    print('dl', dl)

if __name__ == '__main__':
    main()

def find(target):
    if parent[target] < 0:
        return target
    else:
        parent[target] = find(parent[target])
        return parent[target]

def is_same(x, y):
    return find(x) == find(y)

def union(x, y):
    root_x = find(x)
    root_y = find(y)
    if root_x == root_y:
        return
    if parent[root_x] > parent[root_y]:
        root_x, root_y = root_y, root_x
    parent[root_x] += parent[root_y]
    parent[root_y] = root_x
def members(n, x):
    root = find(x)
    return [i for i in range(n) if find(i) == root]

def get_size(x):
    return -parent[find(x)]

def get_root():
    return [i for i, root in enumerate(parent) if root < 0]
n, m = map(int, input().split())
parent = [-1 for _ in range(n)]
for _ in range(m):
    a, b = map(lambda x: int(x) - 1, input().split())
    union(a, b)
    # print(parent)
ans = 0
for i in range(n):
    ans = max(ans, get_size(i))
print(ans)

Verdicts: Runtime Error

Runtime Error

Runtime Error

Accepted