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:
def root(i):
  if par[i] == i:
    return i
  par[i] = root(par[i])
  return par[i]

def union(x, y):
  rx = root(x)
  ry = root(y)
  if rx != ry:
    par[ry] = rx

def same(x, y):
  return par[x] == par[y]

n,m = map(int, input().split(" "))
p = [0] + list(map(int, input().split(" ")))
a = [(list(map(int, input().split(" ")))) for i in range(m)]
par = list(range(n + 1))
count = 0
for i, j in a:
  union(i, j)
  #print(par)
#print(p)
for i in range(1, n):
  if same(root(par[p[i]]), root(par[i])):
    count += 1
print(count)

Submission status: Runtime Error

Solution code:
def root(i):
  if par[i] == i:
    return i
  par[i] = root(par[i])
  return par[i]

def union(x, y):
  rx = root(x)
  ry = root(y)
  if rx != ry:
    par[ry] = rx

def same(x, y):
  return par[x] == par[y]

n,m = map(int, input().split(" "))
p = [0] + list(map(int, input().split(" ")))
a = [(list(map(int, input().split(" ")))) for i in range(m)]
par = list(range(n + 1))
count = 0
for i, j in a:
  union(i, j)
  #print(par)
#print(p)
for i in range(1, n + 5):
  if same(root(par[p[i]]), root(par[i])):
    count += 1
print(count)

Submission status: Runtime Error

Solution code:
def root(x):
  if par[x] == x:
    return x
  par[x] = root(par[x])
  return 1

def union(x, y):
  rx = root(x)
  ry = root(y)
  if rx != ry:
    par[rx] = ry
  return 0
    
n, m=map(int, input().split(" "))
par = list(range(n + 1))
for i in range(m):
  a, b = map(int, input().split(" "))
  union(a, b)
#print(par)
maxi = 0
count = 1
#print(par)
countpar = [0 for i in range(n + 1)]
for i in range(1, n + 1):
  countpar[root(par[i])] += 1
print(max(countpar))

Submission status: Runtime Error

Solution code:
def root(x):
  if par[x] == x:
    return x
  par[x] = root(par[x])
  return par[x]

def union(x, y):
  rx = root(x)
  ry = root(y)
  if rx != ry:
    par[rx] = ry
  return 0
    
n, m=map(int, input().split(" "))
par = list(range(n + 1))
for i in range(m):
  a, b = map(int, input().split(" "))
  union(a, b)
#print(par)
maxi = 0
count = 1
#print(par)
countpar = [0 for i in range(n + 1)]
for i in range(1, n + 1):
  countpar[root(par[i])] += 1
print(max(countpar))

Submission status: Runtime Error

Solution code:
from networkx import *
print(max(*map(len,connected_components(Graph([*map(str.split,open(0))][1:]))),1))

Submission status: Runtime Error

Solution code:
from networkx import *
print(max(*map(len,connected_components(Graph([*map(str.split,open(0))][1:])))))

Submission status: Runtime Error

Solution code:
from networkx import *
print(max(*map(len,connected_components(Graph([*map(str,open(0))][1:])))))

Submission status: Runtime Error

Solution code:
from networkx import *
print(max(*map(len,connected_components(Graph([input().split()][1:])))))

Submission status: Runtime Error

Solution code:
def root(x):
  if par[x] == x:
    return x
  par[x] = root(par[x])
  return par[x]

def union(x, y):
  rx = root(x)
  ry = root(y)
  if rx != ry:
    par[rx] = ry
  return 0
    
def same(x,y):
  rx = root(x)
  ry = root(y)
  return rx == ry
    
n, m=map(int, input().split(" "))
par = list(range(n + 1))
for i in range(m):
  a, b = map(int, input().split(" "))
  union(a, b)
#print(par)
maxi = 0
count = 1
#print(par)
countpar = [0 for i in range(n + 1)]
for i in range(1, n + 1):
  countpar[root(par[i])] += 1
print(max(countpar))

Submission status: Runtime Error

Solution code:
def root(x):
  if par[x] == x:
    return x
  par[x] = root(par[x])
  return par[x]

