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 statistics
import copy
n,m = map(int,input().split())
li = []
lig = [0]*n
for i in range(m):
    a,b = map(int,input().split())
    if a >= b:
        li.append((b,a))
    else:
        li.append((a,b))
liset = list(set(li))
c = 1
for i in range(len(liset)):
    if lig[liset[i][0]-1] == 0 and lig[liset[i][1]-1] == 0:
        lig[liset[i][0]-1] = c
        lig[liset[i][1]-1] = c
        c += 1
    if lig[liset[i][0]-1] != 0 and lig[liset[i][1]-1] != 0:
        lig = [lig[liset[i][0]-1] if i == lig[liset[i][1]-1] else i for i in lig]
    if lig[liset[i][0]-1] == 0 and lig[liset[i][1]-1] != 0:
        lig[liset[i][0]-1] = lig[liset[i][1]-1]
    if lig[liset[i][0]-1] != 0 and lig[liset[i][1]-1] == 0: 
        lig[liset[i][1]-1] = lig[liset[i][0]-1]
print(lig.count(statistics.mode(lig)))

Submission status: Runtime Error

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


def dfs(n, y):
    seen[n] = True
    y += 1
    for c in C[n]:
        if seen[c]:
            continue
        else:
            y = dfs(c, y)
    return y


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

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

print(ans)

Submission status: Runtime Error

Solution code:
#Uses python3
import sys
import threading

# This code is used to avoid stack overflow issues
sys.setrecursionlimit(10**9) # max depth of recursion
threading.stack_size(2**32)  # new thread will get stack of such size

visited = set()

def explore(adj, x, comp, cc):
    visited.add(x)
    if not(cc in comp):
        comp[cc] = []
    comp[cc].append(x)
    for w in adj[x]:
        if not (w in visited):
            explore(adj, w, comp, cc)

def number_of_components(adj, n):
    #visited = [False for _ in range(n)]
    cc = 0
    comp = dict()
    for v in range(n):
        if not(v in visited):
            explore(adj, v, comp, cc)
            cc += 1
    return comp


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)
    res = number_of_components(adj, n)
    max_ = 0
    for value in res.values():
        max_ = max(max_, len(value))
    print(max_)
    #print(n - number_of_components(adj, n) - 1)


threading.Thread(target=main).start()

Submission status: Runtime Error

Solution code:
from statistics import mode
N, M = map(int, input().split())
f, k = [], []

for i in range(M):
    A, B = map(int, input().split())
    if [A, B] not in k and [B, A] not in k:
        k.append([A, B])
        f.append(A)
        f.append(B)

print(f.count(mode(f))+1)

Submission status: Runtime Error

Solution code:
import collections

n, m = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(m)]

l = []
for _ in range(n):
  l.append([])

# for x in range(n):
#   l[x]

for a, b in ab:
  a -= 1
  b -= 1
  l[a].append(b)
  l[b].append(a)

# c = [None] * n

# for i in range(n):
#   if c[i] is None:
#     c[i] = i
#   for f in l[i]:
#     if c[f] is None:
#       c[f] = i


c = [None] * n

def dfs(i, d):
  if c[i] is not None:
    return
  c[i] = d

  for f in l[i]:
    dfs(f, d)


for i in range(n):
  if c[i] is None:
    dfs(i, i)

print(max([v for k, v in collections.Counter(c).items()]))

Submission status: Runtime Error

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

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 v_neighbor[n]:
        if not v_visit[n_]:
            v_visit[n_] = True
            count += 1
            count += search(n_)
    return count

res = 0
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:
#Uses python3
import sys
import threading

# This code is used to avoid stack overflow issues
sys.setrecursionlimit(10**6) # max depth of recursion
threading.stack_size(2**26)  # new thread will get stack of such size

visited = set()

def explore(adj, x, comp, cc):
    visited.add(x)
    if not(cc in comp):
        comp[cc] = []
    comp[cc].append(x)
    for w in adj[x]:
        if not (w in visited):
            explore(adj, w, comp, cc)

def number_of_components(adj, n):
    #visited = [False for _ in range(n)]
    cc = 0
    comp = dict()
    for v in range(n):
        if not(v in visited):
            explore(adj, v, comp, cc)
            cc += 1
    return comp


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)
    res = number_of_components(adj, n)
    max_ = 0
    for value in res.values():
        max_ = max(max_, len(value))
    print(max_)
    #print(n - number_of_components(adj, n) - 1)


threading.Thread(target=main).start()

Submission status: Runtime Error

Solution code:
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


n, m = map(int, input().split())
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())
    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, edge)

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

