Problem:


Score : 400 points

Problem Statement

There are N persons called Person 1 through Person N.

You are given M facts that "Person A_i and Person B_i are friends." The same fact may be given multiple times.

If X and Y are friends, and Y and Z are friends, then X and Z are also friends. There is no friendship that cannot be derived from the M given facts.

Takahashi the evil wants to divide the N persons into some number of groups so that every person has no friend in his/her group.

At least how many groups does he need to make?

Constraints

2 \leq N \leq 2\times 10^5

0 \leq M \leq 2\times 10^5

1\leq A_i,B_i\leq N

A_i \neq B_i

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
\vdots
A_M B_M

Output

Print the answer.

Sample Input 1

5 3
1 2
3 4
5 1

Sample Output 1

3

Dividing them into three groups such as \{1,3\}, \{2,4\}, and \{5\} achieves the goal.

Sample Input 2

4 10
1 2
2 1
1 2
2 1
1 2
1 3
1 4
2 3
2 4
3 4

Sample Output 2

4

Sample Input 3

10 4
3 1
4 1
5 9
2 6

Sample Output 3

3



Sample input:
5 3
1 2
3 4
5 1


Sample output:
3

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix
import collections

N,M = map(int,input().split())
N = 2*(10**5)
edge = np.array([input().split() for _ in range(M)], dtype = np.int64).T
tmp = np.ones(M, dtype = np.int64).T
graph = csr_matrix((tmp, (edge[:] -1)), (N, N))

n, labels = connected_components(graph)

c = collections.Counter(labels)

print(max(c.values()))

Submission status: Runtime Error

Solution code:
from collections import Counter

class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]
        
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
            

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.par[a] = b
    
for i in range(N):
    _ = UF.find(i)
    
c = Counter(UF.par)
print(max(c.values()))

Submission status: Runtime Error

Solution code:
import sys


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


class UnionFindPathCompression():
    def __init__(self, n):
        self.parents = list(range(n))

    def find(self, x):
        if self.parents[x] == x:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        self.parents[y] = x

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


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

for i in range(M):
    A, B = map(int, input().split())
    uf.union(A - 1, B - 1)

hoge = [uf.find(i) for i in range(N)]

from collections import defaultdict
d = defaultdict(int)
for key in hoge:
    d[key] += 1

#print(d.values())
print(max(d.values()))

	          #ソート
"""
hoge = list(uf.all_group_members().values())
Max = 0
for i in range(len(hoge)):
    Max = max(Max, len(hoge[i]))

print(Max)
"""

Submission status: Runtime Error

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

color = []
colorStorage = []
for i in range(N):
    color.append(i)
    colorCount.append([i])

for _ in range(M):
    p,q = map(int,input().split())
    p -= 1
    q -= 1
    if color[p] == color[q]:
        continue
    else:
        x = color[p]
        y = color[q]
        if len(colorStorage[x]) >= len(colorStorage[y]):
            for elem in colorStorage[y]:
                color[elem] = x
                colorStorage[x].append(elem)
            colorStorage[y] = []
        else:
            for elem in colorStorage[y]:
                color[elem] = y
                colorStorage[y].append(elem)
            colorStorage[x] = []
maxL = 0
for colorList in colorStorage:
    if maxL < len(colorList):
        maxL = colorList
print(maxL)

Submission status: Runtime Error

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

G = []
m = {}
for a, b in zip(A, B):
    if a not in m and b not in m:
        G.append({a, b})
        m[a] = len(G) - 1
        m[b] = len(G) - 1
    elif a in m:
        G[m[a]].add(b)
    elif b in m:
        G[m[b]].add(a)

if M == 0:
    print(1)
else:
    print(max(len(g) for g in G))

Submission status: Runtime Error

Solution code:
import collections 
def connected(adj,v,visited,f):
    visited[v]=True 
    f.append(v) 
    for i in adj[v]:
        if not visited[i]:
            connected(adj,i,visited,f) 