def union(x, y):
  rx = root(x)
  ry = root(y)
  if rx != ry:
    par[rx] = ry
    
def same(x,y):
  rx = root(x)
  ry = root(y)
  return rx == ry
    
n, m=map(int, input().split(" "))
par = list(range(n + 1))
for i in range(m):
  a, b = map(int, input().split(" "))
  union(a, b)
#print(par)
maxi = 0
count = 1
#print(par)
countpar = [0 for i in range(n + 1)]
for i in range(1, n + 1):
  countpar[root(par[i])] += 1
print(max(countpar))

Submission status: Runtime Error

Solution code:
import collections

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

q = collections.deque()
visited = [0 for i in range(n)]

def dfs():
    while q:
        s = q.pop()
        for i in friend[s]:
            if visited[i] == 0:
                tmp += 1
                q.append(i)

ans = 0
for i in range(n):
    if visited[i] == 0:
        visited[i] = 1
        tmp = 1
        for j in friend[i]:
            if visited[j] == 0:
                visited[j] = 1
                tmp += 1
                q.append(j)
        dfs()
    ans = max(ans,tmp)

print(ans)

Submission status: Runtime Error

Solution code:
import sys

n, m = [int(a) for a in sys.stdin.readline().strip().split(" ")]


uf = [-1] * n


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


def merge(x, y):
    if(root(x) != root(y)):
        uf[x] += uf[root(y)]
        uf[root(y)] = x


for i in range(m):
    a, b = [int(a) - 1 for a in sys.stdin.readline().strip().split(" ")]
    merge(a, b)


ret = 0
for i in uf:
    if i < ret:
        ret = i
print(-ret)

Submission status: Runtime Error

Solution code:
import numpy as np
from collections import defaultdict
D = defaultdict(set)
N, M = map(int,input().split())
L = np.zeros((N,N))
for _ in range(M):
  a, b = map(int,input().split())
  D[a-1].add(b-1)
  D[b-1].add(a-1)

Q = []
ans = 0
for i in range(N):
  vstd = set()
  Q.append(i)
  while Q:
    a = Q.pop()
    vstd.add(a)
    for j in D[a]:
      if not j in vstd:
        Q.append(j)
  ans = max(ans,len(vstd))
print (ans)

Submission status: Runtime Error

Solution code:
import sys
from collections import Counter
input = sys.stdin.readline


N, M = map(int, input().split())
A_B = [list(map(int, input().split())) for _ in range(M)]


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(N+1)]
        self.rank = [0]*(N+1)
    #検索
    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
    def same_check(self, x, y):
        if self.find(x) == self.find(y):
            return "Yes"
        else:
            return "No"

friend = UnionFind(N)
for i in range(M):
    friend.union(A_B[i][0], A_B[i][1])
for i in range(1,N+1):
    friend.find(i)
#print(friend.par)
a = Counter(friend.par)
b = a.most_common()[0][1]
#print(a)
print(b)

Submission status: Runtime Error

Solution code:
def root(x):
  if par[x] == x:
    return x
  par[x] = root(par[x])
  return par[x]

def union(x, y):
  rx = root(x)
  ry = root(y)
  if rx != ry:
    par[rx] = ry
    
def same(x,y):
  rx = root(x)
  ry = root(y)
  if rx == ry:
    print("Yes")
  else:
    print("No")
    
n, m=map(int, input().split(" "))
par = list(range(n + 1))
for i in range(m):
  a, b = map(int, input().split(" "))
  union(a, b)
#print(par)
for i in range(n):
  par[i] = root(i)
maxi = 0
count = 1
par.sort()
#print(par)
for i in range(1, n + 1):
  if par[i] == par[i - 1]:
    count += 1
  else:
    maxi = max(maxi, count)
    count = 1
else:
  maxi = max(maxi, count)
print(maxi)

Submission status: Runtime Error

Solution code:

#スタック、キューを使う
from collections import deque

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

G = [ set() for row in range(N)]

for i in range(M):
    A,B = map(int,input().split())
    G[A-1].add(B-1)
    G[B-1].add(A-1)

for i in range(N):
    G[i] = set(G[i])

#1グループに所属する最大数
ans = 0

#友達グループの数
count = 0

