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 = map(int, input().split())
A = [0] * M
B = [0] * M
for i in range(M):
    A[i], B[i] = map(int, input().split())

class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        self.par = [-1 for i in range(n + 1)]
        # 木の高さを格納する（初期状態では0）
        """self.rank = [0] * (n + 1)"""

    # 検索
    # 根ならその番号を返す
    def find(self, x):
        if self.par[x] < 0:
            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 x != y:
            if self.par[x] < self.par[y]:  # par<0の小さい方に合わせる
                self.par[y] += self.par[x]
                self.par[x] = y
            else:
                self.par[x] += self.par[y]
                self.par[y] = x
                # 木の高さが同じなら片方を1増やす
                """if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1"""

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.par[self.find(x)]
    
    
u = UnionFind(N)
for i in range(M):
    u.union(A[i], B[i])
    
ans = 1
for i in range(1, N+1):
    ans = max(ans, u.size(i))
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = [0] * M
B = [0] * M
for i in range(M):
    A[i], B[i] = map(int, input().split())

class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        self.par = [-1 for i in range(n + 1)]
        # 木の高さを格納する（初期状態では0）
        """self.rank = [0] * (n + 1)"""

    # 検索
    # 根ならその番号を返す
    def find(self, x):
        if self.par[x] < 0:
            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 x != y:
            if self.par[x] < self.par[y]:  # par<0の小さい方に合わせる
                self.par[y] += self.par[x]
                self.par[x] = y
            else:
                self.par[x] += self.par[y]
                self.par[y] = x
                # 木の高さが同じなら片方を1増やす
                """if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1"""

    def size(self, x):
        return -self.par[self.find(x)]
    
    
u = UnionFind(N)
for i in range(M):
    u.union(A[i], B[i])
    
ans = 1
for i in range(1, N+1):
    print("{}の属するグループは{}人です。".format(i, u.size(i)))
    ans = max(ans, u.size(i))
print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
root=[-1]*n
def r(x):　#-1の項が何番目かを特定
  if root[x]<0: #x番目が-1ならx(>=0)を返す
    return x 
  else: #x番目が0以上なら-1の項に到達するまで回す
    root[x]=r(root[x]) 
    return root[x] #-1の項に到達したらその項が何番目かを返す
def unite(x,y):
  x=r(x)
  y=r(y)
  if x==y: #同じ項に到達した場合は処理の必要なし
    return
  root[x]+=root[y] #-1ずつ加算していく
  root[y]=x #-1を足した後は適当な数に変える(重複回避)
for i in range(m):
  a,b=map(int,input().split())
  a-=1 #リストの序数に合わせる
  b-=1
  unite(a,b) #各人間がどのくらい友達がいるか
ans=0
for i in range(n):
  ans=max(ans,-root[i]) #最多保有友人数が何人か
print(ans)

Submission status: Runtime Error

Solution code:
# Python template 
from collections import defaultdict 
import sys
import math 

def get_array(): return list(map(int , sys.stdin.readline().strip().split()))
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def input(): return sys.stdin.readline().strip()


g = defaultdict(set)
(n,m) = get_ints()
visited = [0]*n 


def dfs(i,l,par):
    global visited
    visited[i] = True
    l.append(i)
    for j in g[i]:
        if j!=par and not visited[j]:
            dfs(j,l,i)

for i in range(m):
    (u,v) = get_ints()
    g[u-1].add(v-1)
    g[v-1].add(u-1)

ans = 0
for i in range(n):
    if not visited[i]:
        l = []
        dfs(i,l,-1)
        ans = max(ans,len(l))
        
print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
grid = [set() for i in range(n)]
for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    grid[u].add(v)
    grid[v].add(u)

cnt = 0
best = 0
visited = set()


def dfs(x):
    global cnt
    if x in visited:
        return
    cnt += 1
    visited.add(x)
    for i in grid[x]:
        dfs(i)


for i in range(n):
    cnt = 0
    dfs(i)
    best = max(best, cnt)

print(best)

Submission status: Runtime Error

Solution code:
from collections import deque
 
N,M = map(int,input().split())
hint_list = [list(map(int,input().split())) for i in range(M)]

r = [-1] * N

def find(a):
    if r[a] < 0:
        return a
    else:
        if r[r[a]] < 0:
            return r[a]
        else:
            r[a] =r[r[a]]
            return r[a]
    
