Problem:


Score : 400 points

Problem Statement

There are N persons called Person 1 through Person N.

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

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

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

At least how many groups does he need to make?

Constraints

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

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

1\leq A_i,B_i\leq N

A_i \neq B_i

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
\vdots
A_M B_M

Output

Print the answer.

Sample Input 1

5 3
1 2
3 4
5 1

Sample Output 1

3

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

Sample Input 2

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

Sample Output 2

4

Sample Input 3

10 4
3 1
4 1
5 9
2 6

Sample Output 3

3



Sample input:
5 3
1 2
3 4
5 1


Sample output:
3

Submission status: Runtime Error

Solution code:

def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

n,m=map(int,input().split())
L=[]

for i in range(m):
    if L==[]:
        L.append(list(map(int,input().split())))
    else:
        t=list(map(int,input().split()))

        for j in range(len(L)):
            if t[0] in L[j] or t[1] in L[j]:
                L[j]=get_unique_list(L[j]+t)
                break
            else:
                 L.append(t)

print(max(len(x) for x in L))

Submission status: Runtime Error

Solution code:
n,m = map(int, input().split())
g = [[] for i in range(n)]
for i in range(m):
  a, b = map(int, input().split())
  if not b-1 in g[a-1]:
    g[a-1].append(b-1)
  if not a-1 in g[b-1]:
    g[b-1].append(a-1)
v = [-1 for i in range(n)]
ans = [0]*n
def dfs(x,y):
  for i in g[x]:
    if v[i] == -1:
      v[i]=v[x]+1
      ans[y]+=1
      dfs(i,y)
for i in range(n):
  if v[i]!=-1:
    continue
  v[i]=0
  dfs(i,i)
print(max(ans)+1)

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 sys

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

sys.setrecursionlimit(M+1)

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


v_visit = [False for _ in range(N)]

def search(n):
    count = 0
    for n_ in set(v_neighbor[n]):
        if not v_visit[n_]:
            v_visit[n_] = True
            count += 1
            count += search(n_)
    return count

res = 1
for i in range(N):
    if v_visit[i]:
        continue
    search_res = search(i)
    res = max(res, search_res)


print(res)

Submission status: Runtime Error

Solution code:
N,M=map(int, input().split())
AB=[list(map(int, input().split())) for _ in range(M)]
mem=[AB.pop(0)]

for _ in range(M-1):
	temp=AB.pop(0)
	if temp not in AB:
		i,j=temp[0],temp[1]
		flag=0
		for h in range(len(mem)):
			if i in mem[h] and j not in mem[h]:
				flag=1
				mem[h].append(j)
			elif j in mem[h] and i not in mem[h]:	
				flag=1
				mem[h].append(i)		
			elif i in mem[h] and j in mem[h]:
				flag=1
		if flag==0:
			mem.append(temp)
		flag=0

ans=0

for n in range(len(mem)):
	ans=max(ans,len(mem[n]))

print(ans)

Submission status: Runtime Error

Solution code:
import random

n, m = map(int, input().split())
# n, m = 10, 10
group = {i: 0 for i in range(1, n+1)}
edge = {}
g_mem = {}
g_num = 0
g_con = set()

for i in range(m):
    a, b = map(int, input().split())
    # a, b = random.sample(range(1,n+1), 2)
    if group[a]==0 and group[b] == 0:
        g_num += 1
        group[a] = g_num
        group[b] = g_num
        g_mem[g_num] = 2
    elif group[a] == 0:
        group[a] = group[b]
        g_mem[group[b]] += 1
    elif group[b] == 0:
        group[b] = group[a]
        g_mem[group[a]] += 1
    elif group[a] != group[b]:
        if edge.get(group[a]):
            edge[group[a]].add(group[b])
        else:
            edge[group[a]] = {group[b]}
        if edge.get(group[b]):
            edge[group[b]].add(group[a])
        else:
            edge[group[b]] = {group[a]}

# print(g_mem)
# print(sum(g_mem.values()))
# print(edge)

g_reached = {i: 0 for i in range(1, g_num+1)}

def dps(g_mem, edge, now):
    count = g_mem[now]
    if edge.get(now):
        for e in edge[now]:
            if g_reached[e] == 0:
                g_reached[e] = 1
                count += dps(g_mem, edge, e)
    return count


