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:
from collections import Counter

class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
            
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            

N, M = map(int, input().split())
UF = UnionFind(N)
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    big = max(a, b)
    small = min(a, b)
    
    if UF.par[big] == big:
        UF.par[big] = small
    else:
        UF.union(big, small)

for i in range(N):
    UF.find(i)
    
c = Counter(UF.par)

if len(c.values()) == 1:
    print(n)
else:
    print(max(c.values()))

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=Adj**2
print(max(np.count_nonzero(AD, 0)))

Submission status: Runtime Error

Solution code:
from collections import defaultdict


def main():
    n, m = map(int, input().split())
    friend_group = defaultdict(set)
    for _ in range(m):
        a, b = map(int, input().split())
        friend_group[a].add(b)
        friend_group[b].add(a)
        friends = friend_group[a] | friend_group[b]
        for friend in friends:
            friend_group[friend] |= friends
    print(max([len(friend_group[key]) for key in friend_group]))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import Counter
def resolve():
    N, connections = map(int, input().split())
    
    connection_set = set([tuple(map(int, input().split())) for _ in range(connections)])
    group_list = [0]*N
    group_num = 1
    for connection in connection_set:
        x0 = connection[0]-1
        x1 = connection[1]-1
        if group_list[x0] != 0:
            if group_list[x1] == 0:
                group_list[x1] = group_list[x0]
        else:
            if group_list[x1] == 0:
                group_list[x0] = group_num
                group_list[x1] = group_num
                group_num += 1
            else:
                group_list[x0] = group_list[x1]
 
    c = Counter(group_list)
    d = c.most_common()
 
    if d[0][0] == 0:
        print(d[1][1])
    else:
        print(d[0][1]) 
resolve()

Submission status: Runtime Error

Solution code:
n, m = (int(x) for x in input().split())
l = []
l2 = []
for i in range(m):
  a ,b =(int(x) for x in input().split())
  f = False
  f2 = False
  for j in range(len(l)):
    if a in l[j]:
      f = True
      for k in range(len(l) - j):
        if b in l[j + k]:
          f2 = True
          if k != 0:
            l[j] += l[j + k]
            del l[j + k]
      if f2 == False:
        l[j].append(b)
    if b in l[j]:
      f = True
      for k in range(len(l) - j):
        if a in l[j + k]:
          f2 = True
          if k != 0:
            l[j] += l[j + k]
            del l[j + k]
      if f2 == False:
        l[j].append(a)
  if f == False:
    l.append([a, b])

max = 0
for i in range(len(l)):
  if len(l[i]) > max:
    max = len(l[i])
print(max)

Submission status: Runtime Error

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

    person_group = [0] * (N+5)
    group_counter = 0
    member_counter = {0: 0}

    def _marge_group(a, b):
        for i in range(len(person_group)):
            if person_group[i] == b:
                person_group[i] == a
        member_counter[a] += member_counter.pop(b)

    for _ in range(M):
        A, B = map(int, input().split())
        if person_group[A] == 0 and person_group[B] == 0:
            group_counter += 1
            person_group[A] = group_counter
            person_group[B] = group_counter
            member_counter[group_counter] = 2
        elif person_group[A] != 0 and person_group[B] == 0:
            person_group[B] = person_group[A]
            member_counter[person_group[A]] += 1
        elif person_group[A] == 0 and person_group[B] != 0:
            person_group[A] = person_group[B]
            member_counter[person_group[B]] += 1
        else:
            if person_group[A] == person_group[B]:
                continue
            else:
                _marge_group(person_group[A], person_group[B])
    print(max(member_counter.values()))

if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
ab = sorted(set([tuple(map(int, input().split())) for _ in range(m)]))

c = []
flag = False
for i in ab:
    a, b = i[0], i[1]
    for i in c:
        if a in i or b in i:
            i.add(a)
            i.add(b)
            if len(i) == n:
                flag = True
            break
        else:
            c.append(set())
            c[-1].add(a)
            c[-1].add(b)
    if flag:
        break