def union(a,b):
    a -= 1
    b -= 1
    ar = find(a)
    br = find(b)
    if ar == br:
        return
    else:
        if r[ar] > r[br]:
            ar,br = br,ar
        r[ar] += r[br]
        r[br] = ar
        return
        
for i in range(len(hint_list)):
    union(hint_list[i][0],hint_list[i][1])
    
print(-min(r))

Submission status: Runtime Error

Solution code:
from collections import deque
 
N,M = map(int,input().split())
hint_list = [list(map(int,input().split())) for i in range(M)]

r = [-1] * N

def find(a):
    if r[a] < 0:
        return a
    else:
        if r[r[a]] < 0:
            return r[a]
        else:
            r[a] =r[r[a]]
            return r[a]
    
def union(a,b):
    a -= 1
    b -= 1
    ar = find(a)
    br = find(b)
    if ar == br:
        return
    else:
        if r[ar] > r[br]:
            ar,br = br,ar
        r[ar] += r[br]
        r[br] = ar
        return
        
for i in range(len(hint_list)):
    union(hint_list[i][0],hint_list[i][1])
    print(r)
    
print(-min(r))

Submission status: Runtime Error

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

#AB = [tuple(map(int, input().split())) for i in range(M)]
#丸暗記。隣接リストの初期化
graph = [[i+1] for i in range(M)]

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

ans = -1
for g in graph:
  ans = max(ans, len(set(g)))
print(ans)

Submission status: Runtime Error

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

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

counted = [False]*N
def grouping(i): # return list of friends of i
	i_friends = friends[i]
	ret = [i]
	for f in i_friends:
		if counted[f]:
			continue
		counted[f] = True
		ret += grouping(f)
	return ret

group_list = []
for i in range(N):
	if counted[i]:
		continue
	counted[i] = True
	group_list.append(grouping(i))

gsize = [len(g) for g in group_list]
print(max(gsize))

Submission status: Runtime Error

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

N,M = map(int,input().split())
dic = {}
sets = {0}
for _ in range(M):
  a,b = map(int,input().split())
  if a in sets or b in sets:
    if a in sets and b in sets:
      tmp_a = 0
      tmp_b = 1
      # つなげる処理
      for key in dic.keys():
        if a in dic[key]:
          tmp_a = key
        if b in dic[key]:
          tmp_b = key
      if tmp_a != tmp_b:
        dic[tmp_a].union(dic[tmp_b])
        del dic[tmp_b]
      else:
        dic[tmp_a].add(a)
        dic[tmp_a].add(b)
    else:
      # 入っている方に追加する処理
      for vls in dic.values():
        if a in vls or b in vls:
          vls.add(a)
          vls.add(b)
  else:
    dic[_] = {a,b}
  sets.add(a)
  sets.add(b)

mx = 0

for vals in dic.values():
  mx = max(mx,len(vals))
print(mx)

Submission status: Runtime Error

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

N,M = map(int,input().split())
dic = {}
sets = {0}
for _ in range(M):
  a,b = map(int,input().split())
  if a in sets or b in sets:
    if a and b in sets:
      tmp_a = 0
      tmp_b = 1
      # つなげる処理
      for key in dic.keys():
        if a in dic[key]:
          tmp_a = key
        elif b in dic[key]:
          tmp_b = key
      if tmp_a != tmp_b:
        dic[tmp_a].union(dic[tmp_b])
        del dic[tmp_b]
      else:
        dic[tmp_a].add(a)
        dic[tmp_a].add(b)
    else:
      # 入っている方に追加する処理
      for vls in dic.values():
        if a in vls or b in vls:
          vls.add(a)
          vls.add(b)
  else:
    dic[_] = {a,b}
  sets.add(a)
  sets.add(b)

mx = 0

for vals in dic.values():
  mx = max(mx,len(vals))
print(mx)

Submission status: Runtime Error

Solution code:
# union-find

import collections

n, m = list(map(int, input().split()))

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

par = [i for i in range(n+1)]

for i in list:
    par[i[0]] = i[1]

def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x]) #経路圧縮
        return par[x]
      
for i in range(len(par)):
    find(i)

c = collections.Counter(par)

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

Submission status: Runtime Error

