Problem:


Score : 400 points

Problem Statement

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?

Constraints

2 \leq N \leq 2\times 10^5

0 \leq M \leq 2\times 10^5

1\leq A_i,B_i\leq N

A_i \neq B_i

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
\vdots
A_M B_M

Output

Print the answer.

Sample Input 1

5 3
1 2
3 4
5 1

Sample Output 1

3

Dividing them into three groups such as \{1,3\}, \{2,4\}, and \{5\} achieves the goal.

Sample Input 2

4 10
1 2
2 1
1 2
2 1
1 2
1 3
1 4
2 3
2 4
3 4

Sample Output 2

4

Sample Input 3

10 4
3 1
4 1
5 9
2 6

Sample Output 3

3



Sample input:
5 3
1 2
3 4
5 1


Sample output:
3

Submission status: Runtime Error

Solution code:
[n, m] = list(map(int, input().split()))
abList = []
for i in range(m):
    abList.append(list(map(int, input().split())))

class QuickFind(object):
    id = []
    count = 0
    def __init__(self, n):
        self.count = n
        i = 0
        while i < n:
            self.id.append(i)
            i += 1
    def connected(self, p, q):
        return self.find(p) == self.find(q)
    def find(self, p):
        return self.id[p]
    def union(self, p, q):
        idp = self.find(p)
        if not self.connected(p, q):
            for i in range(len(self.id)):
                if self.id[i] == idp:  # 将p所在组内的所有节点的id都设为q的当前id
                    self.id[i] = self.id[q]
            self.count -= 1

qf = QuickFind(10)

for k in abList:
    p = k[0]
    q = k[1]
    qf.union(p, q)

countMax = {}
for x in qf.id:
    if x in countMax:
        countMax[x] += 1
    else:
        countMax[x] = 0
def most_frequent(List):
    counter = 0
    num = List[0]

    for i in List:
        curr_frequency = List.count(i)
        if (curr_frequency > counter):
            counter = curr_frequency
            num = i

    return counter

print(most_frequent(qf.id))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
p=[(i,1)for i in range(n)]
def find(i):
  if p[i][0]==i:return i
  else:
    c=find(p[i][0])
    p[i]=(c,0)
    return c
def union(i,j):
  pi=find(i)
  pj=find(j)
  if not pi==pj:
    if p[pi][1]>p[pj][1]:
      p[pi]=(pi,p[pi][1]+p[pj][1])
      p[pj]=(pi,0)
    else:
      p[pj]=(pj,p[pi][1]+p[pj][1])
      p[pi]=(pj,0)
      

for i in range(m):
  a,b=map(int,input().split())
  union(a,b)
ans=0
for i in range(n):
  if p[i][0]==i:ans=max(ans,p[i][1])
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
I = []
for _ in range(M):
    I.append(list(map(int, input().split())))

ans = 2
f = [I[0][0], I[0][1]]
for i in range(1, M):
    if I[i][0] in f:
        if I[i][1] in f:
            continue
        f.append(I[i][1])
        ans += 1
    elif I[i][1] in f:
        f.append(I[i][0])
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
parent = [-1] * N


def union(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    parent[x] = y


def find(x):
    if parent[x] == -1:
        return x
    res = parent[x] = find(parent[x])
    return res

for _ in range(M):
    a, b = map(int, input().split())
    union(a - 1, b - 1)


count = {}
for i in range(N):
    if (g := find(i)) in count:
        count[g] += 1
    else:
        count[g] = 1
res = 0
for value in count.values():
    res = max(res, value)
print(res)

Submission status: Runtime Error

Solution code:
import collections

n, m = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(m)]

l = []
for _ in range(n):
  l.append([])

# for x in range(n):
#   l[x]

for a, b in ab:
  a -= 1
  b -= 1
  l[a].append(b)
  l[b].append(a)

# c = [None] * n

# for i in range(n):
#   if c[i] is None:
#     c[i] = i
#   for f in l[i]:
#     if c[f] is None:
#       c[f] = i


# https://algo-logic.info/connected-components-num/

color = [None] * n