if m == 0:
    print(1)
else:
    print(max(map(len, c)))

Submission status: Runtime Error

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


friends=[1]
num=1
people=[-1]*n
ans=0

for f in F:
    a=f[0]-1
    b=f[1]-1
    #print(a,b)

    if people[a]==-1 and people[b]==-1:
        friends.append(2)
        people[a]=num
        people[b]=num
        num+=1

    elif people[a]!=-1 and people[b]!=-1 and people[a]!=people[b]:
        A=people[a]
        B=people[b]
        friends[A] = friends[A]+friends[B]
        for i in friends[B]:
            people[i]=A

    elif people[a]!=-1 and people[b]==-1:
        friends[people[a]]+=1
        people[b]=people[a]

    elif people[a]==-1 and people[b]!=-1:
        friends[people[b]]+=1
        people[a]=people[b]

for i in friends:
    if i>ans:
        ans=i
print(ans)

Submission status: Runtime Error

Solution code:
mport numpy as np
def dot_py(A,B):
    m, n = A.shape
    p = B.shape[1]

    C = np.zeros((m,p))

    for i in range(0,m):
        for j in range(0,p):
            for k in range(0,n):
                C[i,j] += A[i,k]*B[k,j] 
    return C

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
print(max(np.count_nonzero(Adj, 0)))

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 = []
    num_check = {}
    numnum = {}
    set_num = 1
    for i in range(m):
        check=True
        a,b = map(int, input().split())
        if a in num_check.keys() and a in num_check.keys():
            pass
        elif a in num_check.keys():
            num_check[b] = num_check[a]
            numnum[num_check[a]] += 1
        elif a in num_check.keys():
            num_check[a] = num_check[b]
            numnum[num_check[b]] += 1
        else:
            num_check[a] = set_num
            num_check[b] = set_num
            numnum[set_num] = 2
            set_num += 1


    
        # 
        # 
        # 
        # 
        # for i, friends_set in enumerate(friends_list):
        #     if a in friends_set:
        #         friends_list[i].add(b)
        #         check = False
        #         break
        #     if b in friends_set:
        #         friends_list[i].add(a)
        #         check = False
        #         break
        # if check:
        #     friends_list.append({a, b})
    # group_num = len(friends_list)
    # max = 0
    # for friends_set in friends_list:
    #     length = len(friends_set)
    #     if length > max:
    #         max = length
    print(max(numnum.values()))
    

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
group = [1]*N
tmp = 0
for i in range(M):
    if AB[i][0] > AB[i][1]:
        tmp = AB[i][0]
        AB[i][0] = AB[i][1]
        AB[i][1] = tmp
AB.sort()
before0 = AB[0][0]
before1 = AB[0][1]
for i in range(M):
    if i != 0:
        if before0 == AB[i][0] and before1 == AB[i][1]:
            before0 = AB[i][0]
            before1 = AB[i][1]
            continue
        group[AB[i][0]-1] += 1
        group[AB[i][1]-1] += 1
        before0 = AB[i][0]
        before1 = AB[i][1]
    else:
        group[AB[i][0]-1] += 1
        group[AB[i][1]-1] += 1
print(max(group))

Submission status: Runtime Error

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

    person_group = [0] * (N+1)
    group_counter = 0
    member_counter = {0: 0}

    def _marge_group(a, b):
        for i in range(len(person_group)):
            if person_group[i] == b:
                person_group[i] == a
        member_counter[a] += member_counter.pop(b)

    for _ in range(M):
        A, B = map(int, input().split())
        if person_group[A] == 0 and person_group[B] == 0:
            group_counter += 1
            person_group[A] = group_counter
            person_group[B] = group_counter
            member_counter[group_counter] = 2
        elif person_group[A] != 0 and person_group[B] == 0:
            person_group[B] = person_group[A]
            member_counter[person_group[A]] += 1
        elif person_group[A] == 0 and person_group[B] != 0:
            person_group[A] = person_group[B]
            member_counter[person_group[B]] += 1
        else:
            if person_group[A] == person_group[B]:
                continue
            else:
                _marge_group(person_group[A], person_group[B])
    print(max(member_counter.values()))