ans = []
for now in range(1, g_num+1):
    if g_reached[now] == 0:
        g_reached[now] = 1
        ans.append(dps(g_mem, edge, now))

# print(ans)
print(max(ans))

Submission status: Runtime Error

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

class QuickFind(object):
    id = []
    count = 0

    def __init__(self, n):
        self.count = n
        i = 0
        while i < n:
            self.id.append(i)
            i += 1

    def connected(self, p, q):
        return self.find(p) == self.find(q)

    def find(self, p):
        return self.id[p]

    def union(self, p, q):
        idp = self.find(p)
        if not self.connected(p, q):
            for i in range(len(self.id)):
                if self.id[i] == idp:  # 将p所在组内的所有节点的id都设为q的当前id
                    self.id[i] = self.id[q]
            self.count -= 1

qf = QuickFind(10)

print
"initial id list is %s" % (",").join(str(x) for x in qf.id)


for k in abList:
    p = k[0]
    q = k[1]
    qf.union(p, q)
    print( "%d and %d is connected? %s" % (p, q, str(qf.connected(p, q))))

countMax = {}
for x in qf.id:
    if x in countMax:
        countMax[x] += 1
    else:
        countMax[x] = 0
print(max(countMax, key=countMax.get))

Submission status: Runtime Error

Solution code:
import collections
n, m = map(int, input().split())
gp = []
hf = [-1 for i in range(n+1)]

for i in range(m):
  a, b = map(int, input().split())
  if hf[a] == -1 and hf[b] == -1:
    hf[a] = len(gp)
    hf[b] = len(gp)
    gp.append([a, b])
  elif hf[a] == -1:
    hf[a] = hf[b]
    gp[hf[b]].append(a)
  elif hf[b] == -1:
    hf[b] = hf[a]
    gp[hf[a]].append(b)
  else:
    if hf[a] != hf[b]:
      gp.append(gp[hf[a]]+gp[hf[b]])
      for j in gp[hf[a]]:
        hf[j] = len(gp)-1
      for j in gp[hf[b]]:
        hf[j] = len(gp)-1

c = collections.Counter(hf).most_common()
if c[0][0] == -1:
  print(c[1][1])
else:
  print(c[0][1])

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
import collections


class UnionFind2:
    def __init__(self, size):
        # 負の値はルート (集合の代表)
        # 正の値は次の要素を表す
        self.table = [-1 for _ in range(size)]

    # 集合の代表を求める
    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            # 経路の圧縮
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    # 併合
    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            self.table[s2] = s1
            return True
        return False


N, M = map(int, input().split())
uf = UnionFind2(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)]

# print(hoge)
hogehoge = collections.Counter(hoge).most_common()

print(hogehoge[0][1])

Submission status: Runtime Error

Solution code:
from  collections import Counter

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

friends = []

for _ in range(M):
    A_i, B_i = map(int, input().split())
    if A_i > B_i:
        A_i, B_i = B_i, A_i
    friends.append((A_i, B_i))

friends = list(set(friends))

friends_count = []

for friend_set in friends:
    friends_count.append(friend_set[0])
    friends_count.append(friend_set[1])
    
print(Counter(friends_count).most_common()[0][1] + 1)

Submission status: Runtime Error

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

n,m = map(int, input().split())
matrix = np.zeros((n,n))
for i in range(m):
  a,b = map(int, input().split())
  matrix[a-1][b-1] += 1

x, labels = connected_components(matrix)
group_count = [0 for i in range(x)]
for i in labels:
  group_count[i] += 1
print(max(group_count))

Submission status: Runtime Error

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

## taken from GFG

class Graph:
    
	def __init__(self,V): 
		self.V = V 
		self.adj = [[] for i in range(V)] 

	def DFSUtil(self, temp, v, visited): 
		visited[v] = True
		temp.append(v) 
		for i in self.adj[v]: 
			if visited[i] == False: 
				temp = self.DFSUtil(temp, i, visited) 
		return temp
        
	def addEdge(self, v, w): 
		self.adj[v].append(w) 
		self.adj[w].append(v) 

	def connectedComponents(self): 
		visited = [] 
		cc = [] 
		for i in range(self.V): 
			visited.append(False) 
		for v in range(self.V): 
			if visited[v] == False: 
				temp = [] 
				cc.append(self.DFSUtil(temp, v, visited)) 
		return cc 

