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: Accepted

Solution code:
import sys
def input():
	return sys.stdin.buffer.readline()[:-1]

class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]
		self.size = [1 for _ in range(size)]

	def find(self, x):
		while self.table[x] >= 0:
			if self.table[self.table[x]] >= 0:
				self.table[x] = self.table[self.table[x]]
			x = self.table[x]
		return x

	def unite(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 != s2:
			if self.table[s1] > self.table[s2]:
				self.table[s2] = s1
				self.table[s1] -= 1
				self.size[s1] += self.size[s2]
				self.size[s2] = 0
			else:
				self.table[s1] = s2
				self.table[s2] -= 1
				self.size[s2] += self.size[s1]
				self.size[s1] = 0
		return

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)

print(max(uf.size))

Submission status: Accepted

Solution code:
class UnionFindVerSize():
    def __init__(self, N):
        self._parent = [n for n in range(0, N)]
        self._size = [1] * N

    def find_root(self, x):
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x])
        return self._parent[x]

    def unite(self, x, y):
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans

import sys

input=sys.stdin.readline


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

ans=-1
for i in range(N):
    ans=max(ans,uf.get_size(i))

print(ans)

Submission status: Accepted

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

class UnionFind:
    def __init__(self, N):
        self.parent = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def find(self, x):
        r = x
        while self.parent[r] != r:
            r = self.parent[r]
        while self.parent[x] != r:
            x, self.parent[x] = self.parent[x], r
        return r

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
            self.size[y] += self.size[x]
        else:
            self.parent[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

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

N, M = map(int, input().split())
uf = UnionFind(N+1)
for _ in range(M):
    A, B = map(int, input().split())
    uf.unite(A, B)
ans = max(uf.get_size(i) for i in range(N+1))
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().strip()



n, m = na()

upper = [-1] * n
def root(x):
    if upper[x] < 0:
        return x
    else:
        upper[x] = root(upper[x])
        return upper[x]

def equiv(x, y):
    return root(x) == root(y)

def unite(x, y):
    x, y = root(x), root(y)
    if x != y:
        if upper[y] < upper[x]:
            x, y = y, x
        upper[x] += upper[y]
        upper[y] = x
    return x == y

for i in range(m):
    a, b = na()
    unite(a-1, b-1)

print(-min(upper))

Submission status: Accepted

Solution code:
class UnionFind:
    #def   -> foo=UnionFind(n,1)  <- 1-based index, default is 0
    #method -> foo.hoge(huga)
    __slots__ = ["_size", "_first_idx", "_parents"]
    def __init__(self, size: int, first_index: int = 0) -> None:
        self._size = size
        self._first_idx = first_index
        self._parents = [-1] * (size + first_index)
    def find(self, x: int) -> int:
        if self._parents[x] < 0:
            return x
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]
    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)
    def unite(self, x: int, y: int) -> bool:
        x, y = self.find(x), self.find(y)
        if x == y:
            return False
        if self._parents[x] > self._parents[y]:
            x, y = y, x
        self._parents[x] += self._parents[y]
        self._parents[y] = x
        return True
    def size(self, x: int) -> int:
        return -self._parents[self.find(x)]
    def group_count(self) ->int:
        return sum(1 for i in  self._parents if i<0)-self._first_idx
    def connected(self) ->bool:
        return self._parents[self.find(self._first_idx)]==-self._size
n,m=map(int,input().split())

uf=UnionFind(n,1)
for i in range(m):
    uf.unite(*map(int,input().split()))
print(-min(uf._parents))

Submission status: Accepted

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())
uf=UnionFind(n)
for i in range(m):
  a,b=map(int,input().split())
  uf.union(a-1,b-1)
ans=1
for i in range(n):
  c=uf.size(i)
  if c>ans:
    ans=c
print(ans)

Submission status: Accepted

Solution code:
belong=list()
group=list()

def init(X):
  global belong
  global group
  belong=list(range(X))
  group=[[i] for i in range(X)]

def unite(x,y):
  if len(group[belong[x]])<len(group[belong[y]]):
    x,y=y,x
  if belong[x]==belong[y]:
    return True
  z=belong[y]
  for i in range(len(group[z])):
    belong[group[z][-1]]=belong[x]
    group[belong[x]].append(group[z][-1])
    del group[z][-1]
  return False

N,M=map(int,input().split())
init(N)
a,b=0,0
for i in range(M):
  a,b=map(int,input().split())
  unite(a-1,b-1)
P=0
for i in range(N):
  P=max(P,len(group[i]))