if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
A=[]
B=[]
for i in range(m):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)

Flist=[]
for i in range(m):
    flag = False
    for F in Flist:
        if A[i] in F:
            flag = True
            for G in Flist:
                if (G != F) and (B[i] in G):
                    for g in G:
                        F.append(g)
            if not B[i] in F:
                F.append(B[i])
        elif B[i] in F:
            flag = True
            for  G in Flist:
                if (G != F) and (A[i] in G):
                    for g in G:
                        F.append(g)
            if not A[i] in F:
                F.append(A[i])
    if flag == False:
            f = [A[i],B[i]]
            Flist.append(f)
lenlist=[]
for F in Flist:
    lenlist.append(len(F))

print(max(lenlist))

Submission status: Runtime Error

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

p = [list(map(int,input().split())) for i in range(m)]

def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]


newp = get_unique_list(p)

def flatten_2d(data):
    for block in data:
        for elem in block:
            yield elem

newnewp = flatten_2d(newp)

onusi = statistics.mode(newnewp)
ai = newnewp.count(onusi)

print(ai + 1)

Submission status: Runtime Error

Solution code:
N, M = [int(a) for a in input().split()]
lol = []
for i in range(M):
  a, b = [int(a) for a in input().split()]
  found_a = -10
  found_b = -10
  for j in range(len(lol)):
    if a in lol[j]:
      found_a = j
    if b in lol[j]:
      found_b = j
    if found_a >= 0 and found_b >= 0:
      break
  
  if found_a < 0 and found_b < 0:
    lol.append([a,b])
  elif found_a >= 0 and found_b < 0:
    lol[found_a].append(b)
  elif found_b >= 0 and found_a < 0:
    lol[found_b].append(a)
  elif found_a >= 0 and found_b >=0 and found_a != found_b:
    lol[found_a] += lol[found_b]
    lol.pop(found_b)
    
ans = max([len(z) for z in lol])

print(ans)

Submission status: Runtime Error

Solution code:
N, M  = map(int, input().split())
S = []
for i in range(M):
    S.append(set(input().split()))
# print(S)
groups = [S[0]]

for j in range(1,len(S)-1):
    for k in range(len(groups)):
        if S[j] & groups[k] != set():
            groups[k] = S[j] | group
        else:
            groups.append(S[j])
lens = []
for group in groups:
    lens.append(len(group))
print(max(lens))

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 type(frl[number[a-1]-1]) == int:
		number[a-1] = frl[number[a-1]-1]
	if type(frl[number[b-1]-1]) == int:
		number[b-1] = frl[number[b-1]-1]
	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] = number[a-1]
	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:
# -*- coding: utf-8 -*-
N, M=map(int,input().split(' '))
A=[list(map(int,input().split(' '))) for _ in range(M)]

friends = []
for a in A:
  l=[]
  for i in range(len(friends)):
    if a[0] in friends[i] or a[1] in friends[i]:
      friends[i].extend(a)
      l.append(i)
  
  if len(l) == 0:
    friends.append(a)
  elif len(l) > 1:
    s = l[0]
    for j in range(len(l),1,-1):
      friends[s].extend(friends[l[j]])
      del friends[l[j]]
      
ans = 0
for f in friends:
  fset = set(f)
  ans = max(ans, len(fset))

print(ans)

Submission status: Runtime Error

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

l = []
A = 0
B = 0
ans = 1
if M > 0:
    A, B = map(int, input().split())
    l.append([A, B])
for i in range(M-1):
    A, B = map(int, input().split())
    hit = None
    for tup in l:
        if A in tup or B in tup:
            if hit != None:
                hit = set(hit+tup+[A, B])
            else:
                hit = set(tup+[A, B])
            l.remove(tup)
    if hit != None:
        l.append(hit)
    else:
        l.append((A, B))