def solve():
    n, m = map(int, input().split())
    g = Graph(n)
    if m:
        for _ in range(m):
            u, v = map(int, input().split())
            g.addEdge(u - 1, v - 1)
        ans = g.connectedComponents()
        res = - 10 ** 10
        for i in ans:
            res = max(res, len(i))
        print(res)
    else:
        print(1)

if __name__=="__main__": 
	solve()

Submission status: Runtime Error

Solution code:
def make_group(checked, a, friends):
  group = []
  if checked[a]:
    return group
  group.append(a)
  checked[a] = True
  for b in friends[a]:
    group += make_group(checked, b, friends)
  return group
  
n, m = map(int, input().split())
friends = {}
checked = {}
for i in range(n):
  friends[i+1] = set()
  checked[i+1] = False
for i in range(m):
  a, b = map(int, input().split())
  friends[a].add(b)
  friends[b].add(a)
for i in range(n):
  friends[i+1] = sorted(list(friends[i+1]))
minimum = -float('inf')
for i in range(1, n+1):
  group = make_group(checked, i, friends)
  if group:
    minimum = max(minimum, len(group))
print(minimum)

Submission status: Runtime Error

Solution code:
import collections
import math

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

N,M=map(int, input().split())
l=[[0 for i in range(N)]for j in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    l[a-1][b-1]=1


a = np.array(l)
# print(type(a))
# # <class 'numpy.ndarray'>

n, labels = connected_components(a)

cc=collections.Counter(labels)
ans=max(cc.values())
print(ans)

Submission status: Runtime Error

Solution code:

def resolve():
    import sys
    sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
    to_index = lambda x: int(x) - 1  # 入力した数字に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()))

    # 2次元リスト化
    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)]

    N, M = MII_split()
    groups = []
    for _ in range(M):
        A, B = MII_split()
        is_in_groups = False
        for group in groups:
            if A in group and B not in group:
                group.append(B)
                break
            elif B in group and A not in group:
                group.append(A)
                break
            elif A in group and B in group:
                is_in_groups = True
                break
        if not is_in_groups:
            groups.append([A, B])

    print(max([len(x) for x in groups]) if len(groups) > 0 else 1)
    
  resolve()

Submission status: Runtime Error

Solution code:
n,q=map(int,input().split())
track=(n+1)*[0]
for i in range(q):
    j, k = map(int, input().split())
    j, k = min(j, k), max(j, k)
    if type(track[j]) is int and track[j]==0:
        track[j]={k:1}
        track[k]=-j
    elif type(track[j]) is int and track[j]<0:
        track[-track[j]][k]=1
        track[k]=track[j]
    else:
        track[j][k]=1
ans=1
for i in track:
    if type(i) is not int:
        ans=max(ans,1+len(i))
print(ans)

Submission status: Runtime Error

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

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

for i in range(m):
  a = list(map(int, input().split()))
  a.sort()
  x, y = a[0]-1,a[1]-1
  friend[x].add(y)
  friend[y].add(x)

def dfs(s):
  if vis[s] == False:
    vis[s] = True
    ary.append(s)
    for j in friend[s]:
      dfs(j)
vis = [False for i in range(n)]
ans = 0
for i in range(n):
  ary = []
  dfs(i)
  ans = max(ans,len(ary))
print (ans)

Submission status: Runtime Error

Solution code:
def solve():
    n, m = map(int, input().split())
    group = []
    done = [-1]*n
    num = 0
    for i in range(m):
        a, b = map(lambda x:int(x)-1, input().split())
        if done[a] != -1:
            if done[b] == -1:
                group[done[a]].append(b)
                done[b] = done[a]
        else:
            if done[b] == -1:
                group.append([a,b])
                done[a], done[b] = num, num
                num += 1
            else:
                group[done[b]].append(a)
                done[a] = done[b]
    people = [len(i) for i in group]
    print(max(people))
    return 0