#各頂点の状態を色で表す WHITE:未訪問 GRAY:訪問中 BLACK:訪問完了
color = ['WHITE' for i in range(N)]

#訪問途中の頂点を退避しておくスタック
S = deque()

#次の要素を取り出す
def next(u):    
    #G[u]に格納されているまだ未訪問のノードを返す
    for i in range(len(G[u])):
        if color[G[u][i]] == 'WHITE':
            return G[u][i]
    return -1

def dfs(u):
    #始点uをスタックに追加
    S.append(u)
    color[u] = 'GRAY'
    global count
    count += 1
    #dequeは空のとき偽を返す
    while S:
        u = S[-1]    #スタックの頂点をuに格納
        v = next(u)
        #uに未訪問の隣接ノードがある
        if v != -1:
            color[v] = 'GRAY'
            count += 1
            S.append(v)
        else:
            S.pop()
            color[u]='BLACK'

#未訪問のuを始点として深さ優先探索
for i in range(N):
    count = 0
    if color[i] == 'WHITE':
        dfs(i)
        if count >= ans:
            ans = count

print(ans)

Submission status: Runtime Error

Solution code:
"""D."""

import sys

#def input() -> str:  # noqa: A001
#    """Input."""
#    return sys.stdin.readline()[:-1]


class UnionFindTree:
    """Union-find."""

    def __init__(self, n: int) -> None:
        """Init."""
        self.n = n
        self.parent = [-1] * n

    def find_root(self, x: int) -> int:
        """Find root."""
        parent = self.parent[x]
        if parent < 0:
            return x
        return self.parent[self.find_root(parent)]

    def union(self, x: int, y: int) -> None:
        """Unite two trees."""
        x_root = self.find_root(x)
        y_root = self.find_root(y)

        if x_root == y_root:
            return

        if x_root > y_root:
            x_root, y_root = y_root, x_root

        self.parent[x_root] += self.parent[y_root]
        self.parent[y_root] = x_root

    def get_size(self, x: int) -> int:
        """Get size."""
        return self.parent[self.find_root(x)] * -1

    def is_same(self, x: int, y: int) -> bool:
        """Is same group."""
        return self.find_root(x) == self.find_root(y)


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

tree = UnionFindTree(n)

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

ans = 0

for i in range(n):
    ans = max(ans, tree.get_size(i))

print(ans)

Submission status: Runtime Error

Solution code:
"""D."""

import sys

#def input() -> str:  # noqa: A001
#    """Input."""
#    return sys.stdin.readline()[:-1]


class UnionFindTree:
    """Union-find."""

    def __init__(self, n: int) -> None:
        """Init."""
        self.n = n
        self.parent = [-1] * n

    def find_root(self, x: int) -> int:
        """Find root."""
        parent = self.parent[x]
        if parent < 0:
            return x
        return self.find_root(parent)

    def union(self, x: int, y: int) -> None:
        """Unite two trees."""
        x_root = self.find_root(x)
        y_root = self.find_root(y)

        if x_root == y_root:
            return

        if x_root > y_root:
            x_root, y_root = y_root, x_root

        self.parent[x_root] += self.parent[y_root]
        self.parent[y_root] = x_root

    def get_size(self, x: int) -> int:
        """Get size."""
        return self.parent[self.find_root(x)] * -1

    def is_same(self, x: int, y: int) -> bool:
        """Is same group."""
        return self.find_root(x) == self.find_root(y)


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

tree = UnionFindTree(n)

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

ans = 0

for i in range(n):
    ans = max(ans, tree.get_size(i))

print(ans)

Submission status: Runtime Error

Solution code:
"""D."""

import sys
from typing import List


def input() -> str:  # noqa: A001
    """Input."""
    return sys.stdin.readline()[:-1]