Solution code:
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

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

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


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

answer = 0
for i in range(N):
    answer = max(answer, union_find.size(i))

print(answer)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

class Union_Find:
    def __init__(self, n):
        self.root = [-1]*n
    
    def find(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return root[x]

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

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


n, m = map(int, input().split())
uf = Union_Find(n)

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

ans = 0
for i in range(n):
    size = uf.root[i]*(-1)
    ans = max(ans, size)

print(ans)

Submission status: Runtime Error

Solution code:
def zero_origin(s: str):
  return int(s) - 1


class UnionFindTree:
  """Union Find Tree for disjoint-set data structure.

  Args:
    n (int): number of the vertices.
  """
  def __init__(self, n: int):
    self.parent = list(range(n))
    self.rank = [0] * n
    self.size = [1] * n

  def find(self, i: int) -> int:
    if self.parent[i] != i:
      self.parent[i] = self.find(self.parent[i])
    return self.parent[i]

  def unite(self, i: int, j: int):
    ri = self.find(i)
    rj = self.find(j)
    size = self.size[ri] + self.size[rj]
    self.size[ri] = size
    self.size[rj] = size
    if ri != rj:
      if self.rank[ri] < self.rank[rj]:
        self.parent[ri] = rj
      else:
        self.parent[rj] = ri
        if self.rank[ri] == self.rank[rj]:
          self.rank[ri] += 1

  def is_same(self, i: int, j: int) -> bool:
    return self.find(i) == self.find(j)


n, m = map(int, input().split())
uft = UnionFindTree(n)
for _ in range(m):
  a, b = map(zero_origin, input().split())
  uft.unite(a, b)
print(max(utf.size))

Submission status: Runtime Error

Solution code:
lass UnionFind:
  def __init__(self, n):
    self.parent = [-1] * n
    self.rank = [1] * n
    self.count = [1] * n

  def get_root(self, i):
    if self.parent[i] == i:
      return i
    else:
      self.parent[i] = self.get_root(self.parent[i])
      return self.parent[i]
    #while self.parent[i] != -1:
    #  i = self.parent[i]
    #return i

  def is_same_tree(self, i, j):
    return self.get_root(i) == self.get_root(j)

  def merge(self, i, j):
    i = self.get_root(i)
    j = self.get_root(j)
    if i == j:
      return

    if self.rank[i] > self.rank[j]:
      self.parent[j] = i
      self.rank[i] = max(self.rank[i], self.rank[j] + 1)
      self.count[i] += self.count[j]
    else:
      self.parent[i] = j
      self.rank[j] = max(self.rank[j], self.rank[i] + 1)
      self.count[j] += self.count[i]


n, m = map(int, input().split())
uf = UnionFind(n)
for _ in range(m):
  a, b = [int(i) - 1 for i in input().split()]
  uf.merge(a, b)
print(max(uf.count))

Submission status: Runtime Error

Solution code:
# 接続最大クラスタのサイズが答え？

N, M = [int(x) for x in input().split(' ')]

# from collections import defaultdict
# d = defaultdict(set)

# for i in range(M):
#     a, b = [int(x) for x in input().split(' ')]
#     d[a].add(b)
#     d[b].add(a)

class UF:
    def __init__(self):
        self.r = [-1] * N

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

    def union(self, i, j):
        ri = self.root(i)
        rj = self.root(j)
        if ri == rj:
            return
        else:
            if not self.r[ri] < self.r[rj]:
                ri, rj = rj, ri
            self.r[ri] += self.r[rj]
            self.r[rj] = ri
            return

    def max_size(self):
        return -min(self.r)

uf = UF()
for i in range(M):
    uf.union(*[int(x) for x in input().split(' ')])
print(uf.max_size())

Submission status: Runtime Error

Solution code:
class UnionFind(): 
        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)]


if __name__ == "__main__":
    N, M = map(int, input().split()) 
    union_find = UnionFind(N)
    for _ in range(M):
        A, B = map(int, input().split())
        A -= 1
        B -= 1
        union_find.union(A, B)

    answer = 0
    for i in range(N):
        answer = max(answer, union_find.size(i))

    print(answer)

Submission status: Runtime Error

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