adj=collections.defaultdict(list) 
n,m=map(int,input().split()) 
for i in range(m):
    u,v=map(int,input().split()) 
    adj[u-1].append(v-1) 
    adj[v-1].append(u-1) 
visited=[False]*(n)  
ans=0 
for i in range(n):
    f=[] 
    if not visited[i]:
        connected(adj,i,visited,f) 
    ans=max(ans,len(f)) 
print(ans)

Submission status: Runtime Error

Solution code:

#!/usr/bin/python
# -*- coding: utf-8 -*-

# def
def int_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(map(int,input().split())))
    return np.array(x)

def str_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(input()))
    return np.array(x)

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

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

def print_space(l):
    return print(" ".join([str(x) for x in l]))

# import
import collections as col

import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix


# main code
N,M = int_map()
AB = int_mtx(M)

l = np.zeros((N,N))
for i in range(0,M):
    l[AB[i][0]-1,AB[i][1]-1] = 1

n, labels = connected_components(l)

ll = list(labels)
aa = col.Counter(ll)
print(aa.most_common()[0][1])

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
friend = [[0] * n for i in range(n)]
for i in range(m):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    friend[x][y] = 1
    friend[y][x] = 1
maxfriend = 0
for li in friend:
    maxfriend = max(maxfriend, sum(li))
print(maxfriend+1)

Submission status: Runtime Error

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


def readstr():
    return input().strip()


def readint():
    return int(input())


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


def readstrs():
    return input().split()


def main():
    N, M = readnums()
    ab = [tuple(readnums()) for _ in range(M)]
    al = list()
    for a, b in ab:
        if not al:
            al.append(set([a, b]))
        else:
            for g in al:
                if a in g:
                    g.add(b)
                    break
                elif b in g:
                    g.add(a)
                    break
            else:
                al.append(set([a, b]))

    ans = max(list(map(lambda x: len(x), al)))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
visited = [False for _ in range(n+1)]

# print("graph is : ", graph)
# print("visited is : ", visited)
def dfs(node):
    visited[node] = True
    ret = 0
    for child in graph[node]:
        if not visited[child]:
            ret += dfs(child)
    return ret + 1


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

rets = []
for node in range(1, n+1):
    if not visited[node] :
        counts = dfs(node)
        rets.append(counts)
print(max(rets))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
ad_list = {}
for i in range(M):
  a, b = map(int, input().split())
  if a in ad_list:
    ad_list[a].add(b)
  else:
    ad_list[a] = {b}
  if b in ad_list:
    ad_list[b].add(a)
  else:
    ad_list[b] = {a}

#BFS
ans = 0
done = [True for i in range(N+1)]

def dfs(x):
  global done
  global tmp
  for y in ad_list[x]:
    if done[y]:
      done[y] = False
      tmp += 1
      dfs(y)
      
for i in range(1, N+1):
  if done[i]:
    done[i] = False
    tmp = 1
    if i in ad_list:
        dfs(i)
    ans = max(ans, tmp)

print(ans)

Submission status: Runtime Error

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

from collections import defaultdict

g=[set() for i in range(n)]

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

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

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

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

for i in range(m):
    a,b=list(map(int,input().split()))
    # f[a-1].add(b-1)
    # f[b-1].add(a-1)
    a-=1
    b-=1
    unite(a,b)

ans=0
ro=defaultdict(int)
for i in range(n):
    ro[root(i)]+=1

print(max(ro.values()))

Submission status: Runtime Error

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

for i in range(M):
    l.append([int(x) for x in input().split()])

mn = 0
for i in range(M):
    for j in range(2):
        mn = max(mn,l[i][j])