print(P)

Submission status: Accepted

Solution code:
FAST_IO = 0
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()

    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())
rrmm = lambda n: [rrm() for _ in xrange(n)]

####
from collections import defaultdict as ddic, Counter, deque
import heapq, bisect, itertools
MOD = 10 ** 9 + 7

class DSU:
    def __init__(self, N):
        self.par = list(range(N))
        self.sz = [1] * N

    def find(self, x):
        if self.par[x] != x:
            self.par[x] = self.find(self.par[x])
        return self.par[x]

    def union(self, x, y):
        xr, yr = self.find(x), self.find(y)
        if xr == yr:
            return False
        if self.sz[xr] < self.sz[yr]:
            xr, yr = yr, xr
        self.par[yr] = xr
        self.sz[xr] += self.sz[yr]
        self.sz[yr] = self.sz[xr]
        return True

    def size(self, x):
        return self.sz[self.find(x)]
N,M=rrm()
A= [ rrm() for _ in xrange(M)]

dsu = DSU(N)
for u,v in A:
    u-=1;v-=1
    dsu.union(u, v)

from collections import Counter
count = Counter(dsu.find(u) for u in xrange(N))
print max(count.values())

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = map(int, input().split())
ns = [[] for _ in range(n)]
for _ in range(m):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].append(v)
    ns[v].append(u)
seen = [None]*n
ans = -1
for start in range(n):
    if seen[start]:
        continue
    s = [start]
    seen[start] = True
    val = 0
    while s:
        u = s.pop()
        val += 1
        for v in ns[u]:
            if not seen[v]:
                s.append(v)
                seen[v] = True
    ans = max(ans, val)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

class union_find():
    
    def __init__(self,n):
        self.n=n
        self.root=[-1]*(n+1)
        self.rank=[0]*(n+1)

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

    def unite(self,x,y):
        x=self.find_root(x)
        y=self.find_root(y)

        if x==y:
            return 
        elif self.rank[x]>self.rank[y]:
            self.root[x]+=self.root[y]
            self.root[y]=x
        else:
            self.root[y]+=self.root[x]
            self.root[x]=y

            if self.rank[x]==self.rank[y]:
                self.rank[y]+=1

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

    def cnt(self,x):
        return -self.root[self.find_root(x)]

n,m=map(int,input().split())
g=union_find(n)
ans=0
for _ in range(m):
    a,b=map(int,input().split())
    g.unite(a,b)


for i in range(1,n+1):
    ans=max(ans,g.cnt(i))
print(ans)