print(max(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(int) 
n,m=map(int,input().split()) 
f={} 
for i in range(m):
    u,v=map(int,input().split()) 
    if u<=v:f[(u,v)]=1  
    else:f[(v,u)]=1 
for x in f:
    adj[x[0]]+=1 
    adj[x[1]]+=1 
#print(adj) 
print(max(list(adj.values()))+1)

Submission status: Runtime Error

Solution code:
from collections import Counter


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 = Counter(find(i) for i in range(N))
for x in count.most_common():
    print(x[1])
    break

Submission status: Runtime Error

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

class DFS:

    def __init__(self):
        self.adj = collections.defaultdict(list)
        self.ans = []

    def addEdge(self, u, v):
        self.adj[u].append(v)
        self.adj[v].append(u)

    def dfs_helper(self, src, visited):
        self.ans.append(src)
        visited[src] = True
        for i in self.adj[src]:
            if not visited[i]:
                self.dfs_helper(i, visited)

    def dfs(self, src):
        res = []
        visited = collections.defaultdict(lambda: False)
        for k, v in self.adj.items():
            visited[k] = False
        for k, v in self.adj.items():
            if not visited[k]:
                self.dfs_helper(k, visited)
                res.append(self.ans)
                self.ans = []
        return res


def solve():
    d = DFS()
    n, m = map(int, input().split())
    if m != 0:
        for _ in range(m):
            u, v = map(int, input().split())
            d.addEdge(u, v)
        ans = d.dfs(1)
        print(len(max(ans, key=lambda i: len(i))))
    else:
        print(1)

solve()

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
if m<1:
  print(1)
elif m == 1:
  print(2)
else: 
  ab = [[]]*m
  for i in range(m):
    ab[i] = list(map(int,input().split()))
    ab[i].sort()
  ab.sort()
  frgrps = {0:{ab[0][0],ab[0][1]}}
  grpno = 0
  for i in range(m):
    if ab[i][0] in frgrps[grpno] or ab[i][1] in frgrps[grpno]:
      frgrps[grpno].update(ab[i])
    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:
import numpy as np
from scipy.sparse.csgraph import connected_components

n, m = map(int, input().split())
A = np.zeros((n, n))

for _ in range(m):
  a, b = map(int, input().split())
  A[a-1, b-1] = 1
  A[b-1, a-1] = 1
    
n, labels = connected_components(A)

result = 0
for i in range(n):
  component_num = (labels == i).sum()
  if component_num > result:
    result = component_num
    
print(result)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D
# CreatedDate:  2020-08-29 21:38:12 +0900
# LastModified: 2020-08-29 21:53:47 +0900
#


import os
import sys
sys.setrecursionlimit(100000)
# import numpy as np
# import pandas as pd
from collections import Counter


def dfs(u, color, path, n, d):
    color[u] = d
    for v in path[u]:
        if color[v] == -1:
            dfs(v, color, path, n, d)



def main():
    n, m = map(int, input().split())
    path = [[] for _ in range(n+1)]
    for _ in range(m):
        a, b = map(int, input().split())
        path[a].append(b)
        path[b].append(a)
    color = [-1]*(n+1)
    d = 0
    for i in range(1, n+1):
        if color[i] == -1:
            dfs(i, color, path, n, d)
            d += 1
    color = color[1:]
    color_cnt = Counter(color).values()
    print(max(color_cnt))



if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def findgraphs(nodes):
    graphs = []
    while nodes:
        graph = set()
        queue = set([next(iter(nodes))])
        while queue:
            nextq = set()
            graph.update(queue)
            for q in queue:
                nextq.update(n for n in nodes[q] if n not in graph)
                del nodes[q]

            queue = nextq

        graphs.append(graph)

    return graphs




friends = dict()
N, M = map(int, input().split())
nodes = {x : set() for x in range(1, N+1)}
for _ in range(M):
    A, B = map(int, input().split())
    nodes[A].add(B)
 
graphs = findgraphs(nodes)

m = max(len(g) for g in graphs)
print(m)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
edge = [[]]
for i in range(M):
    a,b = map(int,input().split())
    add = []
    for j in range(len(edge)):
        if a in edge[j] or b in edge[j]:
            edge[j].append(a)
            edge[j].append(b)
            add.append(j)
    if len(add) == 0:
        edge.append([a,b])
    elif len(add) >= 2:
        for j in range(1,len(add)):
            edge[add[0]].extend(add[j])
        for j in range(1,len(add)):
            edge.pop(j)
ans = 0
for i in range(len(edge)):
    x = list(set(edge[i]))
    if len(x) > ans:
        ans = len(x)
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()
  if b not in frends:
    frends[b] = set()
  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:
    if i not in group[i]:
      c += 1
    cnt = c

print(cnt)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D
# CreatedDate:  2020-08-29 21:38:12 +0900
# LastModified: 2020-08-29 21:52:24 +0900
#


import os
import sys
sys.setrecursionlimit(20000)
# import numpy as np
# import pandas as pd
from collections import Counter


def dfs(u, color, path, n, d):
    color[u] = d
    for v in path[u]:
        if color[v] == -1:
            dfs(v, color, path, n, d)



def main():
    n, m = map(int, input().split())
    path = [[] for _ in range(n+1)]
    for _ in range(m):
        a, b = map(int, input().split())
        path[a].append(b)
        path[b].append(a)
    color = [-1]*(n+1)
    d = 0
    for i in range(1, n+1):
        if color[i] == -1:
            dfs(i, color, path, n, d)
            d += 1
    color = color[1:]
    color_cnt = Counter(color).values()
    print(max(color_cnt))



if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
li = [[] for i in range(N+1)]
for i in range(M):
  a, b = map(int, input().split())
  li[a].append(b)
  li[b].append(a)
  
ans = 0
for i in range(1, N+1):
  s = set(li[i])
  for x in s:
    for y in li[x]:
      if y == i:
        pass
      elif y in s:
        pass
      else:
        s.add(y)
  ans = max(ans, len(s)+1)
print(ans)

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):
    if ab[i][0] in frgrps[grpno] or ab[i][1] in frgrps[grpno]:
      frgrps[grpno].update(ab[i])
    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:
import sys
import collections
input = lambda: sys.stdin.readline().rstrip("\r\n")

class DFS:

    def __init__(self):
        self.adj = collections.defaultdict(list)
        self.ans = []

    def addEdge(self, u, v):
        self.adj[u].append(v)
        self.adj[v].append(u)

    def dfs_helper(self, src, visited):
        self.ans.append(src)
        visited[src] = True
        for i in self.adj[src]:
            if not visited[i]:
                self.dfs_helper(i, visited)

    def dfs(self, src):
        res = []
        visited = collections.defaultdict(lambda: False)
        for k, v in self.adj.items():
            visited[k] = False
        for k, v in self.adj.items():
            if not visited[k]:
                self.dfs_helper(k, visited)
                res.append(self.ans)
                self.ans = []
        return res


def solve():
    d = DFS()
    n, m = map(int, input().split())
    for _ in range(m):
        u, v = map(int, input().split())
        d.addEdge(u, v)
    ans = d.dfs(1)
    print(len(max(ans, key=lambda i: len(i))))

solve()

Submission status: Runtime Error

Solution code:
from collections import defaultdict
 
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):
		ret = defaultdict(list)
		for i in range(self.n):
			ret[self.find(i)].append(i)
		return ret

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