class UnionFind:
    def __init__(self, n):
        self.__par = list(range(n))
        self.__siz = [1]*len(self.__par)

    def root(self, ix):
        if self.__par[ix] == ix:
            return ix
        return self.root(self.__par[ix])

    def unite(self, ix, iy):
        rx = self.root(ix)
        ry = self.root(iy)
        if rx == ry:
            return
        self.__siz[ry] += self.__siz[rx]
        self.__par[rx] = ry

    def isAkin(self, ix, iy):
        return self.root(ix) == self.root(iy)

    def size(self, ix):
        return self.__siz[self.root(ix)]


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

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

Submission status: Runtime Error

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


class UnionFind:
    def __init__(self, n):
        self.__par = list(range(n))
        self.__siz = [1]*len(self.__par)

    def root(self, ix):
        if self.__par[ix] == ix:
            return ix
        return self.root(self.__par[ix])

    def unite(self, ix, iy):
        rx = self.root(ix)
        ry = self.root(iy)
        if rx == ry:
            return
        self.__siz[ry] += self.__siz[rx]
        self.__par[rx] = ry

    def isAkin(self, ix, iy):
        return self.root(ix) == self.root(iy)

    def size(self, ix):
        return self.__siz[self.root(ix)]


uf = UnionFind(n)
for i in l:
    uf.unite(i[0]-1, i[1]-1)

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

Submission status: Runtime Error

Solution code:
import sys
from collections import Counter
input = lambda: sys.stdin.readline().rstrip('\r\n')

# Disjoint Set Union

class DSU(object):

    def __init__(self, n):
        self.parent = [-1] * n

    def find(self, key):
        if self.parent[key] == -1:
            return key
        return self.find(self.parent[key])

    def union(self, a, b):
        s1, s2 = self.find(a), self.find(b)
        if s2 != s1:
            self.parent[s2] = s1

    def show(self):
        print(self.parent[1:])

def solve():
    n, m = map(int, input().split())
    d = DSU(n + 1)
    if m:
        for _ in range(m):
           a, b = map(int, input().split())
           d.union(a, b)
        ans = []
        for i in range(1, n + 1):
            ans.append(d.find(i))
        mp = Counter(ans)
        print(max(mp.values()))
    else:
        print(1)
    

solve()

Submission status: Runtime Error

Solution code:
# 接続最大クラスタのサイズが答え？

N, M = [int(x) for x in input().split(' ')]

from collections import defaultdict
d = defaultdict(set)

for i in range(M):
    a, b = [int(x) for x in input().split(' ')]
    d[a].add(b)
    d[b].add(a)

def bfs(i, obs=set()):
    # set_obs = d[i] | {i}
    obs |= {i}
    for j in d[i]:
        if j not in obs:
            obs |= bfs(j, obs)
    return obs

print(max(len(bfs(i, set())) for i in range(1, N+1)))

Submission status: Runtime Error

Solution code:
from collections import deque

n, m = map(int, input().split())
l = [[] for i in range(n)]
union = []
vis = [-1]*n
ans = 0

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

q = deque()

def dfs(a):
    if vis[a] == -1:
        vis[a] = 0
        temp.append(a)
        for j in l[a]:
            q.append(j)
    if len(q) > 0:
        b = q.popleft()
        dfs(b)
    return temp

for i in range(n):
    temp = []
    union.append(dfs(i))

for i in union:
    ans = max(ans, len(i))

print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
N,M=map(int,input().strip().split())
l=list()
dp=[list() for _ in range(N)]
id=[-1 for _ in range(N)] #友人グループid 友人のいない者に-1をつける
for _ in range(M):
    a,b=map(int,input().strip().split())
    l.append((a,b))
    dp[a-1].append(b)
    dp[b-1].append(a)
    id[a-1]=0
    id[b-1]=0

i=1
c=[]
for n in range(1,N+1):
    cnt=0
    if id[n-1]==0:
        q=deque([n])
        cnt+=1
        while q:
            tmp=q.popleft()
            id[tmp-1]=i
            for e in dp[tmp-1]:
                if id[e-1]==0:
                    id[e-1]=i
                    q.append(e)
                    cnt+=1
                else:
                    continue
        i+=1
        c.append(cnt)
    else:
        continue
print(max(c))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

class Union_Find:
    def __init__(self, n):
        self.root = [-1]*n
    
    def find(self, x):
        if self.root[x] < -1:
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return root[x]

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

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


