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:
import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque, defaultdict
from fractions import gcd
from functools import reduce
from itertools import groupby, combinations
from heapq import heapify, heappush, heappop

sys.setrecursionlimit(20000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return list(map(lambda x: x + d, A))
def ldec(A, d=1): return list(map(lambda x: x - d, A))

N, M = nn()
T = nm(M)

for i in range(M):
    T[i][0] -= 1
    T[i][1] -= 1

dic = defaultdict(list)

for i in range(M):
    dic[T[i][0]].append(T[i][1])
    dic[T[i][1]].append(T[i][0])

def search(n):
    ret = 1
    memo[n] = 1

    for d in dic[n]:
        if memo[d] == 0:
            ret += search(d)

    return ret

memo = array1(N)

ans = 0
for i in range(N):
    if memo[i] == 1:
        continue

    tmp = search(i)
    if tmp > ans:
        ans = tmp

print(ans)

Submission status: Runtime Error

Solution code:
import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque, defaultdict
from fractions import gcd
from functools import reduce
from itertools import groupby, combinations
from heapq import heapify, heappush, heappop

sys.setrecursionlimit(10000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return list(map(lambda x: x + d, A))
def ldec(A, d=1): return list(map(lambda x: x - d, A))

N, M = nn()
T = nm(M)

for i in range(M):
    T[i][0] -= 1
    T[i][1] -= 1

dic = defaultdict(list)

for i in range(M):
    dic[T[i][0]].append(T[i][1])
    dic[T[i][1]].append(T[i][0])

def search(n):
    ret = 1
    memo[n] = 1

    for d in dic[n]:
        if memo[d] == 0:
            ret += search(d)

    return ret

memo = array1(N)

ans = 0
for i in range(N):
    if memo[i] == 1:
        continue

    tmp = search(i)
    if tmp > ans:
        ans = tmp

print(ans)

Submission status: Runtime Error

Solution code:
import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque, defaultdict
from fractions import gcd
from functools import reduce
from itertools import groupby, combinations
from heapq import heapify, heappush, heappop

 sys.setrecursionlimit(5000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return list(map(lambda x: x + d, A))
def ldec(A, d=1): return list(map(lambda x: x - d, A))

N, M = nn()
T = nm(M)

for i in range(M):
    T[i][0] -= 1
    T[i][1] -= 1

dic = defaultdict(list)

for i in range(M):
    dic[T[i][0]].append(T[i][1])
    dic[T[i][1]].append(T[i][0])

def search(n):
    ret = 1
    memo[n] = 1

    for d in dic[n]:
        if memo[d] == 0:
            ret += search(d)

    return ret

memo = array1(N)

ans = 0
for i in range(N):
    if memo[i] == 1:
        continue

    tmp = search(i)
    if tmp > ans:
        ans = tmp

print(ans)

Submission status: Runtime Error

Solution code:
import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque, defaultdict
from fractions import gcd
from functools import reduce
from itertools import groupby, combinations
from heapq import heapify, heappush, heappop

 sys.setrecursionlimit(10000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return list(map(lambda x: x + d, A))
def ldec(A, d=1): return list(map(lambda x: x - d, A))

N, M = nn()
T = nm(M)

for i in range(M):
    T[i][0] -= 1
    T[i][1] -= 1

dic = defaultdict(list)

for i in range(M):
    dic[T[i][0]].append(T[i][1])
    dic[T[i][1]].append(T[i][0])

def search(n):
    ret = 1
    memo[n] = 1

    for d in dic[n]:
        if memo[d] == 0:
            ret += search(d)

    return ret

memo = array1(N)

ans = 0
for i in range(N):
    if memo[i] == 1:
        continue

    tmp = search(i)
    if tmp > ans:
        ans = tmp

print(ans)

Submission status: Runtime Error

Solution code:
import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque, defaultdict
from fractions import gcd
from functools import reduce
from itertools import groupby, combinations
from heapq import heapify, heappush, heappop

# sys.setrecursionlimit(5000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return list(map(lambda x: x + d, A))
def ldec(A, d=1): return list(map(lambda x: x - d, A))

N, M = nn()
T = nm(M)

for i in range(M):
    T[i][0] -= 1
    T[i][1] -= 1

dic = defaultdict(list)

for i in range(M):
    dic[T[i][0]].append(T[i][1])
    dic[T[i][1]].append(T[i][0])

def search(n):
    ret = 1
    memo[n] = 1

    for d in dic[n]:
        #print(d)
        if memo[d] == 0:
            ret += search(d)

    return ret

#memo = array1(N)
memo = defaultdict(int)

ans = 0
for i in range(N):
    if memo[i] == 1:
        continue

    tmp = search(i)
    if tmp > ans:
        ans = tmp

print(ans)

Submission status: Runtime Error

Solution code:
import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque, defaultdict
from fractions import gcd
from functools import reduce
from itertools import groupby, combinations
from heapq import heapify, heappush, heappop

# sys.setrecursionlimit(5000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return list(map(lambda x: x + d, A))
def ldec(A, d=1): return list(map(lambda x: x - d, A))

N, M = nn()
T = nm(M)

for i in range(M):
    T[i][0] -= 1
    T[i][1] -= 1

dic = defaultdict(list)

for i in range(M):
    dic[T[i][0]].append(T[i][1])
    dic[T[i][1]].append(T[i][0])

def search(n):
    ret = 1
    memo[n] = 1

    for d in dic[n]:
        #print(d)
        if memo[d] == 0:
            ret += search(d)

    return ret

memo = array1(N)

ans = 0
for i in range(len(memo)):
    if memo[i] == 1:
        continue

    tmp = search(i)
    if tmp > ans:
        ans = tmp

print(ans)

Submission status: Runtime Error

Solution code:
import numpy

class UnionFind:
    def __init__(self, N):
        self.N = N

        # the parent of all node is itself
        # self.parent = list(range(N))
        self.parent = [-1] * N

    def root(self, i):
        if self.parent[i] < 0:
            return i

        r = self.root(self.parent[i])
        self.parent[i] = r
        return r

    def unite(self, i, j):
        # print('root {}, {} = '.format(i, j), end='')
        i = self.root(i)
        j = self.root(j)
        # print(i, j)

        if i == j:
            return

        self.parent[i] += self.parent[j]
        self.parent[j] = i
        # print(self.parent)

    def same(self, i, j):
        return self.root(i) == self.root(j)

    def size(self, i):
        return -self.parent[self.root(i)]

N, M = map(int, input().split())
R = numpy.array([[int(r) for r in input().split()] for _ in range(M)]) - 1

forest = UnionFind(N)
for p1, p2 in R:
    forest.unite(p1, p2)

s = [forest.size(i) for i in range(N)]
print(max(s))

Submission status: Runtime Error

Solution code:
import numpy

class UnionFind:
    def __init__(self, N):
        self.N = N

        # the parent of all node is itself
        # self.parent = list(range(N))
        self.parent = [-1] * N

    def root(self, i):
        if self.parent[i] < 0:
            return i
        else:
            r = self.root(self.parent[i])
            self.parent[i] = r
            return r

    def unite(self, i, j):
        # print('root {}, {} = '.format(i, j), end='')
        i = self.root(i)
        j = self.root(j)
        # print(i, j)

        if i >= 0 and  j >= 0 and  i == j:
            return 

        self.parent[i] += self.parent[j]
        self.parent[j] = i
        # print(self.parent)

    def same(self, i, j):
        return self.root(i) == self.root(j)

    def size(self, i):
        return -self.parent[self.root(i)]

N, M = map(int, input().split())
R = numpy.array([[int(r) for r in input().split()] for _ in range(M)]) - 1

forest = UnionFind(N)
for p1, p2 in R:
    forest.unite(p1, p2)

s = [forest.size(i) for i in range(N)]
print(max(s))

Submission status: Runtime Error

Solution code:
def root(x):
  if F[x] < 0:
    return x
  else:
    F[x] = root(F[x])
    return F[x]

def unite(x, y):
  rx = root(x)
  ry = root(y)
  if rx == ry:
    return
  if rx > ry:
    x, y = y, x
  F[x] += F[y]
  F[y] = x

N, M = map(int, input().split())
F = [-1] * N

for m in range(M):
  a, b = map(int, input().split())
  unite(a - 1, b - 1)
ans = 0
for f in F:
  ans = min(ans, f)
print(-ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
r = [i for i in range(N+1)]
n = [0 for i in range(N+1)]
buf = []

def root(x):
  if x==r[x]:
    return x
  else:
    r[x] = root(r[x])
    return r[x]

def unite(x, y):
  rx = root(x)
  ry = root(y)
  if rx != ry:
    r[ry] = rx

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

for x in range(1, N+1):
  if r[x] != x and r[r[x]] != r[x]:
    _ = root(x)
  
  
for x in r[1:]:
  n[x] += 1
    
ans = max(n[1:])

print(ans)

Submission status: Runtime Error

Solution code:
#D - Friends
N,M = map(int,input().split())
par = [i for i in range(N+1)]
rank = [1] * (N + 1)

def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x]) #経路圧縮
        return par[x]

def size(x):
    return par.count(find(x))

def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    if x > y:
        x,y = y,x
    par[y] = x
    if par[x] == par[y]:
        rank[x] += 1
#    par[x] = y

print(par)
print(rank)
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    unite(a,b)
    print(par)
    print(rank)
group_count = 0

group_count = max(rank)

# 出力
print(group_count)

Submission status: Runtime Error

Solution code:
import sys
from io import StringIO
import unittest

def resolve():
    N, M = map(int, input().split())
    l = []
    for _ in range(M):
        i,j = map(int, input().split())
        gi = find_group(l,i)
        if not gi:
            gi = {i}
            l.append(gi)
        gj = find_group(l, j)
        if not gj:
            gj={j}
            l.append(gj)
        l.remove(gi)
        # if gi!=gj:
        l.remove(gj)
        gi = gi|gj
        l.append(gi)
    max_size=0
    for s in l:
        max_size = max(max_size,len(s))
    print(max_size)


def find_group(l, i):
    for s in l:
        if i in s:
            return s
    return None

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 3
1 2
3 4
5 1"""
        output = """3"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """4 10
1 2
2 1
1 2
2 1
1 2
1 3
1 4
2 3
2 4
3 4"""
        output = """4"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """10 4
3 1
4 1
5 9
2 6"""
        output = """3"""
        self.assertIO(input, output)


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
import sys

N, M = map(int, input().split())
if M == 0:
  print(1)
  sys.exit()
  
check = [0]*N
friendlist = []
tmp = 1
for i in range(M):
  a, b = map(lambda x: int(x)-1, input().split())
  if check[a] + check[b] == 0:
    check[a] = tmp
    check[b] = tmp
    friendlist.append(set([a,b]))
    tmp += 1
  elif check[a] == 0:
    friendlist[check[b]-1].add(a)
    check[a] = tmp
  elif check[b] == 0:
    friendlist[check[a]-1].add(b)
    check[b] = tmp
  else:
    continue
tmpp = 0
for j in friendlist:
  if len(j) > tmpp:
    tmpp = len(j)
print(tmpp)

Submission status: Runtime Error

Solution code:
#D - Friends
N,M = map(int,input().split())
par = [i for i in range(N+1)]

def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x]) #経路圧縮
        return par[x]

def size(x):
    return par.count(find(x))

def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    if par[x] > par[y]:
        x,y = y,x
    #par[x] += par[y]
    par[y] = x
#    par[x] = y

print(par)
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    unite(a,b)
    print(par)

group_count = 0

for i in range(N):
    group_count = max(group_count,size(i))

# 出力
print(group_count)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
check = [0]*N
friendlist = []
tmp = 1
for i in range(M):
  a, b = map(lambda x: int(x)-1, input().split())
  if check[a] + check[b] == 0:
    check[a] = tmp
    check[b] = tmp
    friendlist.append(set([a,b]))
    tmp += 1
  elif check[a] == 0:
    friendlist[check[b]-1].add(a)
    check[a] = tmp
  elif check[b] == 0:
    friendlist[check[a]-1].add(b)
    check[b] = tmp
  else:
    continue
tmpp = 0
for j in friendlist:
  if len(j) > tmpp:
    tmpp = len(j)
print(tmpp)

Submission status: Runtime Error

Solution code:
class UnionFind:
  def __init__(self, N):
    self.r = [-1]*(N+1)
  
  def root(self, x):
    if self.r[x] < 0:
      return x
    else:
      self.r[x] = self.root(self.r[x])
      return self.r[x]
  
  def unite(self, x, y):
    x = self.root(x)
    y = self.root(y)
    if x == y:
      return False
    else:
      self.r[x] += self.r[y]
      self.r[y] = x
      return True
    
  def size(self, x):
    return -1*self.r[self.root(x)]
  
  def print(self):
    print(self.r)


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

UF = UnionFind(N)

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

ans = 0
for i in range(N):
  ans = max(ans, UF.size(i))

print(ans)

Submission status: Runtime Error

Solution code:
class unionfind():

    def __init__(self,n):
        #親番号<0なら根
        #根の場合、数値の絶対値が要素数
        self.par=[-1 for i in range(n)]
        
    def root(self,x):
        
        par=self.par
        if par[x]<0:
            return x
        else:
            self.root = self.root(par[x])
            return self.root
        
    def unite(self,x,y):
        #高いほうに低いほうをくっつける
        rx=self.root(x)
        ry=self.root(y)
        
        if rx==ry:
            return
        else:
            if self.par[rx]>self.par[ry]:
                rx,ry = ry,rx
                
            self.par[rx]+=self.par[ry]
            self.par[ry] = rx

            
    def same(self, x,y):
        return self.root(x) == self.root(y)
    
    def par_print(self):
        print(self.par)
        
    def count(self, x):
        return -self.root(x)
    
n,m = map(int,input().split())

friend = unionfind(n)

for i in range(m):
    a,b = map(int,input().split())
    friend.unite(a-1,b-1)
    # print(friend.par_print())
    
# print(friend.par_print())

ans = -min(friend.par)

print(ans)

Submission status: Runtime Error

Solution code:
class UnionFind:
  def __init__(self, N):
    self.r = [-1]*N
  
  def root(self, x):
    if self.r[x] < 0:
      return x
    else:
      self.r[x] = self.root(self.r[x])
      return self.r[x]
  
  def unite(self, x, y):
    x = self.root(x)
    y = self.root(y)
    if x == y:
      return False
    else:
      self.r[x] += self.r[y]
      self.r[y] = x
      return True
    
  def size(self, x):
    return -1*self.r[self.root(x)]
  
  def print(self):
    print(self.r)


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

UF = UnionFind(N)

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

ans = 0
for i in range(N):
  ans = max(ans, UF.size(i))

print(ans)

Submission status: Runtime Error

Solution code:
class unionfind():

    def __init__(self,n):
        self.par=[i for i in range(n)]
        
    def root(self,x):
        #自分自身の番号==parの番号なら根
        par=self.par
        if par[x]==x:
            return x
        else:
            self.root = self.root(par[x])
            return self.root
        
    def unite(self,x,y):
        #xにyをくっつける
        rx=self.root(x)
        ry=self.root(y)
        
        if rx==ry:
            return
        else:
            self.par[ry]=rx
            
    def same(self, x,y):
        return self.root(x) == self.root(y)
    
    def par_print(self):
        print(self.par)
    
n,m = map(int,input().split())

friend = unionfind(n)

for i in range(m):
    a,b = map(int,input().split())
    friend.unite(a-1,b-1)
    
# print(friend.par_print())

ans = max([friend.par.count(i) for i in range(n)])

print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict 

n,m = map(int, input().strip().split(" "))

adjList = defaultdict(list)

for i in range(m):
    a,b = map(int, input().strip().split(" "))
    a-=1
    b-=1
    if b not in adjList[a]:
        adjList[a].append(b)
        
    if a not in adjList[b]:
        adjList[b].append(a)
    
mca = 0
visited = [False]*n

def dfs(node, cml):
    if len(adjList[node])>0:
        for ngh in adjList[node]:
            if not visited[ngh]:
                visited[ngh] = True
                cml = dfs(ngh, cml+1)
    
    return cml

for i in range(n):
    if not visited[i]:
        visited[i] = True
        ca = dfs(i, 1)
        mca = max(mca, ca)

print(mca)

Submission status: Runtime Error

Solution code:
from collections import defaultdict 

n,m = map(int, input().strip().split(" "))

adjList = defaultdict(list)

for i in range(m):
    a,b = map(int, input().strip().split(" "))
    a-=1
    b-=1
    if b not in adjList[a]:
        adjList[a].append(b)
        
    if a not in adjList[b]:
        adjList[b].append(a)
    
mca = 0
visited = [False]*n

def dfs(node, cml):
    visited[node] = True
    
    if adjList[node]:
        for ngh in adjList[node]:
            if not visited[ngh]:
                cml = dfs(ngh, cml+1)
    
    return cml

for i in range(n):
    if not visited[i]:
        ca = dfs(i, 1)
        mca = max(mca, ca)

print(mca)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)
N,M = map(int,input().split())

root = [i for i in range(N)]

def r(x):
  if root[x] < 0:
    return x
  else:
    root[x] = r(root[x])
    return root[x]
  
def unite(x,y):
  x = r(x)
  y = r(y)
  if x == y:
    return
  root[x] += root[y]
  root[y] = x

def size(x):
  x = r(x)
  return -root[x]

for i in range(M):
  x,y = map(int,input().split())
  x -=1
  y-=1
  unite(x,y)

max_size = max(map(size,range(n)))
print(max_size)

Submission status: Runtime Error

Solution code:
class UnionFind():
  par = []
  sizes = []

  def __init__(self, N):
    self.par = [i for i in range(N)]
    self.sizes = [1 for _ in range(N)]

  def root(self, x: int)-> int:
    if (self.par[x] == x):
      return x
    return self.root(self.par[x])

  def unite(self, x: int, y: int):
    rootX = self.root(x)
    rootY = self.root(y)
    if rootX == rootY:
      return
    self.par[rootX] = rootY
    self.sizes[rootY] += self.sizes[rootX]

  def maxSize(self)-> int:
    return max(self.sizes)

def friends(N, As):
  uf = UnionFind(N)
  setAs = list(set(As))
  for val in setAs:
    uf.unite(val[0]-1, val[1]-1)
  return uf.maxSize()

if __name__ == "__main__":
  nm = list(map(int, input().split()))
  As =[tuple(map(int, input().split())) for _ in range(nm[1])]
  print(friends(nm[0], As))

Submission status: Runtime Error

Solution code:
class UnionFind():
  par = []
  sizes = []

  def __init__(self, N):
    self.par = [i for i in range(N)]
    self.sizes = [1 for _ in range(N)]

  def root(self, x: int)-> int:
    if (self.par[x] == x):
      return x
    return self.root(self.par[x])

  def unite(self, x: int, y: int):
    rootX = self.root(x)
    rootY = self.root(y)
    if rootX == rootY:
      return
    self.par[rootX] = rootY
    self.sizes[rootY] += self.sizes[rootX]

  def maxSize(self)-> int:
    return max(self.sizes)

def friends(N, As):
  uf = UnionFind(N)
  for val in As:
    uf.unite(val[0]-1, val[1]-1)
  return uf.maxSize()

if __name__ == "__main__":
  nm = list(map(int, input().split()))
  As =[list(map(int, input().split())) for _ in range(nm[1])]
  print(friends(nm[0], As))

Submission status: Runtime Error

Solution code:
from collections import defaultdict 

n,m = map(int, input().strip().split(" "))

adjList = defaultdict(list)

for i in range(m):
    a,b = map(int, input().strip().split(" "))
    if b not in adjList[a]:
        adjList[a].append(b)
        
    if a not in adjList[b]:
        adjList[b].append(a)
    
mca = 0
visited = [False]*(n+1)

def dfs(node, cml):
    visited[node] = True
    
    if adjList[node]:
        for ngh in adjList[node]:
            if not visited[ngh]:
                cml = dfs(ngh, cml+1)
    
    return cml

for i in range(n):
    if not visited[i+1]:
        ca = dfs(i+1, 1)
        mca = max(mca, ca)

print(mca)

Submission status: Runtime Error

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

    def root(self, x):
        if self.par[x] < 0:
            return x
        return self.root(self.par[x])

    def unite(self, x, y):
        if x > y:
            x, y = y, x
        rx = self.root(x)
        ry = self.root(y)
        if rx != ry:
            self.par[rx] += self.par[ry]
            self.par[ry] = rx

    def size(self, x):
        return -self.par[self.root(x)]

    def same(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        return rx == ry

    def return_par(self):
        return self.par

n, m = map(int, input().split())
uf = UnionFind(n)
for i in range(m):
    a, b = map(int, input().split())
    uf.unite(a-1, b-1)

ans = 0
for i in range(n):
    ans = max(ans, uf.size(i))
print(ans)

Submission status: Runtime Error

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

    def root(self, x):
        if self.par[x] < 0:
            return x
        return self.root(self.par[x])

    def unite(self, x, y):
        if x > y:
            x, y = y, x
        rx = self.root(x)
        ry = self.root(y)
        if rx != ry:
            self.par[rx] += self.par[ry]
            self.par[ry] = rx

    def size(self, x):
        return -self.par[self.root(x)]

    def same(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        return rx == ry

    def return_par(self):
        return self.par

n, m = map(int, input().split())
uf = UnionFind(n)
for i in m:
    a, b = map(int, input().split())
    uf.unite(a-1, b-1)

ans = 0
for i in range(n):
    ans = max(ans, uf.size(i))
print(ans)

Submission status: Runtime Error

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

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

    def root(self, x):
        if self.par[x] < 0:
            return x
        return self.root(self.par[x])

    def unite(self, x, y):
        if x > y:
            x, y = y, x
        rx = self.root(x)
        ry = self.root(y)
        if rx != ry:
            self.par[rx] += self.par[ry]
            self.par[ry] = rx

    def size(self, x):
        return -self.par[self.root(x)]

    def same(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        return rx == ry

    def return_par(self):
        return self.par

uf = UnionFind(n)
for a, b in ab:
    uf.unite(a-1, b-1)

ans = 0
for i in range(n):
    ans = max(ans, uf.size(i))
print(ans)

Submission status: Runtime Error

Solution code:
import collections 
#=input()
#=int(input())
n,m=map(int,input().split())
#=list(map(int,input().split()))
#=[list(map(int,input().split())) for _ in range()]

def rep(l, x, y):
    for i in range(n + 1):
        if l[i] == x:
            l[i] = y

l = [0] * (n + 1)
for i in range(1, m + 1):
    a,b = map(int,input().split())
    if (l[a] == 0) and (l[b] == 0):
        l[a] = i
        l[b] = i
    elif (l[a] != 0) and (l[b] == 0):
        l[b] = l[a]
    elif (l[a] == 0) and (l[b] != 0):
        l[a] = l[b]
    else:
        rep(l, l[b], l[a])

c = collections.Counter(l)
if c.most_common()[0][0] == 0:
    print(c.most_common()[1][1])
else:
    print(c.most_common()[0][1])

Submission status: Runtime Error

Solution code:
def dfs(visited, graph, node):
    if node not in visited:
        visited.append(node)
        for neighbour in graph[node]:
            dfs(visited, graph, neighbour)

def insert_adj_list(graph,f,t):

    if (t not in graph[f]):
        graph[f].append(t)

    if (f not in graph[t]):
        graph[t].append(f)

def init_dict(dict,n):
    for i in range(1,n+1):
        dict[i]=[]

def rem_item(graph, n):
    if n in graph:
        del graph[n]

def gen_dict(p,n):
    dict={}
    for i in range(0,n):
        dict[p[i]]=i

    return dict

t=1
# t= int(input())

for some_num in range(0,t):
    n,m=[int(i) for i in input().split(" ")]
    graph={}
    init_dict(graph, n)
    for j in range(0,m):
        f, t = [int(i) for i in input().split(" ")]
        insert_adj_list(graph,f,t)

    p = [int(i) for i in range(1,n+1)]

    vc=[0 for i in range(0,n)]
    count=0
    dsets=[]
    for i in range(0,n):
        if(vc[i]==0):
            count+=1
            visited=[]
            dfs(visited,graph,p[i])
            # print(visited)
            for k in visited:
                vc[k-1]=1
            dsets.append(visited)
        else:
            pass
    max_len=0
    for i in range(0,len(dsets)):
        max_len=max(max_len,len(dsets[i]))

    print(max_len)