s = [0 for i in range(mn)]
k = [0 for i in range(M)]
cnt = 0
for i in range(M):
    if s[l[i][0]-1] == 0 and s[l[i][1]-1] == 0:
        cnt += 1
        s[l[i][0]-1] = cnt
        s[l[i][1]-1] = cnt
        k[cnt-1] += 2
    elif s[l[i][0]-1] == 0 and s[l[i][1]-1] != 0:
        s[l[i][0]-1] = s[l[i][1]-1]
        k[s[l[i][1]]-1] += 1
    elif s[l[i][0]-1] != 0 and s[l[i][1]-1] == 0:
        s[l[i][1]-1] = s[l[i][0]-1]
        k[s[l[i][0]]-1] += 1

print(max(k))

Submission status: Runtime Error

Solution code:
import collections 
def connected(adj,v,visited,f):
    visited[v]=True 
    f.append(v) 
    for i in adj[v]:
        if not visited[i]:
            connected(adj,i,visited,f) 
adj=collections.defaultdict(set) 
n,m=map(int,input().split()) 
for i in range(m):
    u,v=map(int,input().split()) 
    adj[u-1].add(v-1) 
    adj[v-1].add(u-1) 
visited=[False]*(n)  
ans=0 
for i in range(n):
    f=[] 
    if not visited[i]:
        connected(adj,i,visited,f) 
    ans=max(ans,len(f)) 
print(ans)

Submission status: Runtime Error

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

G = []

for i, f in enumerate(F):
    new_grp = True
    for j, g in enumerate(G):
        if f[0] in g:
            if f[1] not in g:
                G[j].append(f[1])
                new_grp = False
        if f[1] in g:
            if f[0] not in g:
                G[j].append(f[0])
                new_grp = False
    if new_grp:
        G.append(f)

print(max(map(len, G)))

Submission status: Runtime Error

Solution code:
x, y = map(int, input().split())

graph = [[] for n in range(x+1)]

st = {}

for n in range(y):
    a, b = map(int, input().split())

    if a > b:
        a, b = b, a

    if (a, b) not in st:
        st[(a, b)] = 1

        graph[a].append(b)
        graph[b].append(a)


res = 0
vis = {}


def dfs(node):
    global res
    vis[node] = 1
    res += 1
    for n in graph[node]:
        if n not in vis:
            dfs(n)


mx = 0
for n in range(1, x+1):
    res = 0
    if n not in vis:
        dfs(n)
        mx = max(mx, res)

print(mx)

Submission status: Runtime Error

Solution code:
import collections

# https://www.ics.uci.edu/~eppstein/PADS/UnionFind.py


class UnionFind:
    """Union-find data structure.

    Each unionFind instance X maintains a family of disjoint sets of
    hashable objects, supporting the following two methods:

    - X[item] returns a name for the set containing the given item.
      Each set is named by an arbitrarily-chosen one of its members; as
      long as the set remains unchanged it will keep the same name. If
      the item is not yet part of a set in X, a new singleton set is
      created for it.

    - X.union(item1, item2, ...) merges the sets containing each item
      into a single larger set.  If any item is not yet part of a set
      in X, it is added to X as one of the members of the merged set.
    """

    def __init__(self):
        """Create a new empty union-find structure."""
        self.weights = {}
        self.parents = {}

    def __getitem__(self, object):
        """Find and return the name of the set containing the object."""

        # check for previously unknown object
        if object not in self.parents:
            self.parents[object] = object
            self.weights[object] = 1
            return object

        # find path of objects leading to the root
        path = [object]
        root = self.parents[object]
        while root != path[-1]:
            path.append(root)
            root = self.parents[root]

        # compress the path and return
        for ancestor in path:
            self.parents[ancestor] = root
        return root

    def __iter__(self):
        """Iterate through all items ever found or unioned by this structure."""
        return iter(self.parents)

    def union(self, *objects):
        """Find the sets containing the objects and merge them all."""
        roots = [self[x] for x in objects]
        heaviest = max([(self.weights[r], r) for r in roots])[1]
        for r in roots:
            if r != heaviest:
                self.weights[heaviest] += self.weights[r]
                self.parents[r] = heaviest