n, m = map(int, input().split())
uf = Union_Find(n)

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

ans = 0
for i in range(n):
    size = uf.root[i]*(-1)
    ans = max(ans, size)

print(ans)

Submission status: Runtime Error

Solution code:
class Union_Find:
    def __init__(self, n):
        self.root = [-1]*n
    
    def find(self, x):
        if self.root[x] < -1:
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return root[x]

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

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


n, m = map(int, input().split())
uf = Union_Find(n)

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

ans = 0
for i in range(n):
    size = uf.root[i]*(-1)
    ans = max(ans, size)

print(ans)

Submission status: Runtime Error

Solution code:
class UnionFind:
  def __init__(self, n):
    self.parent = list(range(n))
  def root(self, a):
    if self.parent[a] == a:
      return a
    else:
      self.parent[a] = self.root(self.parent[a])
      return self.parent[a]
  def unite(self, a, b):
    a, b = self.root(a), self.root(b)
    if a == b:
      return
    self.parent[a] = b

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)
minimum = 0
num = [0] * n
for i in range(n):
  root = uf.root(i)
  num[root] += 1
  minimum = max(minimum, num[root])
print(minimum)

Submission status: Runtime Error

Solution code:
import collections as col
from collections import defaultdict as dd

d=dd(list)

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

for _ in range(M):
    i,j=map(int, input().split())
    if i>j:
        i,j=j,i
    d[i].append(j)

for i in d:
    for j in d[i]:
        if p[j-1]!=-1:
            if p[i-1]==-1:
                p[i-1]=j
                cnt[p[j-1]]+=1
            continue
        if p[i-1]==-1:
            p[j-1]=i
            cnt[i]+=1
        else:
            p[j-1]=p[i-1]
            cnt[p[i-1]]+=1

cnt.sort(reverse=True)
print(cnt[0]+1)

Submission status: Runtime Error

Solution code:
import collections as col
from collections import defaultdict as dd

d=dd(list)

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

for _ in range(M):
    i,j=map(int, input().split())
    if i>j:
        i,j=j,i
    d[i].append(j)

for i in d:
    for j in d[i]:
        print(i,j)
        if p[j-1]!=-1:
            if p[i-1]==-1:
                p[i-1]=j
                cnt[p[j-1]]+=1
            continue
        if p[i-1]==-1:
            p[j-1]=i
            cnt[i]+=1
        else:
            p[j-1]=p[i-1]
            cnt[p[i-1]]+=1

cnt.sort(reverse=True)
print(cnt[0]+1)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)

def DFS(i):
    if done[i]:
        ans[-1]+=1
        done[i]=False
        for g in G[i]:
            if done[g]:
                DFS(g)
    else:
        return p

N,M=map(int,input().split())
G=[[] for _ in range(N)]
done=[True for _ in range(N)]

for i in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)
ans=[]
for j in range(N):
    ans.append(0)
    if done[j]:
        DFS(j)
print(max(ans))

Submission status: Runtime Error

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

root = [-1]*n

def find(x):
    if root[x] < 0:
        return x
    else:
        root[x] = find(root[x])
        return root[x]

def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 
    root[x] += root[y]
    root[y] = x

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

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

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

print(ans)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
f = []
for i in range(M):
    A,B = map(int,input().split())
    a = {A,B}
    for j in range(len(f)):
        if f[j] & a != set():
            f[j] = f[j] | a
            a = set()
    if a != set():
        f.append(a)
count = 1
while count > 0:
    count = 0
    for i in range(len(f)-1):
        for j in range(i+1,len(f)):
            if f[i] & f[j] != set():
                count += 1
                f[i] = f[i] | f[j]
                f.remove(f[j])
for i in range(len(f)):
    f[i] = len(f[i])
print(max(f))

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
f = []
for i in range(M):
    A,B = map(int,input().split())
    a = {A,B}
    for i in range(len(f)):
        if f[i] & a != set():
            f[i] = f[i] | a
            a = set()
    if a != set():
        f.append(a)
count = 1
while count > 0:
    count = 0
    for i in range(len(f)-1):
        for j in range(i+1,len(f)):
            if f[i] & f[j] != set():
                count += 1
                f[i] = f[i] | f[j]
                f.remove(f[j])