class UnionFindTree:
    """Union-find."""

    def __init__(self, n: int) -> None:
        """Init."""
        self.n = n
        self.parent = [-1] * n

    def find_root(self, x: int) -> int:
        """Find root."""
        parent = self.parent[x]
        if parent < 0:
            return x
        return self.find_root(parent)

    def union(self, x: int, y: int) -> None:
        """Unite two trees."""
        x_root = self.find_root(x)
        y_root = self.find_root(y)

        if x_root == y_root:
            return

        if x_root > y_root:
            x_root, y_root = y_root, x_root

        self.parent[x_root] += self.parent[y_root]
        self.parent[y_root] = x_root

    def get_size(self, x: int) -> int:
        """Get size."""
        return self.parent[self.find_root(x)] * -1

    def is_same(self, x: int, y: int) -> bool:
        """Is same group."""
        return self.find_root(x) == self.find_root(y)


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

tree = UnionFindTree(n)

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

ans = 0

for i in range(n):
    ans = max(ans, tree.get_size(i))

print(ans)

Submission status: Runtime Error

Solution code:
"""D."""

import sys
from typing import List


def input() -> str:  # noqa: A001
    """Input."""
    return sys.stdin.readline()[:-1]


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

groups: List[set] = []
for _ in range(m):
    a, b = map(int, input().split(' '))
    for g in groups:
        if a in g:
            g.add(b)
            break
        if b in g:
            g.add(a)
            break
    else:
        groups.append({a, b})
print(max([len(g) for g in groups]))

Submission status: Runtime Error

Solution code:
from copy import deepcopy

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

pairs = [0] * m
for i in range(m):
    pairs[i] = list(map(int, input().split()))


# N = 5
# pairs = [[1,2], [3,4], [5,1]]

print(pairs)

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

    def root(self, x):
        if self.r[x] < 0:
            return x
        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
        if self.r[x] > self.r[y]:
            x, y = y, x

        self.r[x] += self.r[y]
        self.r[y] = x
        return True

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

uf = UnionFind(N)
for pair in pairs:
    a = pair[0] - 1
    b = pair[1] - 1
    uf.unite(a, b)

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

print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

n, m = map(int, input().split())
friend_list = []
friend_list2 = []
for i in range(m):
  a, b = map(int, input().split())
  friend_list.append([a, b])
while friend_list:
  friend = friend_list.pop()
  if not friend_list2:
    friend_list2.append(friend)
  else:
    temp_list = friend_list2.copy()
    for i in temp_list:
      if friend[0] in i and friend[1] not in i:
        i.append(friend[1])
        break
      elif friend[1] in i and friend[0] not in i:
        i.append(friend[0])
        break
      elif friend[0] in i and friend[1] in i:
        break
      else:
        friend_list2.append(friend)

print(max(map(len, friend_list2)))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

n, m = map(int, input().split())
friend_list = []
friend_list2 = []
for i in range(m):
  a, b = map(int, input().split())
  friend_list.append([a, b])
while friend_list:
  friend = friend_list.pop()
  if not friend_list2:
    friend_list2.append(friend)
  else:
    temp_list = friend_list2.copy()
    for i in temp_list:
      if friend[0] in i:
        i.append(friend[1])
        break
      elif friend[1] in i:
        i.append(friend[0])
        break
      else:
        friend_list2.append(friend)
friend_list3 = []
for i in friend_list2:
  friend_list3.append(set(i))
friend_list2 = []
for i in friend_list3:
  friend_list2.append(len(i))
print(max(friend_list2))

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

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

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

    def most_depth_root(self):
        return -min(self.parents)


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

union_find = UnionFind(N)
for i in range(M):
    x, y = map(int, input().split())
    union_find.union(x, y)

print(union_find.most_depth_root())

Submission status: Runtime Error

Solution code:
input_line = input().split()
N = int(input_line[0])
M = int(input_line[1])

class UnionFind():
  def __init__(self,n):
    self.n = n
    self.parents = [-1]*n
    
  def find(self,x):
    if self.parents[x] < 0:
      return x
    else:
      self.parents[x] = self.find(self.parents[x])
      return self.parents[x]
  
  def union(self,x,y):
    x = self.find(x)
    y = self.find(y)
    
    if x == y:
      return
    
    if self.parents[x] > self.parents[y]:
      x,y = y,x
    
    self.parents[x] += self.parents[y]
    self.parents[y] = x
    
  def size(self,x):
    return -self.parents[self.find(x)]

  
union = UnionFind(N)