n, m = [int(x) for x in input().split()]
uf = UnionFind()
for _ in range(m):
    a, b = [int(x) for x in input().split()]
    uf.union(a, b)
print(collections.Counter(uf.parents.values()).most_common(1)[0][1])

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix
import collections

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

grid = []
for i in range(m):
    array = list(map(int, input().strip().split(' ')))
    grid.append(array)

l = np.zeros((n,n))

for i in range(m):
    l[grid[i][0]-1][grid[i][1]-1] = 1

n, labels = connected_components(csr_matrix(l))

c = collections.Counter(labels)

print(max(c.values()))

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a,b = map(int,input().split())
sets = [set([a,b])]
for i in range(m-1):
  a,b = map(int,input().split())
  for s in sets:
    if a in s:
      s.add(b)
    elif b in s:
      s.add(a)
    else:
      sets.append(set([a,b]))
ans = 0
for s in sets:
  ans = max(ans,len(s))
print(ans)

Submission status: Runtime Error

Solution code:
import collections 
def connected(adj,v,visited,f):
    visited[v]=True 
    f.append(v) 
    for i in adj[v]:
        if not visited[i]:
            connected(adj,i,visited,f) 
adj=collections.defaultdict(set) 
n,m=map(int,input().split()) 
for i in range(m):
    u,v=map(int,input().split()) 
    adj[u-1].add(v-1) 
    adj[v-1].add(u-1) 
visited=[False]*(n)  
ans=0 
for i in range(n):
    f=[] 
    if not visited[i]:
        connected(adj,i,visited,f) 
        ans=max(ans,len(f)) 
print(ans)

Submission status: Runtime Error

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

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

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

def union(x,y):
  x=find(x)
  y=find(y)
  if x!=y:
    par[x]=y
 
f=lambda x:int(x)-1
for i in range(m):
  x,y=map(f,input().split())
  union(x,y)
  
for j in range(n):
  find(j)
from collections import Counter
c=Counter(par)
cv=c.values()
print(max(cv))

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
ls = [0 for _ in range(N)]
flg = 1
for i in range(M):
    a,b = map(int,input().split())
    if ls[a-1] == 0 and ls[b-1]==0:
        ls[a-1]=flg
        ls[b-1]=flg
        flg+=1
    elif ls[a-1] == 0:
        ls[a-1] = ls[b-1]
    elif ls[b-1] == 0:
        ls[b-1] = ls[a-1]
    else:
        check = min(ls[a-1],ls[b-1])
        ls[a-1] = check
        ls[b-1] = check
import collections
c = collections.Counter(ls)
plan = c.most_common()
ans = 0
if plan[0][0] == 0:
    ans = plan[1][1]
else:
    ans = plan[0][1]
print(ans)

Submission status: Runtime Error

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

g = [set([fs[0][0], fs[0][1]])]
for a, b in fs[1:]:
    f = 0
    for j in g:
        if a in j or b in j:
            f = 1
            j.add(a)
            j.add(b)
    if f == 0:
        g.append(set([a, b]))

ans = 0
for i in g:
    ans = max(ans, len(i))
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict


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