def dfs(i, c):
  if color[i] is not None:
    return
  color[i] = c

  for f in l[i]:
    dfs(f, c)


for i in range(n):
  if color[i] is None:
    dfs(i, i)

print(max([v for k, v in collections.Counter(color).items()]))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
lst=[]
for i in range(m):
  var=list(map(int,input().split()))

  if var not in lst and var[::-1] not in lst:
    lst.append(var)
d={}
for i in lst:
  d.setdefault(i[0],1)
  d.setdefault(i[1],1)
  d[i[0]]+=1
  d[i[1]]+=1

ans=max(d.values()) 

print(ans)

Submission status: Runtime Error

Solution code:
import collections
def solve():
  N,M = map(int,input().split())
  ABlist = [[0 for _ in range(2)] for _ in range(M)]
  WA = [0]*N
  for i in range(N):
    WA[i] = i+1
  for i in range(M):
    A, B = map(int,input().split())
    if A>B:
      A,B =B,A
    ABlist[i][0] = A
    ABlist[i][1] = B
  ABlist.sort(key=lambda x: (x[0],x[1]))
  for i in range(M):
    A = ABlist[i][0]
    B = ABlist[i][1]
    if WA[B-1]<WA[A-1]:
      WA[A-1] = WA[B-1]
    else:
      WA[B-1] = WA[A-1]
    print(i, WA, A,B)
  c = collections.Counter(WA)
  print(c.most_common()[0][1])
solve()

Submission status: Runtime Error

Solution code:
import itertools
n, m = map(int, input().split())
f = []
for i in range(m):
  a, b = map(int, input().split())
  if a in list(itertools.chain.from_iterable(f)):
    for j in range(len(f)):
      if a in f[j]:
        f[j].append(b)
        break
  elif b in list(itertools.chain.from_iterable(f)):
    for j in range(len(f)):
      if b in f[j]:
        f[j].append(a)
        break
  else:
    f.append([a, b])
arr = []
for i in range(len(f)):
  arr.append(len(list(set(f[i]))))
ans = max(arr)
print(ans)

Submission status: Runtime Error

Solution code:
def solve():
    n, m = map(int, input().split())
    group = []
    done = [-1]*n
    num = 0
    for i in range(m):
        a, b = map(lambda x:int(x)-1, input().split())
        if done[a] != -1:
            if done[b] == -1:
                group[done[a]].append(b)
                done[b] = done[a]
        else:
            if done[b] == -1:
                group.append([a,b])
                done[a], done[b] = num, num
                num += 1
            else:
                group[done[b]].append(a)
                done[a] = done[b]
    people = [0]+[len(i) for i in group]
    amari = done.count(-1)
    ans = max(people)
    if sum(people) > amari:
        print(ans)
    else:
        print(amari)def solve():
    n, m = map(int, input().split())
    group = []
    done = [-1]*n
    num = 0
    for i in range(m):
        a, b = map(lambda x:int(x)-1, input().split())
        if done[a] != -1:
            if done[b] == -1:
                group[done[a]].append(b)
                done[b] = done[a]
        else:
            if done[b] == -1:
                group.append([a,b])
                done[a], done[b] = num, num
                num += 1
            else:
                group[done[b]].append(a)
                done[a] = done[b]
    people = [0]+[len(i) for i in group]
    amari = done.count(-1)
    ans = max(people)
    if sum(people) > amari:
        print(ans)
    else:
        print(amari-ans)
    return 0

if __name__ == "__main__":
    solve()

    return 0

if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
def main():
    N, M = map(int, input().split())

    groups = dict()
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        if a in groups:
            groups[a].add(b)
            groups[b] = groups[a]
        elif b in groups:
            groups[b].add(a)
            groups[a] = groups[b]
        else:
            groups[a] = set([a,b])
            groups[b] = groups[a]

    ans = max(map(len, groups.values()))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
s=[list(map(int,input().split())) for _ in range(M)]

f=[[] for _ in range(N+1)]
for i in range(M):
    f[s[i][0]].append(s[i][1])

found=[0 for _ in range(N+1)]
ans=0