if len(l) > 0:
    ans = 1
for item in (l):
    if ans < len(item):
        ans = len(item)
print(ans)

Submission status: Runtime Error

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

dic = dict((i, set()) for i in range(1,N+1))

try:
    for _ in range(M):
        a,b = map(int, input().split()) 
        dic[a].add(b)
except:
    pass


def dfs(x:int, marked:set):

    a = dic[x]
    marked.add(x)
    for i in dic[x]:
        if i not in marked:
            b, marked = dfs(i, marked)
            a = a.union(b)
    return a, marked

res = 0
marked = set()
for i in range(1,N+1):
    if i not in marked:
        a, addmark = dfs(i, set())
        marked = marked.union(addmark)
        #print(a,marked)
        if len(a) > res:
            res = len(a)
print(res)

Submission status: Runtime Error

Solution code:
def solve():
    N, M = [int(i) for i in input().split()]
    F = [-1] * N
    d = {}
    for m in range(M):
        A, B = [int(i) for i in input().split()]
        if F[A - 1] == -1 and F[B - 1] == -1:
            F[A - 1] = m
            F[B - 1] = m
            d[m] = [A, B]
        elif F[A - 1] == -1 and F[B - 1] != -1:
            F[A - 1] = F[B - 1]
            d[F[B - 1]].append(A)
        elif F[A - 1] != -1 and F[B - 1] == -1:
            F[B - 1] = F[A - 1]
            d[F[A - 1]].append(B)
        else:
            d[m] = [A, B]
            for i in range(len(F)):
                if F[i] == F[A - 1] or F[i] == F[B - 1]:
                    F[i] = m
                    d[m].append(i)
            F[A - 1] = m
            F[B - 1] = m
        if len(set(F)) == 1:
            print(len(F))
            exit()
    print(len(max(d.values(), key=len)))

if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
import queue
import sys

imput = sys.stdin.readline
n, m = map(int,input().split())

conne = [[0]*n for _ in range(n)]
visited = [0]*n

for i in range(m):
    a,b=map(int,input().split())
    conne[a-1][b-1]=1
    conne[b-1][a-1]=1

ans=0
for i in range(n):
    
    d=1
    count=0
    if visited[i]==0:
        visited[i]=1
        q=queue.Queue()
        q.put((i,d))
        count+=1
        
        while not q.empty():
            x,d = q.get()
            
            for j in range(n):
                if visited[j]==0 and conne[x][j]==1:
#                    print(i,j)
                    visited[j]=1
                    count+=1
                    q.put((j,d+1))
                    
                    
    ans = max(count,ans)
    
print(ans)

Submission status: Runtime Error

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


friends=[1]
num=1
people=[-1]*n
ans=0

for f in F:
    a=f[0]-1
    b=f[1]-1
    #print(a,b)

    if people[a]==-1 and people[b]==-1:
        friends.append(2)
        people[a]=num
        people[b]=num
        num+=1

    elif people[a]!=-1 and people[b]!=-1 and people[a]!=people[b]:
        A=people[a]
        B=people[b]
        friends[A] = friends[A]+friends[B]
        for i in friends[B]:
            people[i]=A

    elif people[a]!=-1 and people[b]==-1:
        friends[people[a]]+=1
        people[b]=people[a]

    elif people[a]==-1 and people[b]!=-1:
        friends[people[b]]+=1
        people[a]=people[b]

    print(people)
    print(friends)

for i in friends:
    if i>ans:
        ans=i
print(ans)

Submission status: Runtime Error

Solution code:
def dfs(g, start):
    visited[start] = True
    cc.append(0)
    for nbr in g[start]:
        if not visited[nbr]:
            dfs(g, nbr)



from collections import defaultdict
n, m = map(int, input().split())
g = defaultdict(set)

for _ in range(m):
    a, b = map(int, input().split())
    g[a - 1].add(b - 1)
    g[b - 1].add(a - 1)