def union(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    parent[x] = y


def find(x):
    if parent[x] == -1:
        return x
    res = parent[x] = find(parent[x])
    return res

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


count = defaultdict(int)
for i in range(N):
    count[find(i)] += 1
print(max(count.values()))

Submission status: Runtime Error

Solution code:
import numpy as np

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

u = UnionFind(n)

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

res = u.all_group_members()
mxsz = 0
for i in res:
  mxsz = max(mxsz, len(res[i]))
print(mxsz)

Submission status: Runtime Error

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

G = []
m = {}
for a, b in zip(A, B):
    if a not in m and b not in m:
        G.append({a, b})
        m[a] = len(G) - 1
        m[b] = len(G) - 1
    elif a in m:
        gid = m[a]
        G[gid].add(b)
    elif b in m:
        gid = m[b]
        G[gid].add(a)

max_size = max(len(g) for g in G)
print(max_size)

Submission status: Runtime Error

Solution code:
(n,m),*e=[[*map(int,i.split())]for i in open(0)]
d=[[]for i in range(n+1)]
for i,j in e:
    d[i]+=[j]
    d[j]+=[i]
print(max(len(set(d[i]+d[j]))for i in range(n+1)for j in d[i]))

Submission status: Runtime Error

Solution code:
n,m=list(map(int,input().split(" ")))
group=[]
idx=[-1]*n
for i in range(m):
    a,b=list(map(int,input().split(" ")))
    a-=1
    b-=1
    if idx[a]!=-1 or idx[b]!=-1:
        if (idx[a]!=-1 and idx[b]!=-1) and idx[a]!=idx[b]:
            new_group=group[idx[a]]+group[idx[b]]
            length=len(group)
            for g in group[idx[a]]:
                idx[g]=length
            for g in group[idx[b]]:
                idx[g]=length
            group.append(new_group)
        elif idx[a]!=idx[b]:
            if idx[a]==-1:
                group[idx[b]].append(a)
                idx[a]=idx[b]
            else:
                group[idx[a]].append(b)
                idx[b]=idx[a]
    else:
        group.append([a,b])
        idx[a]=len(group)-1
        idx[b]=len(group)-1
M=len(group[0])
for g in group:
    if len(g)>M:
        M=len(g)
print(M)

Submission status: Runtime Error

Solution code:
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
input = sys.stdin.readline
INF = float("inf")


def dfs(G, visited, v, cnt):
    visited[v] = True
    cnt += 1

    for nv in G[v]:
        if visited[nv]:
            continue
        cnt = dfs(G, visited, nv, cnt)
    
    return cnt


# 処理内容
def main():
    N, M = map(int, input().split())

    if M == 0:
        print(1)
        return

    P = set()
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1; b -= 1
        if a > b:
            a, b = b, a
        P.add((a, b))

    G = [[] for _ in range(N)]
    for pair in P:
        a, b = pair
        G[a].append(b)
        G[b].append(a)

    visited = [False] * N
    ans = 0
    for i in range(N):
        if visited[i]:
            continue
        ans = max(ans, dfs(G, visited, 0, 0))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import collections

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

data = set()
for _ in range(M):
  a, b = map(int, input().split())
  data.add((min([a, b]), max([a, b])))

c = collections.Counter(sum(map(list, data), []))
print(c.most_common(1)[0][1] + 1)

Submission status: Runtime Error

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

for _ in range(M):
    A, B = map(lambda x:int(x) - 1, input().split())
    to[A].append(B)
    to[B].append(A)


def dfs(v, to, seen):
    global count
    seen[v] = True
    count += 1
    for nv in to[v]:
        if seen[nv] == True:
            continue
        dfs(nv, to, seen)


def main():
    global count
    seen = [False] * N
    cnts = []
    for i in range(N):
        if not seen[i]:
            dfs(i, to, seen)
            cnts.append(count)
            count = 0
    
    print(max(cnts))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
from collections import Counter

input = lambda : sys.stdin.readline().rstrip()

def main(pairs, n, m):

    graph = {}
    for node in range(1, n+1):
        graph[node] = []

    for a, b in pairs:
        graph[a].append(b)
        graph[b].append(a)

    gids = [None] * (n+1)

    def get_gid(in_i, cur_gid):
        gids[in_i] = cur_gid
        kids = graph[in_i]
        for kid in kids:
            if gids[kid] is None:
                get_gid(kid, cur_gid)


    cur_gid = 0
    for i in range(1, n+1):
        if gids[i] is None:
            get_gid(i, cur_gid)
            cur_gid += 1

    out = Counter(gids).most_common(1)[0][1]
    print(out)

n, m = map(int, input().split(" "))
pairs = set([tuple(sorted(map(int, input().split(" ")))) for i in range(m)])
#import random
#n = random.randint(2, 2000)
#m = random.randint(0, 2000)
#pairs = set([tuple(sorted([random.randint(1, n), random.randint(1, n)])) for i in range(m)])
#print(n, m)
#print(pairs)

main(pairs, n, m)

Submission status: Runtime Error

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

group = [0]*n
group_num = 1

for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    a1 = group[a]  
    b1 = group[b]
    if a1 == 0 and b1 == 0:
        group[a] = group_num
        group[b] = group_num
        group_num += 1
    elif a1 != 0:
        group[b] = a1
    else:
        group[a] = b1

group.sort()
group_num1 = 1
cnt = 1

if m != 0:
    for i in range(group.index(1)+1,n):
        if group[i] == group[i-1]:
            cnt += 1
        else:
            ans = max(ans,cnt)
            cnt = 1
    ans = max(ans,cnt)
    print(ans)
else:
    print(1)

Submission status: Runtime Error

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

ab = [[int(_)-1 for _ in input().split()]for i in range(m)]

for i in range(m):
    if ab[i][0] > ab[i][1]:
        ab[i][0], ab[i][1] = ab[i][1], ab[i][0]

ab.sort(key=lambda x: (x[1], x[0]))

t = [-1 for i in range(n)]
ans = [0 for i in range(n)]
for i in range(m):
    a, b = ab[i]
    if t[b] == -1:
        if t[a] == -1:
            t[b] = a
        else:
            t[b] = t[a]
        ans[t[b]] += 1
    else:


print(max(ans)+1)
# print(t)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
to = [[] for i in range(N)]
for i in range(M):
    A, B = map(int, input().split())
    to[A-1].append(B-1)
    to[B-1].append(A-1)

ans = 0

def DFS(n):
    global h, ans
    #print(h)
    if h[n] == 1:
        ans = max(ans, sum(h))
        return
    h[n] = 1
    for x in to[n]:
        DFS(x)

for i in range(N):
    h = [0] * N
    DFS(i)

print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
UF = [-1] * (N+1)
def find(x):
    global UF
    if UF[x] == -1:
        return x
    else:
        UF[x] = find(UF[x])
        return UF[x]
def union(x,y):
    global UF
    xx = find(x)
    yy = find(y)
    if UF[x] == UF[y] == -1:
        UF[y] = xx
        return
    elif xx == yy:
        return 
    else:
        UF[yy] = xx
        return 
    
for _ in range(M):
    x, y = map(int, input().split())
    union(x,y)
    
cnt = [0] * (N+1)

for i in range(1,N+1):
    z = find(i)
    cnt[z] += 1

print(max(cnt))

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;


//      DEEP

using namespace std;
#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define all(v) v.begin(),v.end()
#define pb push_back
#define endl '\n'
#define mp make_pair

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef pair<int,int> pi;
typedef pair<long long,long long> pll;
typedef set<int> si;


/*
typedef tree<int,null_type,less<int>,rb_tree_tag,
tree_order_statistics_node_update> indexed_set;
*/
/*
typedef tree<
pair<int, int>,
null_type,
less<pair<int, int>>,
rb_tree_tag,
tree_order_statistics_node_update> ordered_set;
*/

const ll mod = 1e9 + 7;
const ll modl=998244353;
const double pie=3.1415926535;
                                                    //power
ull power(ull x,ull y){
   if(y==0) return 1;
   else{
     if(y%2==0) return power(x*x,y/2);
     else return x*power(x*x,(y-1)/2);
   }
}

                        //                    Modular Exponentiation

ll mod_power(ll x, ll y, ll m)
{
    ll r = 1;     // Initialize result

    x = x % m; // Update x if it is more than or equal to m

    if (x == 0) return 0; // In case x is divisible by m;

    while (y > 0)
    {
        // If y is odd, multiply x with result
        if (y & 1)
            r = (r*x) % m;

        // y must be even now
        y = y/2;
        x = (x*x) % m;
    }
    return r;
}

                                                      //GCD
ll gcd(ll x,ll y){
   if(y==0)return x;
   return gcd(y,x%y);
}
                                              // SIEVE

/*
bool isPrime[100001];
void sieve(int N) {

        for(int i = 0; i <= N;++i) {
            isPrime[i]=true;
        }
        isPrime[0]=false;
        isPrime[1]=false;

        for(int i = 2; i * i <= N; ++i) {
             if(isPrime[i] == true) {
                 for(int j = i * i; j <= N ;j += i)
                     isPrime[j] = false;
            }
        }
    }
*/
int gcdExtended(int a, int b, int *x, int *y); 
  
int modInverse(int b, int m) 
{ 
    int x, y; // used in extended GCD algorithm 
    int g = gcdExtended(b, m, &x, &y); 
  
    // Return -1 if b and m are not co-prime 
    if (g != 1) 
        return -1; 
  
    // m is added to handle negative x 
    return (x%m + m) % m; 
} 
int modDivide(int a, int b, int m) 
{ 
    a = a % m; 
    int inv = modInverse(b, m); 
    if (inv == -1) 
       return -1;
    else{
       ll ans=(inv * a) % m; 
       return ans;
     }
    
} 
int gcdExtended(int a, int b, int *x, int *y) 
{ 
    // Base Case 
    if (a == 0) 
    { 
        *x = 0, *y = 1; 
        return b; 
    } 
  
    int x1, y1; // To store results of recursive call 
    int gcd = gcdExtended(b%a, a, &x1, &y1); 
  
    // Update x and y using results of recursive 
    // call 
    *x = y1 - (b/a) * x1; 
    *y = x1; 
  
    return gcd; 
} 
int c=0;
vector<si>adj;
vector<bool>visited;
void dfs(int x){
  visited[x]=true;
  c++;
  for(int i : adj[x]){
    if(!visited[i])dfs(i);
  }
}
int main(){
    boost;
    int TESTS=1;
    //cin>>TESTS;
    while(TESTS--){
      int n,m;
      cin>>n>>m;
      adj=vector<set<int> >(n+1);
      visited=vector<bool>(n+1,false);
      for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        if(x!=y){
        adj[x].insert(y);
        adj[y].insert(x);
      }
      }
      int ans=0;
      for(int i=1;i<=n;i++){
        if(!visited[i]){
          c=0;
          dfs(i);
          ans=max(ans,c);
        }
      }
      cout<<ans<<endl;
     
      
    }
}