for i in range(M):
  date = input().split()
  per1 = int(date[0])
  per2 = int(date[1])
  
  union.union(per1,per2)


answer = 0
for i in range(N):
  if answer < union.size(i):
    answer = union.size(i)

print(answer)

Submission status: Runtime Error

Solution code:
input_line = input().split()
N = int(input_line[0])
M = int(input_line[1])
groups = []

for i in range(M):
  date = input().split()
  per1 = int(date[0])
  per2 = int(date[1])
  
  for j in range(len(groups)):
    if per1 in groups[j]:
      if not per2 in groups[j]:
        groups[j].append(per2)
      break
    
    elif per2 in groups[j]:
      groups[j].append(per1)
      break
  else:
    groups.append([per1,per2])

rank = []
for i in range(len(groups)):
  rank.append(len(groups[i]))

rank.sort(reverse = True)
print(rank[0])

Submission status: Runtime Error

Solution code:
from collections import defaultdict

N, M = map(int, input().split())
friend_info = [list(map(int, input().split())) for _ in range(M)]

relation_dict = {}
for person1, person2 in friend_info:
    add_flag = False
    for k, v in relation_dict.items():
        if((person1 in v) or (person2 in v)):
            relation_dict[k].add(person1)
            relation_dict[k].add(person2)
            add_flag = True
            break
    if(add_flag == False):
        new_key = str(len(relation_dict)+1)
        relation_dict[new_key] = {person1, person2}

max_group = max([len(relation) for relation in relation_dict.values()])

print(max_group)

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):
        self.n = n
        self.parents = [-1] * (n+1)

    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)]
    
u = UnionFind(N)
for i in range(M):
    u.union(A[i], B[i])
     
print(u.size(i))

Submission status: Runtime Error