if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
from collections import defaultdict as dc
x, y = map(int, input().split())
graph = [[] for n in range(x+1)]

st = dc(lambda: 0)

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

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

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

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


res = 0
vis = dc(lambda: 0)


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


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

print(mx)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
info = []
count = 0
while count < M:
    A, B = map(int,input().split())
    info += [[A,B]]
    count += 1


friends = []
for k in range(1,N+1):
    for I in info:
        if I[0] == k and I[1] < k:
            flag = False
            for j in range(len(friends)):
                if I[1] in friends[j] and k not in friends[j]:
                    flag = True
                    friends[j] += [k]
            if flag == False:
                friends += [[I]]
        elif I[1] == k and I[0] < k:
            flag = False
            for j in range(len(friends)):
                if I[0] in friends[j] and k not in friends[j]:
                    flag = True
                    friends[j] += [k]
            if flag == False:
                friends += [I]

print(max(len(f) for f in friends))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
L=[list(map(int,input().split()))]

def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

for i in range(m-1):
    t=list(map(int,input().split()))
    
    for j in range(len(L)):
        if t[0] in L[j] or t[1] in L[j]:
            L[j]=get_unique_list(L[j]+t)
            break
        else:
             L.append(t)

print(max(len(x) for x in L))

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

D = defaultdict(set)
R = {}
for _ in range(M):
  a, b = map(int, input().split())
  if a in R:
    if b in R:
      aa, bb = R[a], R[b] 
      if aa == bb:
        pass
      else:
        for x in D[bb]:
          R[x] = aa
        D[aa] |= D[bb]
        del D[bb]
    else:
      R[b] = R[a]
      D[R[a]].add(b)
  else:
    if b in R:
      R[a] = R[b]
      D[R[b]].add(a)
    else:
      R[a] = a
      R[b] = a
      D[a].add(a)
      D[a].add(b)

print(max(len(x) for x in D.values()))

Submission status: Runtime Error

Solution code:
import collections
N, M = map(int, input().split())
groups = [0] * (N + 1)
group_num = 1
for _ in range(M):
    A, B = map(int, input().split())
    if groups[A] != 0:
        groups[B] = groups[A]
    elif groups[B] != 0:
        groups[A] = groups[B]
    else:
        groups[A] = groups[B] = group_num
        group_num += 1
collection = collections.Counter(groups)
# print(collection)
print(collection.most_common()[0][1] if collection.most_common()[0][0] != 0 else collection.most_common()[1][1])

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
ab = [[]]*m
for i in range(m):
  ab[i] = list(map(int,input().split()))
  ab[i].sort()
if m<1:
  print(1)
else:  
  ab.sort()
  frgrps = {0:{ab[0][0],ab[0][1]}}
  grpno = 0
  for i in range(m):
    for j in range(grpno+1):
      if ab[i][0] in frgrps[j] or ab[i][1] in frgrps[j]:
        frgrps[j].update(ab[i])
        break
    else:
      grpno += 1
      frgrps[grpno] = {ab[i][0],ab[i][1]}
longestset = 0
for x in frgrps:
  longestset = max(longestset,len(frgrps[x]))
print(longestset)

Submission status: Runtime Error

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

for i in range(m):
  a, b = map(int, input().split())
  if a > b:
    a, b = b, a
  group_idx[b - 1] = group_idx[a - 1]
  print(group_idx)

groups = [0 for i in range(n)]

for i in range(n):
  groups[group_idx[i]] += 1

print(group_idx)
print(max(groups))

Submission status: Runtime Error

Solution code:
import collections # deque, Counter
# import itertools   # accumulate, compress, permutations(nPr), combinations(nCr)
# import bisect      # bisect_left(insert位置), bisect_right(slice用)
# import math        # factorical（階乗) # hypot(距離)
# import heapq
# from fractions import gcd # >=Python3.5 # lcm（最小公倍数） = (a*b)//gcd(a,b)
# from fractions import Fraction
# from math import gcd # <Python3.5
# --------------------------------------------------------------

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())
lis = [list(map(int,input().split())) for _ in range(m)]
 
cmax  = 0
 
uf = UnionFind(n)

for i in lis:
    uf.union(i[0],i[1])

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

print(cmax)