Submission status: Runtime Error

Solution code:
def dfs(s):
	ret = 1
	vis[s] = True
	for v in adj[s]:
		if not vis[v]:
			ret+=dfs(v)
	return ret

n,m = map(int,input().split())
adj = [set() for i in range(n)]
for _ in range(m):
	u,v = map(int,input().split())
	u-=1
	v-=1
	adj[u].add(v)
	adj[v].add(u)
	
vis = [False] * n

ans = 0
for i in range(n):
	if not vis[i]:
		tmp = dfs(i)
		ans = max(ans, tmp)
		
print(ans)

Submission status: Runtime Error

Solution code:
import collections


class unionFind:
    parent = []
    count = []

    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.count = [1]*N

    def root(self, x):
        if self.parent[x] == x:
            return(x)
        else:
            self.parent[x] = self.root(self.parent[x])
            self.count[x] = self.count[self.parent[x]]
            return(self.parent[x])

    def same(self, x, y):
        x, y = x-1, y-1
        return(self.root(x) == self.root(y))

    def unite(self, x, y):
        x, y = x-1, y-1
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.parent[x] = y
            self.count[y] += self.count[x]
            self.count[x] = self.count[y]
            return

    def getCount(self, x):
        x = self.root(x)
        return(self.count[x])


N, M = map(int, input().split())
G = unionFind(N)
for i in range(M):
    a, b = map(int, input().split())
    G.unite(a, b)

ans = 1
for i in range(N):
    ans = max(ans, G.getCount(i))

print(ans)