visited = [False]*n
ans = 0
for i in range(n):
    if not visited[i]:
        cc = []
        dfs(g, i)
        ans = max(ans, len(cc))

print(ans)

Submission status: Runtime Error

Solution code:
import collections
import copy

class Num:
    def __init__(self, conum):
        self.conum = CoNum(conum)

class CoNum:
    def __init__(self, num):
        self.num = num

N, M = map(int, input().split())
friend_group = [Num(0) for i in range(N+1)]

for _ in range(M):
    a, b = map(int, input().split())
    tmp = max(friend_group[a].conum.num, friend_group[b].conum.num)
    if tmp == 0:
        tmp = a

    friend_group[a].conum.num = tmp
    friend_group[b].conum.num = tmp
    friend_group[b] = copy.copy(friend_group[a])

tmp_friend_group = []
for i in range(N+1):
    tmp_friend_group.append(friend_group[i].conum.num)

col = collections.Counter(tmp_friend_group)
sorted_rank = sorted(col.values(), reverse=True)
r1 = sorted_rank[0]
r2 = sorted_rank[1]

if col.get(0) == r1:
    print(r2)
else:
    print(r1)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

def main():
    N, M = map(int, input().split())
    groups = []
    for _ in range(M):
        a, b = map(int, input().split())
        if len(groups) == 0:
            groups.append({a, b})
        else:
            flag = True
            for g in groups:
                if a in g:
                    g.add(b)
                    flag = False
                if b in g:
                    g.add(a)
                    flag = False
            if flag:
                groups.append({a, b})
        ans = 0
        for g in groups:
            ans = max(ans, len(g))

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
A=[]
B=[]
for i in range(m):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)

Flist=[]
for i in range(m):
    flag = False
    for F in Flist:
        if A[i] in F:
            flag = True
            for G in Flist:
                if (G != F) and (B[i] in G):
                    for g in G:
                        print(str(g)+"is moved")
                        F.append(g)
            if not B[i] in F:
                F.append(B[i])
        elif B[i] in F:
            flag = True
            for  G in Flist:
                if (G != F) and (A[i] in G):
                    for g in G:
                        F.append(g)
            if not A[i] in F:
                F.append(A[i])
    if flag == False:
            f = [A[i],B[i]]
            Flist.append(f)
lenlist=[]
for F in Flist:
    lenlist.append(len(F))

print(max(lenlist))

Submission status: Runtime Error

Solution code:
#import sys
#sys.setrecursionlimit(99999999)


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

tomodachi=[[]for i in range(n)]

for i in range(m):
    tomodachi[friends[i][0]-1].append(friends[i][1]-1)
    tomodachi[friends[i][1]-1].append(friends[i][0]-1)

for i in range(n):
    tomodachi[i]=list(set(tomodachi[i]))

namelist=[1 for i in range(n)]
teams=[]

def haba(x,kari,tomodachi,namelist):
    for i in range(len(tomodachi[x])):
        if namelist[tomodachi[x][i]]==1:#生き残っているなら
            kari.append(tomodachi[x][i])
            namelist[tomodachi[x][i]]=0#殺す
            haba(tomodachi[x][i],kari,tomodachi,namelist)
    return(kari)
            


for i in range(n):
    if namelist[i]==1:
        teams.append(list(set(haba(i,[i],tomodachi,namelist))))

saidai=0

for i in range(len(teams)):
    if saidai<len(teams[i]):
        saidai=len(teams[i])

ans=saidai

print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
l = {k: k for k in range(1, n+1)}
g = {k: set() for k in range(1, n+1)}

for _ in range(m):
  a, b = map(int, input().split()) 
  g[a].add(b)
  g[b].add(a)

def get_group(curr_group, x):
  if g.get(x):
    group = set(curr_group) | {x}
    for i in g[x] - curr_group:
      group |= get_group(group, i)
    del g[x]
    return group
  return curr_group

ans = 0
for i in range(1, n + 1):
  if g.get(i):
    group = get_group(set(), i)
    ans = max(ans, len(group))

    
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import copy