Submission status: Accepted

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

    def get_root(self, 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: Accepted

Solution code:
class UnionFindNode:
    def __init__(self, group_id, parent=None, value=None):
        self.group_id_ = group_id
        self.parent_ = parent
        self.value = value
        self.rank_ = 1
        self.member_num_ = 1

    def is_root(self):
        return not self.parent_

    def root(self):
        parent = self
        while not parent.is_root():
            parent = parent.parent_
            self.parent_ = parent
        return parent

    def find(self):
        root = self.root()
        return root.group_id_

    def rank(self):
        root = self.root()
        return root.rank_

    def unite(self, unite_node):
        root = self.root()
        unite_root = unite_node.root()

        if root.group_id_ != unite_root.group_id_:
            if root.rank() > unite_root.rank():
                n_root, child = root, unite_root
            else:
                n_root, child = unite_root, root
            child.parent_ = n_root
            n_root.rank_ = max(n_root.rank_, child.rank_ + 1)
            n_root.member_num_ = n_root.member_num_ + child.member_num_


N, M = map(int, input().split())
nodes = [UnionFindNode(i) for i in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    nodes[a-1].unite(nodes[b-1])
R = 0
for i in range(N):
    R = max(R, nodes[i].root().member_num_)
print(R)

Submission status: Accepted

Solution code:
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class UF:
    def __init__(self, N):
        self.state = [-1] * N
        self.rank = [0] * N
        self.num_group = N
    
    def get_parent(self, a):
        p = self.state[a]
        if p < 0:
            return a
        
        q = self.get_parent(p)
        self.state[a] = q
        return q

    def make_pair(self, a, b):
        pa = self.get_parent(a)
        pb = self.get_parent(b)
        if pa == pb:
            return

        if self.rank[pa] > self.rank[pb]:
            pa, pb = pb, pa
            a, b = b, a
        elif self.rank[pa] == self.rank[pb]:
            self.rank[pb] += 1

        self.state[pb] += self.state[pa]
        self.state[pa] = pb
        self.state[a] = pb
        self.num_group -= 1
    
    def is_pair(self, a, b):
        return self.get_parent(a) == self.get_parent(b)

    def get_size(self, a):
        return -self.state[self.get_parent(a)]


def main():
    N, M = read_values()
    uf = UF(N)
    for _ in range(M):
        A, B = read_index()
        uf.make_pair(A, B)

    res = 0
    for n in range(N):
        res = max(res, uf.get_size(n))

    print(res)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import Counter

n, m = map(int, input().split())
ab = [map(int, input().split()) for _ in range(m)]
a, b = [list(i) for i in zip(*ab)]

a.extend(b)
c = Counter(a)
most = c.most_common(1)[0][0]

temp = []
for i in range(m):
  if a[i] == most or b[i] == most:
    if a[i] == b[i]:
      continue
    temp.append(a[i])
    temp.append(b[i])
temp = list(set(temp))
print(len(temp))

Submission status: Runtime Error

Solution code:
from collections import Counter

n, m = map(int, input().split())
ab = [map(int, input().split()) for _ in range(m)]
a, b = [list(i) for i in zip(*ab)]

a.extend(b)
c = Counter(a)
most = c.most_common(1)[0][0]

temp = []
for i in range(m):
  if a[i] == most or b[i] == most:
    temp.append(a[i])
    temp.append(b[i])
temp = list(set(temp))
print(len(temp))

Submission status: Runtime Error

Solution code:
N, M = (int(d) for d in input().split())

C = [[] for i in range(N+1)]
for i in range(M):
    A, B = (int(d) for d in input().split())
    C[A].append(B)
    C[B].append(A)

# BFS
Q = []
ungrouped = [i for i in range(1, N+1)]
G = []

while len(ungrouped) > 0:
    init = ungrouped.pop(0)
    Q += C[init]
    G.append([])
    G[-1].append(init)

    while len(Q) > 0:
        I = Q.pop(0)
        for J in C[I]:
            if J in ungrouped:
                Q.append(J)
        G[-1].append(I)
        ungrouped.remove(I)

print(max([len(g) for g in G]))

Submission status: Runtime Error

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

par = list(range(n))
qua = [1]*n

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

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

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

print(max(qua))

Submission status: Runtime Error

Solution code:
import networkx as nx

G = nx.Graph()

n, m = map(int, input().split())
for i in range(m):
    a, b = map(int, input().split())
    G.add_edge(a, b)

largest_cc = max(nx.connected_components(G), key=len)
print(len(largest_cc))

Submission status: Runtime Error

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

ans = [i for i in range(1,n+1,1)]
#now = [1]*n
now_num = 1
link = [[] * 1 for i in range(n)]

for i in ab:
    link[i[0]-1].append(i[1])
    link[i[1]-1].append(i[0])
    a = max(len(link[i[0]-1]),len(link[i[1]-1]))
    if now_num < a:
        now_num = a
    
        
print(now_num+1)

Submission status: Runtime Error

Solution code:
par = []
for i in range(n):
    par.append(-1)  #初期親
rank = [1 for i in range(n)] #初期ランク
cut = []
def find(n): #親検索andランク短縮
    global cut
    if par[n] < 0:
        for i in range(len(cut)):
            par[cut[i]] = n
        cut = []
        return n
    else:
        cut.append(n)
        find(par[n])
        return find(par[n])
def shorten(n): # 根に直接接続する
    global cut
    if par[n] < 0:
        for i in range(len(cut)):
            par[cut[i]] = n
        cut = []
    else:
        cut.append(n)
        shorten(par[n])
def unite(a,b): #グループ併合
    x = find(a)
    y = find(b) #根っこ同士をくっつける
    if x == y: 
        return    #既に同一ユニオンなら何もしない
    if rank[x] < rank[y]:
        par[y] += par[x]
        par[x] = y 
    elif rank[x] == rank[y]:
        par[x] += par[y]
        par[y] = x
        rank[x] += 1
    else:
        par[x] += par[y]
        par[y] = x
def judge(a,b):
    return par[a] == par[b]
n,m = map(int,input().split())
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,-par[i])
print(ans)

Submission status: Runtime Error

Solution code:
par = []
for i in range(n):
    par.append(-1)  #初期親
rank = [1 for i in range(n)] #初期ランク
cut = []
def find(n): #親検索andランク短縮
    global cut
    if par[n] < 0:
        for i in range(len(cut)):
            par[cut[i]] = n
        cut = []
        return n
    else:
        cut.append(n)
        find(par[n])
        return find(par[n])
def shorten(n): # 根に直接接続する
    global cut
    if par[n] < 0:
        for i in range(len(cut)):
            par[cut[i]] = n
        cut = []
    else:
        cut.append(n)
        shorten(par[n])
def unite(a,b): #グループ併合
    x = find(a)
    y = find(b) #根っこ同士をくっつける
    if x == y: 
        return    #既に同一ユニオンなら何もしない
    if rank[x] < rank[y]:
        par[y] += par[x]
        par[x] = y 
    elif rank[x] == rank[y]:
        par[x] += par[y]
        par[y] = x
        rank[x] += 1
    else:
        par[x] += par[y]
        par[y] = x
def judge(a,b):
    return par[a] == par[b]

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,-par[i])
print(ans)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
par = []
for i in range(n):
    par.append(i)  #初期親