n,m = map(int, input().split())
 
uf = UnionFind(1000)

for _ in range(m):
	a,b = map(int, input().split())
	uf.union(a, b)
MA = 0
for i in range(1000):
	if MA <= uf.size(i):
		MA = uf.size(i)
print(MA)

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
import collections

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


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

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

print(hogehoge[0][1])

Submission status: Runtime Error

Solution code:
from collections import deque

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

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

for i in range(m):
    a,b=input().split()
    G[int(a)-1]+=[int(b)-1]
    G[int(b)-1]+=[int(a)-1]

#print(G)

dist=[-1 for i in range(n)]
# que=deque([0])
# dist[0]=0

count=0
def bfs(G):
    global count
    #print(que)
    if not que:
        return
    v = que.popleft()

    for nv in G[v]:
        if dist[nv] != -1:
            continue
        dist[nv]=dist[v]+1
        que.append(nv)
    count+=1
    
    bfs(G)

ans=0
for i in range(n):
    count=0
    if dist[i] != -1:
        continue
    else:
        que=deque([i])
        dist[i]=0
        bfs(G)
        if ans < count:
            ans=count

print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
index = 1
group = [0] * (n + 1) # 何番目のグループにいるか
groups = [set()] # グループ
for i in range(m):
  a, b = map(int, input().split())
  _a = group[a]
  _b = group[b]
  if _a == 0 and _b == 0: # 新しいグループ
    group[a] = index
    group[b] = index
    groups.append({a,b})
    index += 1
  elif _a == 0: # aが新人
    group[a] = _b
    groups[_b].add(a)
  elif _b == 0: # bが新人
    group[b] = _a
    groups[_a].add(b)
  elif _a != _b: # a,bが別グループに所属
    # 番号の若いほうへ
    if _a < _b: # bのいるグループをaのいるグループに移行
      for m in groups[b]:
        group[m] = _a
      groups[_a] = groups[_a] | groups[_b]
    else: # aのいるグループをbのいるグループに移行
      for m in groups[a]:
        group[m] = _b
      groups[_b] = groups[_b] | groups[_a]
