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

Solution (Python):
"""D."""

import sys


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


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

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

    def find_root(self, x: int) -> int:
        """Find root."""

        if self.rank[x] < 0:
            return x

        self.rank[x] = self.find_root(self.rank[x])
        return self.rank[x]

    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.rank[x_root] += self.rank[y_root]
        self.rank[y_root] = x_root

    def get_size(self, x: int) -> int:
        """Get size."""
        return self.rank[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)

Solution (Python):
"""D."""

import sys






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

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

    def find_root(self, x: int) -> int:
        """Find root."""

        if self.rank[x] < 0:
            return x

        self.rank[x] = self.find_root(self.rank[x])
        return self.rank[x]

    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.rank[x_root] += self.rank[y_root]
        self.rank[y_root] = x_root

    def get_size(self, x: int) -> int:
        """Get size."""
        return self.rank[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)

Solution (Python):
from collections import deque


def main():
    n, m = map(int, input().split())
    adj = [[] for _ in range(n)]

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

    ans = 0
    visited = [False] * n

    for i in range(n):
        if visited[i]:
            continue

        q = deque()
        q.append(i)
        cnt = 1
        visited[i] = True

        while q:
            u = q.popleft()
            for v in adj[u]:
                if not visited[v]:
                    q.append(v)
                    cnt += 1
                    visited[v] = True
            ans = max(ans, cnt)

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
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()))






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)

Solution (Python):


import collections

def main():
    n, m = input_list()
    Friend = [[] for i in range(n+1)]
    for _ in range(m):
        a, b = input_list()
        Friend[a].append(b)
        Friend[b].append(a)
    Flag = [False for i in range(n+1)]
    ans = 1
    for i in range(1, n+1):
        if Flag[i]:
            continue
        q = collections.deque()
        q.append(i)
        cnt = 1
        while q:
            st = q.popleft()
            Flag[st] = True
            for j in Friend[st]:
                if Flag[j]:
                    continue
                cnt += 1
                Flag[j] = True
                q.append(j)
            ans = max(ans, cnt)
    print(ans)


def input_list():
    return list(map(int, input().split()))


def input_list_str():
    return list(map(str, input().split()))


if __name__ == "__main__":
    main()

Solution (Python):



class UnionFind:
    
    
    def __init__(self, n):
        self.N = n
        self.parent = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

    
    def root(self, x):
        visited_nodes = []
        while True:
            p = self.parent[x]
            if p == x:
                
                for node in visited_nodes:
                    self.parent[node] = x
                return x
            else:
                visited_nodes.append(x)
                x = p

    
    def unite(self, x, y):
        if not self.root(x) == self.root(y):
            if self.rank[x] > self.rank[y]:
                self.parent[self.root(y)] = self.root(x)
            else:
                self.parent[self.root(x)] = self.root(y)
                if self.rank[x] == self.rank[y]:
                    self.rank[self.root(y)] += 1

    def ifSame(self, x, y):
        return self.root(x) == self.root(y)

    
    def printDebugInfo(self):
        print([self.root(i) for i in range(self.N)])


N, M = map(int, input().split())
tree = UnionFind(N)
for i in range(M):
    A, B = map(int, input().split())
    tree.unite(A-1, B-1)


bag = {}
for i in range(N):
    boss = tree.root(i)
    if not boss in bag.keys():
        bag[boss] = 1
    else:
        bag[boss] += 1

print(max(bag.values()))

Solution (Python):




class UnionFind():
    """ UnionFindはグループの分割はできないことに注意 """
    def __init__(self, n):
        """
            n: 要素数
            parents: 親を示す、-1の場合、自身の親がいない(頂点)であることを示す
        """
        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と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())
    x -= 1
    y -= 1
    union_find.union(x, y)

print(union_find.most_depth_root())

Solution (Python):
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy
INF = 10**9


"""
UnionFind
要素を素集合(互いに素)に分割して管理するデータ構造
O(α)<O(log)
逆アッカーマン関数
"""

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())


if __name__ == "__main__":
    n,m = map(int,input().split())
    uf = UnionFind(n)
    for i in range(m):
        a,b = map(int,input().split())
        a-=1
        b-=1
        uf.union(a,b)
    ans = 0
    for i in range(n):
        c = uf.size(i)
        ans = max(ans,c)
    print(ans)