Submission status: Runtime Error

Solution code:
#グループの最大人数を算出=ans

N,M = map(int,input().split())
groups = []

for i in range(M):
    A,B = map(int,input().split())
    groups.append([A,B])

for i in range(M):
    groups = list(map(lambda x: list(set(x+groups[i])) if not set(x).isdisjoint(set(groups[i])) else x, groups))

print(max(len(x) for x in groups))

Submission status: Runtime Error

Solution code:
def DFS(graph, start, end, mark_set, max_count):
    mark_set.add(start)
    tmp = max_count
    for target in list(graph[start]):
        if target == end:
            print("exist")
            return
        elif target not in mark_set:
            mark_set.add(target)
            tmp = max(DFS(graph, target, end, mark_set, max_count), tmp)
    return tmp + 1


N, M = map(lambda x: int(x), input().split(" "))

graph = {x: set() for x in range(1, N+1)}


for _ in range(M):
    A, B = map(lambda x: int(x), input().split(" "))
    graph[A].add(B)
    graph[B].add(A)

result = 0
mark_set = set()

while True:
    if len(mark_set) == N:
        break
    for i in range(1, N+1):
        if i in mark_set:
            continue
        result = max(DFS(graph, i, -1, mark_set, 0), result)

result += 1
if result > N:
    result = N

print(result)

Submission status: Runtime Error

Solution code:
import copy
(N,M) = map(int,input().split())
l = []
if M == 0:
    print(1)

else:
    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] += 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] += 1
        else:
            t = copy.deepcopy(s)
            s = [t[l[i][1]-1] for x in t if x == t[l[i][0]-1]]
            k[t[l[i][1]-1]-1] += k[t[l[i][0]-1]-1]

    print(max(k))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
ab = [map(int, sorted(input().split())) for _ in range(m)]
a, b = [list(i) for i in zip(*ab)]
ans=[set(str(i)) for i in range(1,n+1)]
for i in range(m):
  ans[a[i]-1].add(b[i])
print(max([len(x) for x in ans]))

Submission status: Runtime Error

Solution code:
def resolve():
    import sys
    sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
    to_index = lambda x: int(x) - 1  # 入力した数字に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()))

    # 2次元リスト化
    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)]

    N, M = MII_split()
    groups = []
    for _ in range(M):
        A, B = MII_split()
        is_in_groups = False
        for group in groups:
            if A in group and B not in group:
                group.append(B)
            elif B in group and A not in group:
                group.append(A)
            elif A in group and B in group:
                is_in_groups = True
        if not is_in_groups:
            groups.append([A, B])


    print(max([len(x) for x in groups]))

resolve()

Submission status: Runtime Error

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

A, B = list(map(int, input().split()))
T = [{A, B}]

for i in range(M-1):
    A, B = list(map(int, input().split()))
    Flag = True
    for j in T:
        if A in j:
            if B in j:
                Flag = False
            else:
                j.add(B)
                Flag = False
        else:
            if B in j:
                j.add(A)
                Flag = False
            else:
                pass
    if Flag:
        T.append({A, B})

ans = len(T[-1])
yu = []

for i in range(len(T)-1):
    if ans < len(T[i]):
        ans = len(T[i])
    for j in range(i+1, len(T)):
        for k in T[i]:
            if k in T[j]:
                yu.append(T[i] | T[j])
                if ans < len(T[i] | T[j]):
                    ans = len(T[i] | T[j])
                break


print(ans)

Submission status: Runtime Error

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

for i in range(1, M):
  a, b = input().split()
  for j in range(len(r)):
    if a in r[j] or b in r[j]:
      r[j].append(a)
      r[j].append(b)
    else:
      r.append([a, b])

ans = 0
for i in range(len(r)):
  ans = max(ans, len(set(r[i])))

print(ans)

Submission status: Runtime Error

Solution code:
import copy

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

frends = {}

for i in range(m):
  a,b = map(int, input().split())
  if a not in frends:
    frends[a] = set([a])
  if b not in frends:
    frends[b] = set([b])
  frends[a].add(b)
  frends[b].add(a)

group = copy.copy(frends) 
  