ans = max(map(lambda g: len(g), groups))
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
friends = dict()
for i in range(M):
    a, b = map(int, input().split())
    if friends.get(a) is None:
        friends[a] = set([b])
    else:
        friends[a].add(b)
    if friends.get(b) is None:
        friends[b] = set([a])
    else:
        friends[b].add(a)
ans = max([len(a) for a in friends.values()]) + 1
#print(friends)
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D
# CreatedDate:  2020-08-29 21:38:12 +0900
# LastModified: 2020-08-29 21:51:01 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd
from collections import Counter


def dfs(u, color, path, n, d):
    color[u] = d
    for v in path[u]:
        if color[v] == -1:
            dfs(v, color, path, n, d)



def main():
    n, m = map(int, input().split())
    path = [[] for _ in range(n+1)]
    for _ in range(m):
        a, b = map(int, input().split())
        path[a].append(b)
        path[b].append(a)
    color = [-1]*(n+1)
    d = 0
    for i in range(1, n+1):
        if color[i] == -1:
            dfs(i, color, path, n, d)
            d += 1
    color = color[1:]
    color_cnt = Counter(color).values()
    print(max(color_cnt))



if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#Uses python3

import sys

visited = set()

def explore(adj, x, comp, cc):
    visited.add(x)
    if not(cc in comp):
        comp[cc] = []
    comp[cc].append(x)
    for w in adj[x]:
        if not (w in visited):
            explore(adj, w, comp, cc)

def number_of_components(adj, n):
    #visited = [False for _ in range(n)]
    cc = 0
    comp = dict()
    for v in range(n):
        if not(v in visited):
            explore(adj, v, comp, cc)
            cc += 1
    return comp

if __name__ == '__main__':
    input = sys.stdin.read()
    data = list(map(int, input.split()))
    n, m = data[0:2]
    data = data[2:]
    edges = list(zip(data[0:(2 * m):2], data[1:(2 * m):2]))
    adj = [[] for _ in range(n)]
    for (a, b) in edges:
        adj[a - 1].append(b - 1)
        adj[b - 1].append(a - 1)
    res = number_of_components(adj, n)
    max_ = 0
    for value in res.values():
        max_ = max(max_, len(value))
    print(max_)
    #print(n - number_of_components(adj, n) - 1)

Submission status: Runtime Error

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

r = [[A[0],B[0]]]

for i in range(1, M):
  for j in range(len(r)):
    if A[i] in r[j] and B[i] in r[j]: break
    if not A[i] in r[j] and B[i] in r[j]:
      r[j].append(A[i])
      break
    if A[i] in r[j] and not B[i] in r[j]:
      r[j].append(B[i])
      break
  else: r.append([A[i], B[i]])

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

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

N, M = map(int,input().split())
Adj=np.identity(N)
for i in range(M):
    A, B=  map(int,input().split())
    Adj[A-1,B-1]=1
    Adj[B-1,A-1]=1

AD=Adj**2
count=0
for i in range(N):
    ans=np.count_nonzero(Adj[i, :])
    if ans>count:
        count=ans
print(count)

Submission status: Runtime Error

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

group = []
people = [-1]*n
a,b = map(int, input().split())
group.append([a,b])
people[a-1] = 0
people[b-1] = 0
for i in range(m-1):
  a,b = map(int, input().split())
  
  if people[a-1] != -1 and people[b-1] == -1:
    group[people[a-1]].append(b)
    people[b-1] = people[a-1]
  elif people[a-1] == -1 and people[b-1] != -1:
    group[people[b-1]].append(a)
    people[a-1] = people[a-1]
  elif people[a-1] != -1 and people[b-1] != -1:
    group[people[a-1]] += group[people[b-1]]
    people[b-1] = people[a-1]
  elif people[a-1] == -1 and people[b-1] == -1:
    people[a-1] = len(group)
    people[b-1] = len(group)
    group.append([a,b])

ans = 1
for g in group:
  ans = max(ans,len(list(set(g))))

print(ans)

Submission status: Runtime Error

Solution code:
n,m=list(map(int,input().split()))
par=[i for i in range(n)]
ro=dict()
for i in range(n):
    ro[i]=1
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
        ro[ry]+=ro[rx]
        ro[rx]=0

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