N, M = map(int, input().split())
rinsetu = np.zeros((N, N))


def explore(i, through, ungropued):
    through += [i]
    ungrouped.remove(i)
    candidates = copy.deepcopy(ungrouped)
    for j in candidates:
        if j not in through and rinsetu[i, j] == 1:
            through = explore(j, through, ungrouped)
    return through


def friendize(a, b, rinsetu):
    rinsetu[a, b] = 1
    rinsetu[b, a] = 1
    return rinsetu


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

ungrouped = list(range(N))
group_list = []
while len(ungrouped) != 0:
    group_list.append(explore(ungrouped[0], [], ungrouped))
print(max(map(len, group_list)))

Submission status: Runtime Error

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

l=[-1]*N

getIDmem={}
def getID(l,idx):
  orig=idx
  if(getIDmem.get(idx)!=None):idx=getIDmem[idx]
  while True:
    if idx==l[idx]:break
    idx=l[idx]
  getIDmem[orig]=idx
  return idx

d={}
for i in range(M):
  s=list(map(int,input().split()))
  a,b=s[0]-1,s[1]-1
  s[0]-=1
  s[1]-=1
  if l[a]==-1 and l[b]==-1:
    l[a]=a
    l[b]=b
    d[a]=2
  elif l[a]==-1 or l[b]==-1:
    for j in range(2):
      if l[s[j]]==-1:
        id=getID(l,s[(j+1)%2])
        l[s[j]]=id
        d[id]+=1
  else:
    r1=getID(l,a)
    r2=getID(l,b)
    if r1==r2:continue
    l[r1]=r2
    d[r2]+=d[r1]
    d[r1]=0
ans=1

for i in d:
  ans=max(ans,d[i])
print(ans)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
F=[1]*N
G=[0]*N
for i in range(M):
  A,B=map(int,input().split())
  if G[A-1]!=0 and G[B-1]==0:
    f=F[A-1]+F[B-1]
    F[A-1]=f
    F[B-1]=f
    G[B-1]=G[A-1]
    print(f,G[A-1],G[B-1])
  elif  G[A-1]==0 and G[B-1]!=0:
    f=F[A-1]+F[B-1]
    F[A-1]=f
    F[B-1]=f
    G[A-1]=G[B-1]
    print(f,G[A-1],G[B-1])
  elif G[A-1]!=G[B-1]:
    f=F[A-1]+F[B-1]
    F[A-1]=f
    F[B-1]=f
    a=G[A-1]
    b=G[B-1]
    for j in range(M):
      if G[j]==b:
        G[j]=a
    print(f,G[A-1],G[B-1])
  elif G[A-1]==0 and G[B-1]==0:
    f=F[A-1]+F[B-1]
    F[A-1]=f
    F[B-1]=f
    G[A-1]=i+1
    G[B-1]=i+1
    print(f,G[A-1],G[B-1])
  else:
    print(0)
print(max(F))

Submission status: Runtime Error

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

def main():
    import bisect, collections, copy, heapq, itertools, math, string
    import sys
    def I():
        return int(sys.stdin.readline().rstrip())

    def MI():
        return map(int, sys.stdin.readline().rstrip().split())

    def LI():
        return list(map(int, sys.stdin.readline().rstrip().split()))

    def S():
        return sys.stdin.readline().rstrip()

    def LS():
        return list(sys.stdin.readline().rstrip().split())

    def main():
        from collections import deque
        N, M = MI()
        fri_list = []
        num_list = [0] * (N + 1)
        for i in range(M):
            a, b = MI()
            if num_list[a] == 0 and num_list[b] == 0:
                fri_list.append([a, b])
            elif num_list[a] == 0 or num_list[b] == 0:
                for l in fri_list:
                    if a in l:
                        l.append(b)
                    elif b in l:
                        l.append(a)
            else:
                continue
            num_list[a] = num_list[b] = 1

        len_list = []
        for l in fri_list:
            x = len(l)
            len_list.append(x)
        ans = max(len_list)
        print(ans)

    if __name__ == "__main__":
        main()