for i in frends:
  flag = False
  r = group[i]
  for j in r:
    if j > i:
      flag = True
      break
  if flag == True:
    group[max(r)].update(group.pop(i))

    
cnt = 0
for i in group:
  c = len(group[i])
  if c > cnt:
    cnt = c

print(cnt)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
d = {x:-1 for x in range(1,n+1)}
gp = []

for _ in range(m):
    i,j = map(int, input().split())
    if d[i] == -1 and d[j] == -1:
        gp.append({i, j})
        d[i] = len(gp) - 1
        d[j] = len(gp) - 1
    elif d[i] == -1 and d[j] != -1:
        d[i] = d[j]
        gp[d[j]].add(i)
    elif d[i] != -1 and d[j] == -1:
        d[j] = d[i]
        gp[d[i]].add(j)
    else:
        if d[i] != d[j]:
            gp[d[i]].update(gp[d[j]])
            for item in gp[d[j]]:
                d[item] = d[i]
                
print(max([len(x) for x in gp]))

Submission status: Runtime Error

Solution code:
from collections import defaultdict

def dfs(node):
    if node in visited:
        return False
    visited.add(node)
    for neighbor in adj_list[node]:
        dfs(neighbor)
    return True

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

A, B = [], []

adj_list = defaultdict(set)
visited = set([])

count = 0

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

#for node in range(1, N+1):
#    if dfs(node):
#        count += 1

print(max(map(lambda x: len(x)+1, adj_list.values())))

Submission status: Runtime Error

Solution code:
import collections

N, M = map(int, input().split())
friend_group = [0] * (N+1)

for _ in range(M):
    a, b = map(int, input().split())
    tmp = max(friend_group[a], friend_group[b])
    if tmp == 0:
        tmp = a

    friend_group[a] = tmp
    friend_group[b] = tmp

col = collections.Counter(friend_group)
sorted_rank = sorted(col.values(), reverse=True)
r1 = sorted_rank[0]
r2 = sorted_rank[1]

if col.get(0) == r1:
    print(r2)
else:
    print(r1)

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.height = [0 for _ in range(n)]
            
    def unite(self, i, j):
        root_i = self.get_root(i)
        root_j = self.get_root(j)
        if root_i != root_j:
            if self.height[root_i] < self.height[root_j]:
                self.parent[root_i] = root_j
            else:
                self.parent[root_j] = root_i
                if self.height[root_j] == self.height[root_j]:
                    self.height[root_i] += 1
                    
    def max_group_size(self):
        d = {}
        for i in self.parent:
            if i not in d:
                d[i] = 1
            else:
                d[i] += 1
        values = list(d.values())
        return max(values)

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.unite(a, b)
ans = u.max_group_size()
print(ans)

Submission status: Runtime Error

Solution code:
def resolve():
    import sys
    sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
    to_index = lambda x: int(x) - 1  # 入力した数字に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()))

    # 2次元リスト化
    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)]

    N, M = MII_split()
    groups = []
    for _ in range(M):
        A, B = MII_split()
        is_in_groups = False
        for group in groups:
            if A in group and B not in group:
                group.append(B)
            elif B in group and A not in group:
                group.append(A)
            elif A in group and B in group:
                is_in_groups = True
        if not is_in_groups:
            groups.append([A, B])


    print(max([len(x) for x in groups]))

resolve()

Submission status: Runtime Error

Solution code:
n,m = (int(x) for x in input().split())
friendlist = [0]*(n+1)
classes = 0
for i in range(m):
    a,b = (int(x)-1 for x in input().split())
    if friendlist[a]!=0:
        friendlist[b] = friendlist[a]
    elif friendlist[b]!=0:
        friendlist[a] = friendlist[b]
    else:
        classes += 1
        friendlist[a] = classes
        friendlist[b] = classes

count = [0]*(classes+1)
for i in range(n):
    count[friendlist[i]] += 1
print(max(count[1:]))

Submission status: Runtime Error

Solution code:
from collections import defaultdict as dc
x, y = map(int, input().split())
graph = [[] for n in range(x+1)]

st = dc(lambda: 0)

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

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

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

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


res = 0
vis = dc(lambda: 0)


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 vis[n] == 0:
        dfs(n)
        mx = max(mx, res)

print(mx)