# for i in range(n):
#     ro[root(i)]+=1

print(max(ro.values()))

Submission status: Runtime Error

Solution code:
n,m = (int(x) for x in input().split())
friendlist = [0]*n
classes = 1
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:
        friendlist[a] = classes
        friendlist[b] = classes
        classes += 1

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

print(max(count[1:]))

Submission status: Runtime Error

Solution code:
s = input()
t = input()
x = len(t)
res= 0
for i in range(len(s) - x):
    tmp = s[i:x]
    cntmp = 0
    for j in range(x):
        if t[j] == s[j]:
            cntmp += 1
    res = max(res, cntmp)
print(x-res)

Submission status: Runtime Error

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

N, M = map(int, input().split())
d = {}
for i in range(N):
    d[i] = set()
for i in range(M):
    a, b = map(int, input().split())
    d[a-1].add(b-1)
    d[b-1].add(a-1)


G = []
index = 0
while index < N:
    if index in d:
        s = list([index] + list(d[index]))
        G.append(s)
        for i in d[index]:
            del d[i]
        del d[index]

    index += 1


ret = 0
for i in range(len(G)):
    ret = max(len(G[i]), ret)

print(ret)

Submission status: Runtime Error

Solution code:
n,m = (int(x) for x in input().split())
friendlist = [0]*n
classes = 1
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:
        friendlist[a] = classes
        friendlist[b] = classes
        classes += 1

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

print(count)
print(max(count[1:]))

Submission status: Runtime Error

Solution code:
n,m=list(map(int,input().split()))
par=[i for i in range(n)]
ro=dict(int)
for i in range(n):
    ro[i]=1
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
        ro[ry]+=ro[rx]
        ro[rx]=0

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


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

parent_dict = dict() #key:子 value:親

#接続追加
def add_connect(A,B):
    A_parent = get_parent(A)
    B_parent = get_parent(B)
    
    if A_parent != B_parent:
        parent_dict[B_parent] = A_parent

#接続有無判断
def judge_connection(A,B):
    A_parent = get_parent(A) #未更新状態でも、ここで更新される
    B_parent = get_parent(B)
    
    if A_parent != B_parent:
        return False
    else:
        return True

#親の取得
def get_parent(child):
    if child not in parent_dict: #初出なら自分自身を親として追加
        parent_dict[child] = child
    
    parent = parent_dict[child]
    
    if parent == child: 
        return parent
    else: #最上位の親なら上の等式が成り立つ。不成立ならさらに上位の親を辿る。
        parent_dict[child] = get_parent(parent) 
        return parent_dict[child]


##注意!!　全入力完了後にget_parentをしないと、正しい親が得られない
#ex 12 23 13 56 61 43→{1: 5, 2: 1, 3: 5, 5: 4, 6: 5, 4: 4}になる
for i in range(M):
    A,B = map(int, input().split())
    add_connect(A,B)

for i in range(1,N+1):
    get_parent(i)

#print(parent_dict)

#最も子が多い親を求めるために、親:子の辞書を作る
#child_dict = dict() #key:親 value:子

#for i in range(1,N+1):
#    if parent_dict[i] not in child_dict:
#        child_dict[parent_dict[i]] = set()
#    child_dict[parent_dict[i]].add(i)


#ans = 1
#for parent in child_dict:
#    if len(child_dict[parent]) > ans:
#        ans = len(child_dict[parent])

#print(ans)

Submission status: Runtime Error

Solution code:
import sys,os
import math
from fractions import Fraction 
from collections import defaultdict
from random import randint

# sys.stderr=open('err.txt','w')
# sys.stdout=open('output.txt','w')
# sys.stdin=open('input.txt','r')

def linput():
    return list(minput())

def minput():
    return map(int, sys.stdin.readline().strip().split())

###############################################################

def make_set(a,parent):
    parent[a]=a

def find_set(a,parent):
    if parent[a]==a:
        return a
    parent[a]=find_set(parent[a])
    return parent[a]

def union_set(a,b,parent):
    x=find_set(a)
    y=find_set(b)
    if x==y:
        return
    else:
        parent[y]=x

n,m=minput()
parent=[0]*n
for i in range(n):
    make_set(i,parent)
ans=0
for i in range(m):
    x,y=minput()
    if x>y:
        x,y=y,x
    x=x-1
    y=y-1
    union_set(x,y,parent)
# print(parent)
di = defaultdict(int)
for i in parent:
    di[i]+=1
# print(di)
for k,v in di.items():
    ans=max(ans,v)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict


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


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

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

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