for i in range(len(f)):
    f[i] = len(f[i])
print(max(f))

Submission status: Runtime Error

Solution code:
class UnionFind:
  def __init__(self, n):
    self.parent = list(range(n))
  def root(self, a):
    if self.parent[a] == a:
      return a
    self.parent[a] = self.root(self.parent[a])
    return self.parent[a]
  def unite(self, a, b):
    if a > b:
      a, b = b, a
    a, b = self.root(a), self.root(b)
    if a == b:
      return
    self.parent[a] = b
  def same(self, a, b):
    return self.root(a) == self.root(b)
  def depth(self, a):
    root = self.root(a)
    return self.parent.count(root)

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)
minimum = -float('inf')
for i in range(n):
  minimum = max(minimum, uf.depth(i))
print(minimum)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)

n, m = map(int, input().split())
root = [-1] * n

def find_root(x):
    if root[x] < 0:
        return x
    else:
        root[x] == find_root(root[x])
        return root[x]

def unite(x, y):
    x = find_root(x)  
    y = find_root(y)
    if x == y:
        return
    root[x] += root[y]
    root[y] = x

def size(x):
    x = find_root(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:
n, m = map(int, input().split())
root = [-1] * n

def find_root(x):
    if root[x] < 0:
        return x
    else:
        root[x] == find_root(root[x])
        return root[x]

def unite(x, y):
    x = find_root(x)  
    y = find_root(y)
    if x == y:
        return
    root[x] += root[y]
    root[y] = x

def size(x):
    x = find_root(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:
N, M = map(int, input().split())
friends = {i: set() for i in range(N)}
for _ in range(M):
  A, B = sorted(list(map(int, input().split())))
  friends[A-1].add(B-1)

#print(friends)
ignore = set()
max = 0
def getAllFriends(il):
  res = set()
  for i in il:
    res |= friends[i]
  res |= getAllFriends(res)
  return res
for i, ff in friends.items():
  if i in ignore: continue
  fs = getAllFriends({i})
  ignore = ignore|fs
  if max<len(fs): max = len(fs)
print(max+1)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
friends = {i: set() for i in range(N)}
for _ in range(M):
  A, B = sorted(list(map(int, input().split())))
  friends[A-1].add(B-1)

#print(friends)
ignore = set()
max = 0
def getAllFriends(il):
  res = {friends[i] for i in il}
  res |= getAllFriends(res)
  return res
for i, ff in friends.items():
  if i in ignore: continue
  fs = getAllFriends({i})
  ignore = ignore|fs
  if max<len(fs): max = len(fs)
print(max+1)

Submission status: Runtime Error

Solution code:
n, m = list(map(int, input().rstrip().split(" ")))
friendships = []
l = 0
for mm in range(m):
  a, b = list(map(int, input().rstrip().split(" ")))
  i_a = -1
  i_b = -1
  j_a = -1
  j_b = -1
  for ll in range(l):
    if a in friendships[ll]:
      j_a = friendships[ll].index(a)
      i_a = ll
      break
  for ll in range(l):
    if b in friendships[ll]:
      j_b = friendships[ll].index(b)
      i_b = ll
      break
  if i_a != -1 and i_b != -1:
    if i_a != i_b:
      fb_ls = friendships[i_b]
      for fb in fb_ls:
        friendships[i_a].append(fb)
        del friendships[i_b]
        l -= 1
  elif i_a != -1:
    friendships[i_a].append(b)
  elif i_b != -1:
    friendships[i_b].append(a)
  else:
    l += 1
    friendships.append([a, b])
print(max([len(friendship) for friendship in friendships]))

Submission status: Runtime Error

Solution code:
class union_find:
    def __init__(self, node_num):
        self.root_array = [-1] * node_num

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

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.root_array[x] > self.root_array[y]:
            x, y = y, x
        self.root_array[x] += self.root_array[y]
        self.root_array[y] = x

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


def solve(n, m, ab_array):
    uf = union_find(n)
    for ab in ab_array:
        a, b = ab
        uf.unite(a - 1, b - 1)

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

    return ans

if __name__ == '__main__':
    n, m = map(int, input().split())
    ab_array = [list(map(int, input().split())) for _ in range(m)]
    ans = solve(n, m, ab_array)
    print(ans)