def find(bi,i,root,found):
    if root[i]:
        return
    root[i]=1
    found[i]=1
    f[i].append(bi)
    for j in range(len(f[i])):
        find(i,f[i][j],root,found)

for i in range(1,N+1):
    if found[i]: continue
    root=[0 for _ in range(N+1)]
    find(i,i,root,found)
    tmp=root.count(1)
    if ans<tmp:
        ans=tmp
print(ans)

Submission status: Runtime Error

Solution code:
import collections
n,m = map(int,input().split())

indexlist = [0 for i in range(n)]
indexnum = 1
for _ in range(m):
    a,b = map(int,input().split())
    x = indexlist[a-1]
    y = indexlist[b-1]
    if x == 0 and y == 0:
        indexlist[a-1] = indexnum
        indexlist[b-1] = indexnum
        indexnum += 1
    elif x == 0 and y != 0:
        indexlist[a-1] = y
    elif x != 0 and y == 0:
        indexlist[b-1] = x

c = collections.Counter(indexlist)

often = c.most_common()
#print(often)
for item in often:
    if item[0] == 0:
        often.remove(item)
#print(often)
print(often[0][1])

Submission status: Runtime Error

Solution code:
#D
N,M = map(int, input().split())
L = []
for i in range(N):
    L.append([])
#print(L)
maxim = 0
for i in range(M):
    A,B = map(int, input().split())
    for j in L:
        if A in j and B in j:
            break
        elif A in j:
            j.append(B)
            break
        elif B in j:
            j.append(A)
            break
        else:
            L[maxim] += [A, B]
            maxim += 1
            break
    #print(L)
result = 0
for j in L:
    if len(j)>result:
        result = len(j)
print(result)

Submission status: Runtime Error

Solution code:
import collections

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        else:
            self.parent[x] = y

N, M = map(int, input().split())
tree = UnionFind(N)

for i in range(M):
    A, B = map(int, input().split())
    tree.unite(A-1, B-1)

roots = [tree.find(p) for p in tree.parent]
count = collections.Counter(roots).most_common(1)[0][1]
print(count)

Submission status: Runtime Error

Solution code:
N, M=map(int, input().split())
import collections

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
      
    def main(self):
      return max([len(self.members(r)) for r in self.roots()])
uf = UnionFind(N)

for _ in range(M):
  A, B  = map(int, input().split())
  uf.union(A-1,B-1)

c = collections.Counter([i for i in uf.parents  if i >= 0])