Solution code:
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c${TYO>cuR480@qAH2g<Sknro9VRsPM>-Bp2oMbdN;6g4ub)FGU-bp-_x$|gq%wU6t>WT*wMOY0gzARgSm<PTl{O42M-acZ>GgR)gKaC@nKT&GwVX(kN~!u8ucZ|Y8b(B=Z50NhloinL<u!3pzz_z0QZz6)r3^d(FK|_Vvacc{$MMog(mIMk_qA%XFaU}f;tT}jkofYgQLTh@BDvrMPL85@DXWT*4|sdefE$V53*yuSSxFN(66Zu54;pEIj0Umt)k-X-adrW>{z!kgU_m32?B0nU8teJJ*Jbf$fUB%#Xa*evWbUMjfo0CYP1$BMPdnFcOFr$kY1JE0q&D4MM1o^;p2n+H;kN0%y<G_x??~H8ckBt`JBapy@RS2z&0Fv3lRmuIfi5g*;$zvl;E!eJz;4T<{4pQ(_Xsb%`n(^%9vv^Ycp5Is*%R6LGR8Cv{L_vO&*hgs(2dYZ{{h3n*31")))
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Submission status: Runtime Error

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

def dfs(node, edge, vis):
    if vis[node]:
        return 0
    vis[node] = True
    count = 1
    for b in edge[node]:
        if not vis[b]:
            count += dfs(b, edge, vis)
    return count

n, m = [int(i) for i in input().split(' ')]

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

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

vis = [False]*n

count = 0

for i in range(n):
    if not vis[i]:
        count = max(count, dfs(i, edge, vis))

print(count)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
ab = [set(map(int, input().split())) for _ in range(m)]
sets = [ab[0]]
for a, b in ab[1:]:
    for i in range(len(sets)):
        if a in sets[i] or b in sets[i]:
            sets[i].add(a)
            sets[i].add(b)
            break
        else:
            sets.append({a, b,})
ans = 0
for s in sets:
    ans = max(len(s), ans)

print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
ab = [set(map(int, input().split())) for _ in range(m)]
sets = []
sets.append(ab[0])
ans = 0
print(sets)
print(ans)

Submission status: Runtime Error

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

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

print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
ab = [set(map(int, input().split())) for _ in range(m)]
sets = [ab[0]]
print(ans)

Submission status: Runtime Error

Solution code:
import typing


class DSU:
    '''
    Implement (union by size) + (path compression)
    Reference:
    Zvi Galil and Giuseppe F. Italiano,
    Data structures and algorithms for disjoint set union problems
    '''

    def __init__(self, n: int = 0):
        self._n = n
        self.parent_or_size = [-1] * n

    def merge(self, a: int, b: int) -> int:
        assert 0 <= a < self._n
        assert 0 <= b < self._n

        x = self.leader(a)
        y = self.leader(b)

        if x == y:
            return x

        if -self.parent_or_size[x] < -self.parent_or_size[y]:
            x, y = y, x

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

        return x

    def same(self, a: int, b: int) -> bool:
        assert 0 <= a < self._n
        assert 0 <= b < self._n

        return self.leader(a) == self.leader(b)

    def leader(self, a: int) -> int:
        assert 0 <= a < self._n

        if self.parent_or_size[a] < 0:
            return a

        self.parent_or_size[a] = self.leader(self.parent_or_size[a])
        return self.parent_or_size[a]

    def size(self, a: int) -> int:
        assert 0 <= a < self._n

        return -self.parent_or_size[self.leader(a)]

    def groups(self) -> typing.List[typing.List[int]]:
        leader_buf = [self.leader(i) for i in range(self._n)]

        result = [[] for _ in range(self._n)]
        for i in range(self._n):
            result[leader_buf[i]].append(i)

        return list(filter(lambda r: r, result))

n, m = map(int, input().split())
 
uf = DSU(n)
 
for _ in range(m):
    a, b = map(int, input().split())
    uf.marge(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:
l=lambda:map(int, input().split())
n,m=l()
p=[-1]*n
p=[-1]*n
def root(x):
  if p[x]<0:return x
  return (x:=root(p[x]))
def union(x,y):
  x,y=root(x),root(y)
  if x==y: return
  p[x]+=p[y]
  p[y]=x
def same(x,y):
  return root(x)==root(y)
def size(x):
  return -p[r(x)]
for _ in range(m):
  a,b=l()
  union(a-1,b-1)
print(-min(p))

Submission status: Runtime Error

Solution code:
from collections import defaultdict

friend_dict = defaultdict(list)

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

for m in range(M):
  x, y = map(int, input().split())
  friend_dict[x].append(y)
  friend_dict[y].append(x)
  
max_num_group = max([len(set(v)) for v in friend_dict.values()])

print(max_num_group + 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

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

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

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

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

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N, M = map(int, input().split())
f_uf = UnionFind(self, N)
for _ in range(M):
  a, b = map(int, input().split())
  f_uf.union(a-1, b-1)
answer = 1
for i in range(N):
  answer = max(answer, f_uf.size(i))
print(answer)

Submission status: Runtime Error

Solution code:
mycode = r'''
# distutils: language=c++
# cython: language_level=3, boundscheck=False, wraparound=False, cdivision=True
ctypedef long long LL
from libc.stdio cimport scanf
from libc.vector cimport vector
ctypedef vector[LL] vec

cdef:
    LL N,M
    vec A

scanf("%lld %lld",N,M)
'''

import sys
import os
if sys.argv[-1] == 'ONLINE_JUDGE':  # コンパイル時
    with open('mycode.pyx', 'w') as f:
        f.write(mycode)
    os.system('cythonize -i -3 -b mycode.pyx')

import mycode

Submission status: Runtime Error

Solution code:
def solve(N, M, fridens):
    parents = {}
    groups = {}
    for A, B in friends:
        parents[B] = A
        if A not in groups:
            if A not in parents:
                groups[A] = [A]
            else:
                continue
        groups[A].append(B)

    ans = len(max(groups.values(), key=len))
    print(ans)


if __name__ == "__main__":
    N, M = map(int, input().split())
    friends = []
    for _ in range(M):
        AB = sorted([x - 1 for x in map(int, input().split())])
        if AB not in friends:
            friends.append(AB)
    solve(N, M, friends)

Submission status: Runtime Error

Solution code:
numbers = [int(i) for i in input().split()]
N, M = numbers[0], numbers[1]

AB = []
for m in range(M):
    numbers = [int(i) for i in input().split()]
    AB.append((numbers[0], numbers[1]))

F = []

for A, B in AB:
    new = True
    for i, f in enumerate(F):
        if A in f or B in f:
            F[i] = f | {A} | {B}
            new = False
            break

    if new:
        F.append({A, B})

print(max([len(f) for f in F]))

Submission status: Runtime Error

Solution code:
from sys import stdin
import collections
def ip(): return [int(i) for i in stdin.readline().split()]
def sp(): return [str(i) for i in stdin.readline().split()]

n,m = ip()
# d = collections.defaultdict(list)
d = {}
seen = set()
for i in range(m):
    x,y = ip()
    if (x,y) in seen or (y,x) in seen:
        continue
    # d[x].append(y)
    # d[y].append(x)
    if x not in d:
        d[x] = [y]
    else:
        d[x].append(y)
    if y not in d:
        d[y] = [x]
    else:
        d[y].append(x)
    seen.add((x,y))
    seen.add((y,x))

def dfs(k, i, d, visited):
    k += 1
    visited.add(i)
    if i not in d: return visited, k
    for j in d[i]:
        if j not in visited:
            visited, k = dfs(k, j, d, visited)
    return visited, k

visited = set()
ans = 0
for i in range(1, n+1):
    if i in visited: continue
    visited, k = dfs(0, i, d, visited)
    # print(f'{visited=} | {k=} | {ans=}')
    ans = max(ans, k)
print(ans)

Submission status: Runtime Error

Solution code:
from sys import stdin
import collections
def ip(): return [int(i) for i in stdin.readline().split()]
def sp(): return [str(i) for i in stdin.readline().split()]

n,m = ip()
d = collections.defaultdict(list)
seen = set()
for i in range(m):
    x,y = ip()
    if (x,y) in seen or (y,x) in seen:
        continue
    d[x].append(y)
    d[y].append(x)
    seen.add((x,y))
    seen.add((y,x))

def dfs(k, i, d, visited):
    k += 1
    visited.add(i)
    if i not in d: return visited, k
    for j in d[i]:
        if j not in visited:
            visited, k = dfs(k, j, d, visited)
    return visited, k

visited = set()
ans = 0
for i in range(1, n+1):
    if i in visited: continue
    visited, k = dfs(0, i, d, visited)
    # print(f'{visited=} | {k=} | {ans=}')
    ans = max(ans, k)
print(ans)

Submission status: Runtime Error

Solution code:
from sys import stdin
import collections
def ip(): return [int(i) for i in stdin.readline().split()]
def sp(): return [str(i) for i in stdin.readline().split()]

n,m = ip()
d = collections.defaultdict(list)
seen = set()
for i in range(m):
    x,y = ip()
    if (x,y) in seen or (y,x) in seen:
        continue
    d[x].append(y)
    d[y].append(x)
    seen.add((x,y))
    seen.add((y,x))

def dfs(k, i, d, visited):
    k += 1
    visited.add(i)
    for j in d[i]:
        if j not in visited:
            visited, k = dfs(k, j, d, visited)
    return visited, k

visited = set()
ans = 0
for i in range(1, n+1):
    if i in visited: continue
    if i in d: visited, k = dfs(0, i, d, visited)
    # print(f'{visited=} | {k=} | {ans=}')
    ans = max(ans, k)
print(ans)

Submission status: Runtime Error

Solution code:
from sys import stdin
import collections
def ip(): return [int(i) for i in stdin.readline().split()]
def sp(): return [str(i) for i in stdin.readline().split()]

n,m = ip()
d = collections.defaultdict(list)
seen = set()
for i in range(m):
    x,y = ip()
    if (x,y) in seen or (y,x) in seen:
        continue
    d[x].append(y)
    d[y].append(x)
    seen.add((x,y))
    seen.add((y,x))

def dfs(k, i, d, visited):
    k += 1
    visited.add(i)
    for j in d[i]:
        if j not in visited:
            visited, k = dfs(k, j, d, visited)
    return visited, k

visited = set()
ans = 0
for i in range(1, n+1):
    if i in visited: continue
    visited, k = dfs(0, i, d, visited)
    # print(f'{visited=} | {k=} | {ans=}')
    ans = max(ans, k)
print(ans)