Solution (Python):

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

    def find(self, x :int) -> int:
        if self.d[x] < 0: return x
        return self.find(self.d[x])
    
    def unite(self, x, y :int):
        xr, yr = self.find(x), self.find(y)
        if xr == yr:
            return

        if -self.d[xr] < -self.d[yr]:
            xr, yr = yr, xr

        self.d[xr] += self.d[yr]
        self.d[yr] = xr

    def is_same(self, x, y :int) -> bool:
        return self.find(x) == self.find(y)

    def size(self, x :int) -> int:
        return - self.d[self.find(x)]


def main():
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in range(m)]
    ab = [[a-1, b-1] for a, b in ab]

    uf = UnionFind(n)

    for a, b in ab:
        uf.unite(a, b)

    mx = 0
    for i in range(n):
        s = uf.size(i)
        if s > mx:
            mx = s

    print(mx)


if __name__ == "__main__":
    main()

Solution (Python):
def find(target):
    if parent[target] < 0:
        return target
    else:
        parent[target] = find(parent[target])
        return parent[target]

def is_same(x, y):
    return find(x) == find(y)

def union(x, y):
    root_x = find(x)
    root_y = find(y)
    if root_x == root_y:
        return
    if parent[root_x] > parent[root_y]:
        root_x, root_y = root_y, root_x
    parent[root_x] += parent[root_y]
    parent[root_y] = root_x


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

def get_size(x):
    return -parent[find(x)]

def get_root():
    return [i for i, root in enumerate(parent) if root < 0]
n, m = map(int, input().split())
parent = [-1 for _ in range(n)]
for _ in range(m):
    a, b = map(lambda x: int(x) - 1, input().split())
    union(a, b)
ans = 0
for i in range(n):
    ans = max(ans, get_size(i))
print(ans)

Solution (Python):
def resolve():
    import sys
    sys.setrecursionlimit(10 ** 6)  
    to_index = lambda x: int(x) - 1  
    print_list_in_2D = lambda x: print(*x, sep="\n")  



    
    def input_int():
        return int(input())

    def map_int_input():
        return map(int, input())

    MII = map_int_input

    def MII_split():
        return map(int, input().split())

    def MII_to_index():
        return map(to_index, input())

    def MII_split_to_index():
        return map(to_index, input().split())

    
    def list_int_inputs():
        return list(map(int, input()))

    LII = list_int_inputs

    def LII_split():
        return list(map(int, input().split()))

    
    def LII_2D(rows_number):
        return [LII() for _ in range(rows_number)]

    def LII_split_2D(rows_number):
        return [LII_split() for _ in range(rows_number)]

    class UnionFind:
        def __init__(self, n):
            """
            :param n: 人数
            :type n: int
            """
            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 = MII_split()


    
    uf = UnionFind(N)

    for _ in range(M):
        A, B = MII_split()
        uf.union(A-1, B-1)  
        
        
        
        
        
        
        
        
        
        
        
        
        

    print(max(uf.size(x) for x in range(uf.group_count())))
    
resolve()

Solution (Python):
import collections

def searchRoot(n):
    par = parList[n]
    if n == par:
        if len(q) > 0:
            rootIn(q,n)
        return n
    else:
        q.append(n)
        return(searchRoot(par))

def rootIn(q,root):
    while len(q) > 0:
        parList[q.popleft()] = root

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

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

for i in range(m):
    a,b = list(map(int,input().split()))
    aRoot = searchRoot(a)
    bRoot = searchRoot(b)
    if aRoot != bRoot:
        parList[max(aRoot,bRoot)] = min(aRoot,bRoot)
    


ansDic = dict()
rootSet = set()
for i in range(1,n+1):
    root = searchRoot(i)
    if root in rootSet:
        ansDic[root] += 1
    else:
        rootSet.add(root)
        ansDic[root] = 1

ans = 1
for i in rootSet:
    if ansDic[i] > ans:
        ans = ansDic[i]

print(ans)

Solution (Python):
class UFTree:
    def __init__(self, N):
        self.nodes = [Node(i) for i in range(N)]
        self.N = N
 
    def find_max_child_num(self):
        result = 0
        for i in range(self.N):
            result = max(result, self.nodes[i].child_num)
        return result
 
class Node:
    def __init__(self, ID):
        self.ID = ID
        self.parent = None
        self.child_num = 0
        self.rank = 1
 
    def get_root(self):
        if self.parent is None:
            return self
        
        return self.parent.get_root()
 
    def concat(self, another):
        sr = self.get_root()
        ar = another.get_root()
 
        
        if sr.ID == ar.ID:
            return
 
        if sr.rank > ar.rank:
            parent, child = sr, ar
        else:
            parent, child = ar, sr
 
        parent.child_num += child.child_num + 1
        parent.rank = max(parent.rank, child.rank + 1)
        child.parent = parent
 