print(c.most_common()[0][1] + 1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque
n,m = list(map(int, input().split()))

d = defaultdict(list)

for _ in range(m):
    
    a,b = list(map(int, input().split()))
    d[a].append(b)
    d[b].append(a)
    
   
def dfs(node):
    
    s = set()
    stack = deque([node])
    while stack:
        
        n = stack.popleft()
        s.add(n)
        for i in d[n]:
            if i not in s and visited[i] == 0:
                stack.append(i)
                
    return s
    

keys = list(d.keys())
m = max(keys)
visited = [0]*(2*10**5+1)
ans = 0
for key in keys:
    if visited[key] == 0:
        ans +=1
        s = dfs(key)
        for i in range(key, m+1):
            if visited[i] == 0 and i not in s:
                visited[i] = 1


print(ans)

Submission status: Runtime Error

Solution code:
import random
import sys

sys.setrecursionlimit(100000)

n, m = map(int, input().split())
# n, m = 200000, 200000
group = {i: 0 for i in range(1, n+1)}
edge = {}
g_mem = {}
g_num = 0
g_con = set()

for i in range(m):
    a, b = map(int, input().split())
    # a, b = random.sample(range(1,n+1), 2)
    if group[a]==0 and group[b] == 0:
        g_num += 1
        group[a] = g_num
        group[b] = g_num
        g_mem[g_num] = 2
    elif group[a] == 0:
        group[a] = group[b]
        g_mem[group[b]] += 1
    elif group[b] == 0:
        group[b] = group[a]
        g_mem[group[a]] += 1
    elif group[a] != group[b]:
        if edge.get(group[a]):
            edge[group[a]].add(group[b])
        else:
            edge[group[a]] = {group[b]}
        if edge.get(group[b]):
            edge[group[b]].add(group[a])
        else:
            edge[group[b]] = {group[a]}

# print(g_mem)
# print(sum(g_mem.values()))
# print(edge)

g_reached = {i: 0 for i in range(1, g_num+1)}

def dps(g_mem, edge, now):
    count = g_mem[now]
    if edge.get(now):
        for e in edge[now]:
            if g_reached[e] == 0:
                g_reached[e] = 1
                count += dps(g_mem, edge, e)
    return count


ans = []
for now in range(1, g_num+1):
    if g_reached[now] == 0:
        g_reached[now] = 1
        ans.append(dps(g_mem, edge, now))

# print(ans)
print(max(ans))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# def get_group_num(sum, nums):
#     if len(nums) == 1:
#         return sum + nums[0]
#     pass

def main():
    n, m = map(int, input().split())
    friends_list = []
    for i in range(m):
        check=True
        a,b = map(int, input().split())
        for i, friends_set in enumerate(friends_list):
             if a in friends_set or b in friends_set:
                 friends_list[i].add(a)
                 friends_list[i].add(b)
                 check = False
                 continue
        if check:
            friends_list.append({a, b})
    group_num = len(friends_list)
    group_nums = []
    for friends_set in (friends_list):
        group_nums.append(len(friends_set))
    ans = max(group_nums)
    print(ans)
    

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import collections

N,M = list(map(int, input().split()))
team_table = [0 for i in range(N)]
color = 0
for i in range(M):
    A,B = list(map(int, input().split()))
    if (team_table[A-1] == 0)&(team_table[B-1] == 0):
        color = A
        team_table[A-1] = color 
        team_table[B-1] = color
    elif (team_table[A-1] == 0)&(team_table[B-1] != 0):
        team_table[A-1] = team_table[B-1]
    elif (team_table[A-1] != 0)&(team_table[B-1] == 0):
        team_table[B-1] = team_table[A-1]
        
ans_table = []
for t in team_table:
    if t != 0:
        ans_table.append(t)
        
ans = collections.Counter(ans_table).most_common()[0][1]
        
print(ans)

Submission status: Runtime Error

Solution code:
import collections
def solve():
  N,M = map(int,input().split())
  ABlist = [[0 for _ in range(2)] for _ in range(M)]
  WA = [0]*N
  for i in range(N):
    WA[i] = i+1
  for i in range(M):
    A, B = map(int,input().split())
    if A>B:
      A,B =B,A
    ABlist[i][0] = A
    ABlist[i][1] = B
  ABlist.sort(key=lambda x: (x[0],x[1]))
  print(ABlist)
  for i in range(M):
    A = ABlist[i][0]
    B = ABlist[i][1]
    if WA[B-1]<WA[A-1]:
      WA[A-1] = WA[B-1]
    else:
      WA[B-1] = WA[A-1]
    print(i, WA, A,B)
  c = collections.Counter(WA)
  print(c.most_common()[0][1])
solve()

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
import collections


class UnionFind2:
    def __init__(self, size):
        # 負の値はルート (集合の代表)
        # 正の値は次の要素を表す
        self.table = [-1 for _ in range(size)]

    # 集合の代表を求める
    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            # 経路の圧縮
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    # 併合
    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            self.table[s2] = s1
            return True
        return False


N, M = map(int, input().split())
uf = UnionFind2(N+1)

for i in range(M):
    A, B = map(int, input().split())
    uf.union(A, B)

hoge = [uf.find(i) for i in range(N)]

# print(hoge)
hogehoge = collections.Counter(hoge).most_common()

print(hogehoge[0][1])

Submission status: Runtime Error

Solution code:
[n, m] = list(map(int, input().split()))
abList = []
for i in range(m):
    abList.append(list(map(int, input().split())))

class QuickFind(object):
    id = []
    count = 0

    def __init__(self, n):
        self.count = n
        i = 0
        while i < n:
            self.id.append(i)
            i += 1

    def connected(self, p, q):
        return self.find(p) == self.find(q)

    def find(self, p):
        return self.id[p]

    def union(self, p, q):
        idp = self.find(p)
        if not self.connected(p, q):
            for i in range(len(self.id)):
                if self.id[i] == idp:  # 将p所在组内的所有节点的id都设为q的当前id
                    self.id[i] = self.id[q]
            self.count -= 1

qf = QuickFind(10)

print
"initial id list is %s" % (",").join(str(x) for x in qf.id)


for k in abList:
    p = k[0]
    q = k[1]
    qf.union(p, q)

countMax = {}
for x in qf.id:
    if x in countMax:
        countMax[x] += 1
    else:
        countMax[x] = 0


def most_frequent(List):
    counter = 0
    num = List[0]

    for i in List:
        curr_frequency = List.count(i)
        if (curr_frequency > counter):
            counter = curr_frequency
            num = i

    return counter


print(most_frequent(qf.id))

Submission status: Runtime Error

Solution code:
import random
import sys

sys.setrecursionlimit(10000)

n, m = map(int, input().split())
# n, m = 200000, 200000
group = {i: 0 for i in range(1, n+1)}
edge = {}
g_mem = {}
g_num = 0
g_con = set()

for i in range(m):
    a, b = map(int, input().split())
    # a, b = random.sample(range(1,n+1), 2)
    if group[a]==0 and group[b] == 0:
        g_num += 1
        group[a] = g_num
        group[b] = g_num
        g_mem[g_num] = 2
    elif group[a] == 0:
        group[a] = group[b]
        g_mem[group[b]] += 1
    elif group[b] == 0:
        group[b] = group[a]
        g_mem[group[a]] += 1
    elif group[a] != group[b]:
        if edge.get(group[a]):
            edge[group[a]].add(group[b])
        else:
            edge[group[a]] = {group[b]}
        if edge.get(group[b]):
            edge[group[b]].add(group[a])
        else:
            edge[group[b]] = {group[a]}

# print(g_mem)
# print(sum(g_mem.values()))
# print(edge)

g_reached = {i: 0 for i in range(1, g_num+1)}

def dps(g_mem, edge, now):
    count = g_mem[now]
    if edge.get(now):
        for e in edge[now]:
            if g_reached[e] == 0:
                g_reached[e] = 1
                count += dps(g_mem, edge, e)
    return count


ans = []
for now in range(1, g_num+1):
    if g_reached[now] == 0:
        g_reached[now] = 1
        ans.append(dps(g_mem, edge, now))

# print(ans)
print(max(ans))

Submission status: Runtime Error

Solution code:
N, M=map(int, input().split())
import collections

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
      
    def main(self):
      return max([len(self.members(r)) for r in self.roots()])
uf = UnionFind(N)

for _ in range(M):
  A, B  = map(int, input().split())
  uf.union(A-1,B-1)

c = collections.Counter([i for i in uf.parents if i>0])
print(c.most_common()[0][1] + 1)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
frl = [] #friend list
number = [0]*n #personal number
lnum = 1
for i in range(m):
	a,b = map(int,input().split())
	if number[a-1] == 0 and number[b-1] == 0:
		number[a-1] = lnum
		number[b-1] = lnum
		frl.append([a,b])
		lnum += 1
	elif number[a-1] != 0 and number[b-1] != 0:
		if number[a-1] != number[b-1]:
			frl[number[a-1]-1].extend(frl[number[b-1]-1])
			frl[number[b-1]-1] = frl[number[a-1]-1].copy()
	elif number[a-1] != 0:
		frl[number[a-1]-1].append(b)
		number[b-1] = number[a-1]
	elif number[b-1] != 0:
		frl[number[b-1]-1].append(a)
		number[a-1] = number[b-1]
leng = []
for i in range(len(frl)):
	leng.append(len(frl[i]))
print(max(leng))

Submission status: Runtime Error

Solution code:
from collections import defaultdict
def generate_primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

def main():  
    n = int(input())
    A = list(map(int, input().split()))
    d = defaultdict(int)
    primes = generate_primes(max(A))
    for a in A:
        for p in primes:
            if a < p: break
            if a % p == 0:
                d[p] += 1
    d[1] = 0
    m = max(d.values())
    if m == n:
        print('not coprime')
    elif m >= 2:
        print('setwise coprime')
    else:
        print('pairwise coprime')
    

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
G = []
for _ in range(M):
    ver = list(map(int,input().split()))
    G.append(ver)

Ans = [G[0]]

for i in range(M):
    test = False
    for k in range(len(Ans)):
        a = Ans[k]
        b = G[i]
        if set(a).isdisjoint(set(b)):
            test = True
        else:
            Ans[k].append(G[i][0])
            Ans[k].append(G[i][1])
            break
    if test :
        Ans.append(G[i])

answer = 0
for i in range(len(Ans)):
    bn = Ans[i]
    an = len(set(bn))
    answer = max(answer, an)

print(answer)

Submission status: Runtime Error

Solution code:
import random
import sys

sys.setrecursionlimit(10000)

# n, m = map(int, input().split())
n, m = 200000, 200000
group = {i: 0 for i in range(1, n+1)}
edge = {}
g_mem = {}
g_num = 0
g_con = set()

for i in range(m):
    # a, b = map(int, input().split())
    a, b = random.sample(range(1,n+1), 2)
    if group[a]==0 and group[b] == 0:
        g_num += 1
        group[a] = g_num
        group[b] = g_num
        g_mem[g_num] = 2
    elif group[a] == 0:
        group[a] = group[b]
        g_mem[group[b]] += 1
    elif group[b] == 0:
        group[b] = group[a]
        g_mem[group[a]] += 1
    elif group[a] != group[b]:
        if edge.get(group[a]):
            edge[group[a]].add(group[b])
        else:
            edge[group[a]] = {group[b]}
        if edge.get(group[b]):
            edge[group[b]].add(group[a])
        else:
            edge[group[b]] = {group[a]}

# print(g_mem)
# print(sum(g_mem.values()))
# print(edge)

g_reached = {i: 0 for i in range(1, g_num+1)}

def dps(g_mem, edge, now):
    count = g_mem[now]
    if edge.get(now):
        for e in edge[now]:
            if g_reached[e] == 0:
                g_reached[e] = 1
                count += dps(g_mem, edge, e)
    return count


ans = []
for now in range(1, g_num+1):
    if g_reached[now] == 0:
        g_reached[now] = 1
        ans.append(dps(g_mem, edge, now))

# print(ans)
print(max(ans))

Submission status: Runtime Error

Solution code:
import sys

N, M = map(int, input().split())

sys.setrecursionlimit(M+N)

v_neighbor = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    v_neighbor[a-1].append(b-1)
    v_neighbor[b-1].append(a-1)


v_visit = [False for _ in range(N)]

def search(n):
    count = 0
    for n_ in set(v_neighbor[n]):
        if not v_visit[n_]:
            v_visit[n_] = True
            count += 1
            count += search(n_)
    return count

res = 1
for i in range(N):
    if v_visit[i]:
        continue
    search_res = search(i)
    res = max(res, search_res)


print(res)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

N, M = map(int, input().split())

D = defaultdict(set)
R = {}
for _ in range(M):
  a, b = map(int, input().split())
  if a in R:
    if b in R:
      aa, bb = R[a], R[b] 
      if aa == bb:
        pass
      else:
        if len(D[aa]) < len(D[bb]):
          aa, bb = bb, aa
        for x in D[bb]:
          R[x] = aa
        D[aa] |= D[bb]
        del D[bb]
    else:
      R[b] = R[a]
      D[R[a]].add(b)
  else:
    if b in R:
      R[a] = R[b]
      D[R[b]].add(a)
    else:
      R[a] = a
      R[b] = a
      D[a].add(a)
      D[a].add(b)

print(max(len(x) for x in D.values()))

Submission status: Runtime Error

Solution code:
def solve():
    N, M = [int(i) for i in input().split()]
    R = []
    for _ in range(M):
        A, B = [int(i) for i in input().split()]
        f = False
        if (len(R) > 0):
            for r in R:
                if A in r:
                    f = True
                    r.add(B)
                elif B in r:
                    f = True
                    r.add(A)
        if not f:
            R.append(set([A, B]))
    print(R)
    print(len(sorted(R, key=len)[-1]))


if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
import numpy as np

N, M = map(int,input().split())
Adj=np.identity(N)
for i in range(M):
    A, B=  map(int,input().split())
    Adj[A-1,B-1]=1
    Adj[B-1,A-1]=1

AD=np.dot(Adj, Adj)
count=0
for i in range(N):
    ans=np.count_nonzero(AD[i, :])
    if ans>count:
        count=ans
print(count)

Submission status: Runtime Error

Solution code:
n,m = map(int, input().split())
ls=[]
a,b = map(int, input().split())
tmp = {a, b}
ls.append(tmp)
for i in range(m-1):
  a,b = map(int, input().split())
  for s in ls:
    if (a in s) or (b in s):
      s.add(a)
      s.add(b)
      break
    else:
      tmp = {a,b}
      ls.append(tmp)

ans = 0
for s in ls:
  ans = max(ans, len(s))
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
import collections


class UnionFind2:
    def __init__(self, size):
        # 負の値はルート (集合の代表)
        # 正の値は次の要素を表す
        self.table = [-1 for _ in range(size)]

    # 集合の代表を求める
    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            # 経路の圧縮
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    # 併合
    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            self.table[s2] = s1
            return True
        return False


N, M = map(int, input().split())
uf = UnionFind2(N+1)

for i in range(M):
    A, B = map(int, input().split())
    uf.union(A, B)

hoge = [uf.find(i) for i in range(N+1)]

#print(hoge)
hogehoge = collections.Counter(hoge).most_common()

print(hogehoge[0][1])

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
info = []
count = 0
while count < M:
    A, B = map(int,input().split())
    info += [[A,B]]
    count += 1


friends = []
for k in range(1,N+1):
    for I in info:
        if I[0] == k and I[1] < k:
            flag = False
            for j in range(len(friends)):
                if I[1] in friends[j] and k not in friends[j]:
                    flag = True
                    friends[j] += [k]
            if flag == False:
                friends += [[I]]
        elif I[1] == k and I[0] < k:
            flag = False
            for j in range(len(friends)):
                if I[0] in friends[j] and k not in friends[j]:
                    flag = True
                    friends[j] += [k]
            if flag == False:
                friends += [I]

print(max(len(f) for f in friends))

Submission status: Runtime Error

Solution code:

def solve():
    n,m=map(int,input().split())

    fa=list(range(0,n+1))
    sz=[1]*(n+1)
    def gf(x) :
        if x==fa[x] :
            return x
        fa[x]=gf(fa[x])
        return fa[x]

    for i in range(m) :
        a,b=map(gf,map(int,input().split()))
        if a!=b :
            fa[a]=b
            sz[b]+=sz[a]

    ans=1
    for i in range(1,n+1) :
        ans=max(ans,sz[gf(i)])
    return ans

print(solve())

Submission status: Runtime Error

Solution code:
ininfo = input().split(" ")
num = int(ininfo[0])
m = int(ininfo[1])

list=[]
for i in range(m):
  list.append(input().split(" "))
  list[i].sort()

list.sort()
anslist=[]
s={list[0][0],list[0][1]}
anslist.append(s)
for i in list:
  for j in anslist:
    if i[0] in j or i[1] in j:
      j.add(i[0])
      j.add(i[1])
    else:
      s={i[0],i[1]}
      anslist.append(s)
      
ans=0
for i in anslist:
  if len(i)>ans:
    ans=len(i)

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import connected_components
import collections

def main():
    N, M = map(int, input().split())
    ab = []
    for i in range(M):
        ab.append(list(map(int,input().split())))

    l = np.zeros((N, N), dtype = np.int64)

    for i in range(M):
        l[ab[i][0]-1,ab[i][1]-1] = 1
        #[ab[i][1]-1][ab[i][0]-1] = 1

    a = np.array(l)
    n, labels = connected_components(a)

    print(collections.Counter(labels).most_common()[0][1])
    
if __name__ == "__main__":
    main()