if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def dfs(g, start):
    visited[start] = True
    cc.append(0)
    for nbr in g[start]:
        if not visited[nbr]:
            dfs(g, nbr)



import sys
from collections import defaultdict
input = sys.stdin.readline
n, m = map(int, input().split())
g = defaultdict(set)

for _ in range(m):
    a, b = map(int, input().split())
    g[a - 1].add(b - 1)
    g[b - 1].add(a - 1)


visited = [False]*n
ans = 0
for i in range(n):
    if not visited[i]:
        cc = []
        dfs(g, i)
        ans = max(ans, len(cc))

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import copy
N,M=map(int,input().split())
mat=np.zeros((N,N))
for _ in range(M):
    a,b=map(int,input().split())
    mat[a-1][b-1]=1
    mat[b-1][a-1]=1
mat2=copy.deepcopy(mat)
for i in range(N):
    for j in range(i+1,N):
        for k in range(j+1,N):
            if (mat[i][j]==1)&(mat[i][k]==1):
                mat2[j][k]=1
                mat2[k][j]=1
print(str(int(np.max(np.sum(mat2,axis=1))+1)))

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

if M == 0:
    print(1)
    exit()

adj_list = defaultdict(set)

for i in range(M):
    a, b = map(int, input().split())
    adj_list[a].add(b)
    adj_list[b].add(a)

visited = set([])
def dfs(target):
    global visited
    if target in visited:
        return 0
    visited.add(target)
    node_count = 1

    for neighbor in adj_list[target]:
        node_count += dfs(neighbor)
    return node_count
count = 1

for node in range(1, N+1):
    if node not in visited:
        count = max(dfs(node), count)
print(count)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
group = [1]*N
for i in range(M):
    if AB[i][0] > AB[i][1]:
        tmp = AB[i][0]
        AB[i][0] = AB[i][1]
        AB[i][1] = tmp
AB.sort()
before0 = AB[0][0]
before1 = AB[0][1]
for i in range(M):
    if i != 0:
        if before0 == AB[i][0] and before1 == AB[i][1]:
            before0 = AB[i][0]
            before1 = AB[i][1]
            continue
        group[AB[i][0]-1] += 1
        group[AB[i][1]-1] += 1
        before0 = AB[i][0]
        before1 = AB[i][1]
print(max(group))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
# Union-Find
a=list(range(n))
def find(x):
  if a[x]==x:
    return x
  a[x] = find(a[x])
  return a[x]

def union(x,y):
  x, y = find(x), find(y)
  if x == y: return
  a[min(x,y)] = max(x,y)

for _ in range(m):
  x,y=map(lambda x:int(x)-1,input().split())
  union(x, y)

count=[0]*n
for i in range(n):
  count[find(i)] += 1
print(max(count))

Submission status: Runtime Error

Solution code:
def make_group(checked, a, friends):
  group = []
  if checked[a]:
    return group
  group.append(a)
  checked[a] = True
  for b in friends[a]:
    group += make_group(checked, b, friends)
  return group
  
n, m = map(int, input().split())
friends = {}
checked = {}
for i in range(1, n+1):
  friends[i] = set()
  checked[i] = False
for i in range(m):
  a, b = map(int, input().split())
  friends[a].add(b)
  friends[b].add(a)
for i in range(1, n+1):
  friends[i] = sorted(list(friends[i]))
minimum = -float('inf')
for i in range(1, n+1):
  group = make_group(checked, i, friends)
  if group:
    minimum = max(minimum, len(group))
print(minimum)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
L = []
N2 = [[0]*N for i in range(N)]
ans = 0
for _ in range(M):
  A, B = map(int, input().split())
  N2[A-1][B-1] = 1; N2[B-1][A-1] =1
for i in range(N):
  ans = max(ans, sum(N2[i])+1)
print(ans)