N, M = map(int, input().split())
tree = UFTree(N)
 
AB = []
for i in range(M):
    l = list(map(int, input().split()))
    AB.append(l)
 
for i in range(M):
    a, b = AB[i][0], AB[i][1]
    a -= 1;
    b -= 1;
 
    tree.nodes[a].concat(tree.nodes[b])
 
print(tree.find_max_child_num() + 1)

Solution (Python):
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('tourist.pyx', 'wb').write(zlib.decompress(base64.b85decode("c${TY%Wi`(5WFMt58Fc(Xq*VD9x7D&BPj>l7_bTkIj*Ai>${5yulNExGoBr<UD>{aRttH)I;%|$Qg=gd9dxR@Di;P73FNP9dUGDQ<!!6lSu|K~YBh-_ms0mLUn?gYZW
    os.system('cythonize -i -3 -b tourist.pyx')
import tourist

Solution (Python):
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time


def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False


class UnionFind(object):
    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()),


def main():
    N, M = MI()
    uf = UnionFind(N)

    for i in range(M):
        a, b = MI()
        uf.union(a-1, b-1)

    ret = [uf.size(i) for i in uf.roots()]

    print(max(ret))

if __name__ == '__main__':
    main()

Solution (Python):
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c$|Gw%Wi`(5WFMt58Fc(+?WWe9x7D&BPj>l7_e
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Solution (Python):
import sys
if sys.argv[-1] != 'ONLINE_JUDGE': import solve
else:
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c${TY%Wi`(5WFMt58Fc(Xq*VD9x7D&BPj>l7_bTkIj*Ai>${5yulNExGoBr<UD>{aRttH)I;%|$Qg=gd9dxR@Di;P73FNP9dUGDQ<!!6lSu|K~YBh-_ms0mLUn?gYZW
    os.system('cythonize -i -3 -b solve.pyx')

Solution (Python):
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c${TY%Wi`(5WFMt58Fc(Xq*VD9x7D&BPj>l7_bTkIj*Ai>${5yulNExGoBr<UD>{aRttH)I;%|$Qg=gd9dxR@Di;P73FNP9dUGDQ<!!6lSu|K~YBh-_ms0mLUn?gYZW
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Solution (Python):
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c$`&I!ES>v480@q58h!atm
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Solution (Python):
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c$`&I!ES>v480@q58h!atm
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Solution (Python):
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c${5PL2iRE5WFMthv^{+v?dBYMx`G~IoQTdEE$80tEzo{*Wd=yz1W_eo!MP$KlHFh$m0~eaaTywkAn~BRX?eaXF3w(ceoAiIC9UeRrXFAJ$F}?NJ*tL!
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Solution (Python):
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c${5PL2kn!5WHLRAEt*Sc1xnT$EfZ{QXc?Aiev-A^w7S(i%nyvdjV!=XLlAI+=
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Solution (Python):
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c${5PL2kn!5WHLRAEt*Sc1xnT$EfZ{QXc?Aiev-A^w7S(i%nyvdjV!=XLlAI+=
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Solution (Python):
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c${5PL2kn!5WHLRAEt*Sc1xnT$EfZ{QXc?Aiev-A^w7S(i%nyvdjV!=XLlAI+=
    os.system('cythonize -i -3 -b -j 36 solve.pyx')
import solve

Solution (Python):
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c${5PL2kn!5WHLRAEt*Sc1xnT$EfZ{QXc?Aiev-A^w7S(i%nyvdjV!=XLlAI+=
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Solution (Python):
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c${5PL2kn!5WHLRAEt*Sc1xnT$EfZ{QXc?Aiev-A^w7S(i%nyvdjV!=XLlAI+=
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Solution (Python):
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c${5PL2kn!5WHLRAEt*Sc1xnT$EfZ{QXc?Aiev-A^w7S(i%nyvdjV!=XLlAI+=
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Solution (Python):
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c${5PL2kn!5WHLRAEt*Sc1xnT$EfZ{QXc?Aiev-A^w7S(i%nyvdjV!=XLlAI+=
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Solution (Python):


import queue

def dfs(node, edge, vis):
    vis[node] = True
    count = 1
    vq = []
    vq.append(node)
    vq = queue.LifoQueue()
    vq.put(node)
    while not vq.empty():
        fnode = vq.get()
        for b in edge[fnode]:
            if not vis[b]:
                count += 1
                vq.put(b)
                vis[b] = True
    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)

Solution (Python):

from queue import Queue

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

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

Flag=[False for i in range(N+1)]
ans=1

for i in range(1,N+1):
    if Flag[i]:
        continue
    q=Queue()
    q.put(i)
    cnt=1
    while not q.empty():
        st=q.get()
        Flag[st]=True
        for j in Friend[st]:
            if Flag[j]:
                continue
            cnt+=1
            Flag[j]=True
            q.put(j)
            
        ans=max(ans,cnt)
print(ans)

Solution (Python):
n,m = map(int,input().split())
a = [1]*(n+1)
b = [0]*(n+1)
for i in range(m):
  x,y = map(int,input().split())
  u = x
  while a[u]==0:
    u = b[u]
  v = y
  while a[v]==0:
    v = b[v]
  if u!=v:
    b[v] = u
    b[y] = u
    b[x] = u
    a[u] += a[v]
    a[v] = 0
print(max(a))

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
class UnionFind:
  def __init__(self, n):
    self.n = [-1]*n
    self.r = [0]*n
    self.siz = n

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

  def unite(self, x, y):
    x = self.find_root(x)
    y = self.find_root(y)
    if x == y:
      return
    elif self.r[x] > self.r[y]:
      self.n[x] += self.n[y]
      self.n[y] = x
    else:
      self.n[y] += self.n[x]
      self.n[x] = y
      if self.r[x] == self.r[y]:
        self.r[y] += 1
    self.siz -= 1

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

  def count(self, x):
    return -self.n[self.find_root(x)]

  def size(self):
    return self.siz

n,m=map(int,input().split())
u=UnionFind(n)
for _ in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  u.unite(a,b)
ans=0
for i in range(n):
  ans=max(ans,u.count(i))
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1
 
N,M=map(int,input().split())
 
class UnionFind:
    def __init__(self,n):
        self.par=[i for i in range(n)]
        self.siz=[1]*n
        
    def root(self,x):
        while self.par[x]!=x:
            self.par[x]=self.par[self.par[x]]
            x=self.par[x]
        return x
    
    def unite(self,x,y):
        x=self.root(x)
        y=self.root(y)
        if x==y:
            return False
        if self.siz[x]<self.siz[y]:
            x,y=y,x
        self.siz[x]+=self.siz[y]
        self.par[y]=x
        return True
    
    def is_same(self,x,y):
        return self.root(x)==self.root(y)
    
    def size(self,x):
        return self.siz[self.root(x)]
    
u=UnionFind(N)
 
for _ in range(M):
    a,b=map(int1,input().split())
    
    u.unite(a,b)
    



ans = 0
for aa in u.siz:
    ans=max(ans,aa)
print(ans)

Solution (Python):

import base64
import subprocess
import zlib


exe_bin = "c%1D

open("./kyomu", 'wb').write(zlib.decompress(base64.b85decode(exe_bin)))
subprocess.run(["chmod +x ./kyomu"], shell=True)
subprocess.run(["./kyomu"], shell=True)

Solution (Python):

import subprocess
import sys


if sys.argv[-1] == "ONLINE_JUDGE":
    import zlib, base64

    exe_bin = "c%1E9eRLDol^=Z=8w`>lCNW<@p(ceSR;(bvB4)8{3C2V?Ua*OiKqg`&V>Plwq!HNJmT)jm859v8&Th-eZduap>85mhmQA;Na_H`2aDa5TJta*~!ZvBvrwy$XH^E&Jz5;0Pee<3?GuAZeZvW)@*!SJvyZ65P?!5PA=FRo9f
    open("./kyomu", 'wb').write(zlib.decompress(base64.b85decode(exe_bin)))

subprocess.run(["chmod +x ./kyomu"], shell=True)
subprocess.run(["./kyomu"], shell=True)

Solution (Python):

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 = 0
for i in range(N):
    ans = max(ans, uf.size(i))
print(ans)

Solution (Python):
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.merge(a - 1, b - 1)

ans = 0

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

print(ans)

Solution (Python):
l=lambda:map(int, input().split())
n,m=l()
p=[-1]*n
def root(x):
  if p[x]<0:return x
  p[x]=root(p[x]);return 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))