rank = [1 for i in range(n)] #初期ランク
cut = []
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    unite(a,b)
for i in range(n):
    shorten(i)
import collections
c = collections.Counter(par)
ans = 0
for i in range(n):
    ans = max(ans,c[i])
print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
g = [[] for _ in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

seen = [False]*(n+1)
seen[0] = True

def dfs(root):
    depth=0
    seen[root] = True
    for i in g[root]:
        if seen[i]:
            continue
        depth += dfs(i)
    return depth+1

a=[]

while sum(seen) != n+1:
    a.append(dfs(seen.index(0)+1))

print(max(a))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
g = [[] for _ in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

seen = [False]*(n+1)
seen[0] = True

def dfs(root):
    depth=0
    seen[root] = True
    for i in g[root]:
        if seen[i]:
            continue
        depth += dfs(i)
    return depth+1

a=[]

while sum(seen) != n+1:
    a.append(dfs(seen.index(0)))

print(max(a))

Submission status: Runtime Error

Solution code:
from sys import stdin
from itertools import accumulate

input = stdin.readline
from collections import Counter

N, M = map(int, input().split())
friends = [tuple(map(int, inp.strip().split())) for inp in stdin.read().splitlines()]
father = list(range(N))


def getfather(x):
    if father[x] != x:
        father[x] = getfather(father[x])
    return father[x]


def union(x, y):
    fx = getfather(x)
    fy = getfather(y)
    if fx != fy:
        father[fx] = fy


for a, b in friends:
    union(a - 1, b - 1)
print(max(Counter([getfather(i) for i in range(N)]).values()))

Submission status: Runtime Error

Solution code:
from sys import stdin
from itertools import accumulate
input = stdin.readline
from collections import Counter
N,M = map(int,input().split())
friends = [tuple(map(int,inp.split())) for inp in stdin.read().splitlines()]
father = list(range(N))
def getfather(x):
    if father[x] != x:
        father[x] = getfather(father[x])
    return father[x]
def union(x,y):
    fx = getfather(x)
    fy = getfather(y)
    if fx != fy:
        father[fx] = fy
for a,b in friends:
    union(a-1,b-1)
print(max(Counter([getfather(i) for i in range(N)]).values()))

Submission status: Runtime Error

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

def find(x,par):
    y=par[x]
    while y!=par[y]:
        y=find(y,par)
    par[x]=y
    return par[x]
def unite(a,b,par):
    x=find(a,par)
    y=find(b,par)
    if x!=y:
        par[x]=y

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

cnt=[0 for _ in range(N)]
for i in range(N):
    cnt[find(i,parent)]+=1
print(max(cnt))

Submission status: Runtime Error

Solution code:
from typing import Counter


def main():
    N, M = map(int, input().split())
    friend = [set([]) for _ in range(N)]
    for _ in range(M):
        A, B = map(int, input().split())
        friend[A-1].add(B-1)
        friend[B-1].add(A-1)

    ans = 0
    global visited
    visited = [0] * N
    for n in range(N):
        if visited[n] == 1:
            continue
        else:
            global connect
            connect = 0
            recur(n, friend)
            if connect > ans:
                ans = connect
    print(ans)


def recur(n, friend):
    global visited
    global connect
    visited[n] = 1
    connect += 1
    for i in friend[n]:
        if visited[i] == 0:
            recur(i, friend)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
V=[]
for _ in range(M):
    s=set(map(int,input().split()))
    f=True
    for v in V:
        l=len(s&v)
        if l>0:
            f=False
            if l==1:
                v.update(s)
            break
    if f:
        V.append(s)
print(max(map(len,V)))

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
V=[]
for _ in range(M):
    s=set(map(int,input().split()))
    f=True
    for v in V:
        if len(s&v)>0:
            v.update(s)
            f=False
            break
    if f:
        V.append(s)
print(max(map(len,V)))

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
V=[]
for _ in range(M):
    a,b=map(int,input().split())
    flg=True
    for v in V:
        if (a in v) or (b in v):
            if a not in v:
                v.append(a)
            if b not in v:
                v.append(b)
            flg=False
    if flg:
        V.append([a,b])
print(max(map(len,V)))

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
N,M=map(int,input().split())

visited=[0]*N
frnds=[[] for i in range(N)]

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

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

def saiki(num):
    value=1
    visited[num]=1
    for f in frnds[num]:
        if visited[f]!=1:
            value+=saiki(f)
    return value

ans=0
for i in range(N):
    if visited[i]!=1:
        ans=max(saiki(i),ans)

print(ans)

Submission status: Runtime Error

Solution code:
N,M = (int(x) for x in input().split())
m = []
for i in range(M):
  a,b = (int(x)-1 for x in input().split())
  m.append({a,b})
m_merge = [m.pop(0)]
while m:
  for j in range(len(m_merge)):
    if m_merge[j]&m[0]:
      m_merge[j] = m_merge[j]|m.pop(0)
      break
  else: m_merge.append(m.pop(0))
m_size = [len(x) for x in m_merge]
print(max(m_size))

Submission status: Runtime Error

Solution code:
N,M = (int(x) for x in input().split())
m = []
for i in range(M):
  a,b = (int(x)-1 for x in input().split())
  m.append({a,b})
m_merge = [m.pop(0)]
while m:
  for j in range(len(m_merge)):
    if m_merge[j]&m[0]:
      m_merge[j] = m_merge[j]|m.pop(0)
      break
  else: m_merge.append(m.pop(0))
m_size = [size(x) for x in m_merge]
print(max(m_size))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
ki = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    ki[a-1].append(b-1)
    ki[b-1].append(a-1)
tf = [False for _ in range(N)]

# DFS
def dfs(v):
    global eda
    tf[v] = True
    eda += 1
    for nv in set(ki[v]):
        if not tf[nv]:
            dfs(nv)

ans = 0
for i in range(N):
    if not tf[i]:
        eda = 0
        dfs(i)
        ans = max(ans, eda)
print(ans)

Submission status: Runtime Error

Solution code:
N=list(map(int,input().split()))
n=N[0]
m=N[1]
A = []
for i in range(m):
  array = list(map(int,input().split()))
  array.sort()
  A.append(array)
def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

X=get_unique_list(A)

import collections

t = map(tuple,X)
counted = collections.Counter(t)
mode=counted.most_common()[0][0]

c=1
for j in range(len(X)):
  if mode[0] in X[j]:
    c+=1
 
    
print(c)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
friend = [[0]*n for i in range(n)]
s = [0] * n
for i in range(m):
    a, b = map(int, input().split())
    if friend[a-1][b-1] != 1 and friend[b-1][a-1] != 1:
        friend[a-1][b-1] = 1
        friend[b-1][a-1] = 1
        s[a-1] += 1
        s[b-1] += 1
print(max(s) + 1)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
friend = [[0]*n for i in range(n)]
s = 0
for i in range(m):
    a, b = map(int, input().split())
    friend[a-1][b-1] = 1
    friend[b-1][a-1] = 1
for i in range(n):
    s = max(s, sum(friend[i]))
print(s)

Submission status: Runtime Error

Solution code:
import sys
import resource

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

sys.setrecursionlimit(10 ** 5 * 2)
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)]
#print(len(countpar), len(par))
for i in range(1, n + 1):
  countpar[root(par[i])] += 1
print(max(countpar))
#print(countpar, par)

Submission status: Runtime Error

Solution code:
def root(x):
  if par[x] == x:
    return x
  par[x] = root(par[1])
  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)]
#print(len(countpar), len(par))
for i in range(1, n + 1):
  countpar[root(par[i])] += 1
print(max(countpar))
#print(countpar, par)

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)) + [0 for i in range(200000)]
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 + 200000)]
#print(len(countpar), len(par))
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)) + [0 for i in range(100)]
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 + 100)]
#print(len(countpar), len(par))
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 + 3)]
for i in range(1, n + 1):
  countpar[root(par[i])] += 1
print(max(countpar))

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 + 1):
  if same(root(par[p[i]]), root(par[i])):
    count += 1
print(count)