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: Wrong Answer

Solution code:
N,M = map(int,input().split())
mInfos = [list(map(int, input().split())) for _ in range(M)]
gl = [0]*N
gc = 0
for i in range(M):
    mInfo = mInfos[i]
    p1 = mInfo[0]
    p2 = mInfo[1]
    naiflag = True
    if gl[p1-1] == 0 and gl[p2-1] == 0:
        gl[p1 - 1] = gc + 1
        gl[p2 - 1] = gc + 1
        gc += 1
    elif gl[p1-1] != 0:
        gl[p2 - 1] = gl[p1-1]
    else:
        gl[p1 - 1] = gl[p2 - 1]

mi = 0
for i in range(1,gc+1):
    dd = gl.count(i)
    mi = max(mi,dd)
print(mi)

Submission status: Wrong Answer

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

    for i in range(M):
        A, B = map(int, input().split())
        person[A - 1] |= 1 << (B - 1)
        person[B - 1] |= 1 << (A - 1)
        person[A - 1] |= person[B - 1]
        person[B - 1] |= person[A - 1]

    ans = 0
    for i in range(N):
        p = str(bin(person[i]))
        ans = max(ans, p.count("1"))

    print(ans)

if __name__ == "__main__":
    main2()

Submission status: Wrong Answer

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

network = {i: set() for i in range(1, N+1)}

for a, b in AB:
    network[a].add(b)
    network[b].add(a)

group_num = sorted([len(v) for v in network.values()], reverse=True)[0] + 1
print(group_num)

Submission status: Wrong Answer

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
    big = max(a, b)
    small = min(a, b)
    
    if UF.par[big] == big:
        UF.par[big] = small
    else:
        num = min(UF.par[big], UF.find(small))
        UF.par[UF.par[big]] = num
        UF.par[small] = num
        UF.par[big] = num
        
for i in range(N):
    _ = UF.find(i)

c = Counter(UF.par)
print(max(c.values()))

Submission status: Wrong Answer

Solution code:
nm = input('').split()
n = int(nm[0])
m = int(nm[1])

mx=0
friends={}
for i in range(n):
    friends[i+1]=set([i+1])
for i in range(m):
    ab=input('').split()
    a = int(ab[0])
    b = int(ab[1])
    friends[a].add(b)
    friends[b].add(a)
#    print("{} <<{} ={}".format(a,b,friends[a]))
#    print("{} <<{} ={}".format(b,a,friends[b]))
    if len(friends[a]) > mx:
        mx=len(friends[a])
    if len(friends[b]) > mx:
        mx=len(friends[b])

    for a2 in friends[a]:
        friends[a2].add(b)
#       print("{} <<{} ={}".format(a2,b,friends[a2]))
        if len(friends[a2]) > mx:
            mx=len(friends[a2])
    for b2 in friends[b]:
        friends[b2].add(b)
#        print("{} <<{} ={}".format(a2,b,friends[a2]))
        if len(friends[b2]) > mx:
            mx=len(friends[b2])

#print(friends)
print(mx)

Submission status: Wrong Answer

Solution code:
import sys,math
from collections import deque,defaultdict
import operator as op
from functools import reduce

sys.setrecursionlimit(10**6) 

I=sys.stdin.readline

 #s="abcdefghijklmnopqrstuvwxyz"

"""
x_move=[-1,0,1,0,-1,1,1,-1]
y_move=[0,1,0,-1,1,1,-1,-1]
"""
def ii():
	return int(I().strip())
def li():
	return list(map(int,I().strip().split()))
def mi():
	return map(int,I().strip().split())

def ncr(n, r):
    r = min(r, n-r)
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer // denom

def gcd(x, y):
    while y:
        x, y = y, x % y
    return x




	
def main():
	n,m=mi()
	ans=0
	d=defaultdict(int)
	grp=[0]*(n+1)
	mem=[-1]*(n+1)
	for i in range(m):
		a,b=mi()
		if mem[a]==-1 and mem[b]==-1:
			grp[a]+=2
			mem[a]=1
			mem[b]=a
			d[(a,b)]=1
			d[(b,a)]=1
		elif d[(a,b)]==0 or d[(b,a)]==0:
			if mem[a]==-1:
				if mem[b]==1:
					mem[a]=b
					grp[b]+=1
				else:
					mem[a]=mem[b]
					grp[mem[b]]+=1

			else:
				if mem[a]==1:
					mem[b]=a
					grp[a]+=1
				else:
					mem[b]=mem[a]
					grp[mem[a]]+=1

			d[(a,b)]=1
			d[(b,a)]=1
	#print(grp)
	print(max(grp))




			


	

























	
	
	





if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
N,M = list(map(int, input().split()))
d = {}
newd = {}
for i in range(N):
  d[i+1] = []
  newd[i+1] = []
for i in range(M):
  A,B = list(map(int, input().split()))
  d[A].append(B)
  d[B].append(A)
#print(d)

for i in range(N):
  d[i+1] = list(set(d[i+1]))

#print(d)

for i in range(N):
  if(len(d[i+1])>=2):
    for j in range(len(d[i+1])):
      for k in range(j+1,len(d[i+1])):
        newd[ d[i+1][j] ].append(d[i+1][k])
        newd[ d[i+1][k] ].append(d[i+1][j])
#print(newd)

for i in range(N):
  if(len(newd[i+1])>0):
    for j in range(len(newd[i+1])):
      if(newd[i+1][j] not in d[i+1]):
        d[i+1].append(newd[i+1][j])
#print(d)

anslist = []
for i in range(N):
  anslist.append(len(d[i+1]))
print(max(anslist)+1)

Submission status: Wrong Answer

Solution code:
#coding: utf-8
from collections import defaultdict

N, M = [int(x) for x in input().split()]

uniq_grp = 0
grp = defaultdict(int)
ngrp = defaultdict(int)

ret = 0

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

    if a in grp:
        if b not in grp:
            grp[b] = grp[a]
            ngrp[grp[b]] += 1
            ret = max(ret, ngrp[grp[b]])
    elif b in grp:
        if a not in grp:
            grp[a] = grp[b]
            ngrp[grp[a]] += 1
            ret = max(ret, ngrp[grp[a]])
    else:
        grp[a] = uniq_grp
        grp[b] = grp[a]
        ngrp[grp[a]] += 2

        uniq_grp += 1
        ret = max(ret, ngrp[grp[a]])

print(ret)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
l = [[] for i in range(N)]
for i in range(M):
        a, b = map(int, input().split())
        l[a - 1].append(b - 1)
        l[b - 1].append(a - 1)
m = 0 
for i in range(N):
    
        m = max(m, len(set(l[i])))
print(m + 1)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
f_l = [[] for _ in range(n)]
ans_list = [0]*n

for i in range(m):
    a,b = map(int,input().split())
    f_l[a-1].append(b)
    for j in f_l[a-1]:
        if j != b:
            f_l[j-1].append(b)
    f_l[b-1].append(a)
    for j in f_l[b-1]:
        if j != a:
            f_l[j-1].append(a)

for i in range(n):
    ans_list[i] = len(set(f_l[i]))

print(max(ans_list)+1)

Submission status: Wrong Answer

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

import networkx as nx

edges = []
for _ in range(M):
    i,j=map(int, input().split())
    i-=1
    j-=1
    edges.append([i,j])
G = nx.Graph()
G.add_nodes_from(range(N))
G.add_edges_from(edges)
sg = nx.connected_components(G)
connected = sorted(sg)

"""
max_len = 0
for nodes in connected:
    len_ = len(nodes)
    if len_>max_len:
        max_len=len_
"""
print(len(connected[0]))

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
I = [-1] * (n+1)
x = [[]]
for _ in range(m):
    a,b = map(int, input().split())
    if (I[a]!=-1 and I[b]!=-1) or a==b: continue
    if x == [[]]:
        x[0] += [a,b]
        I[a]=I[b]=0
    else:
        if I[a]!=-1 and I[b] == -1:
            x[I[a]].append(b)
            I[b] = I[a]
        elif I[b] != -1 and I[a] == -1:
            x[I[b]].append(a)
            I[a] = I[b]
        elif I[b] == -1 and I[a] == -1:
            x.append([a,b])
            I[a]=I[b]=len(x)-1
ans = 0
for i in x:
    ans = max(ans, len(i))
print(ans if ans != 0 else 1)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.height = [0 for _ in range(n)]
        
    def get_root(self, i):
        if self.parent[i] == i:
            return i
        else:
            self.parent[i] = self.get_root(self.parent[i])
            return self.parent[i]
            
    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)
if m == 0:
    print(1)
    exit()
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: Wrong Answer

Solution code:
import numpy as np
N, M = map(int, input().split())
A = np.zeros((M,2), dtype=int)

for i in range(M):
    Ai = input().split()
    A[i,0] = int(Ai[0])
    A[i,1] = int(Ai[1])

Asort = np.sort(A, axis=0)

Grp_lst = np.arange(1, N+1)
for i in range(M):
    Grp_lst[Asort[i,1] - 1] = Grp_lst[Asort[i,0] - 1]

count = np.zeros(N,dtype=int)

for i in range(N):
    count[Grp_lst[i]-1] += 1

print(max(count))

Submission status: Wrong Answer

Solution code:
class Solution:
    def find_root(self, A, parent):
        if parent[A] == A:
            return A
        return self.find_root(parent[A], parent)

    def union(self, A, B, parent, height):
        C = self.find_root(A, parent)
        D = self.find_root(B, parent)

        if C == D:
            return

        if height[C] < height[D]:
            parent[C] = D

        elif height[C] > height[D]:
            parent[D] = C

        else:
            parent[D] = C
            height[C] += 1

        self.cnt += 1

    def solve(self, A, N):
        self.cnt = 0
        parent = [i for i in range(N)]
        height = [0 for _ in range(N)]
        for i, j in A:
            C = self.find_root(i-1, parent)
            D = self.find_root(j-1, parent)

            if C == D:
                continue

            self.union(C, D, parent, height)

        return self.cnt

if __name__ == '__main__':
    N, M = map(int, input().split())
    A = []
    for _ in range(M):
        p,q = map(int, input().split())
        A.append([p,q])
    B = Solution()
    print(B.solve(A, N))

Submission status: Wrong Answer

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

grpno=[i for i in range(N)]
ngrp=[1 for i in range(N)]
# members=[[i] for i in range(N)]


for i in range(M):
    p,q = list(map(int,input().split()))

    if grpno[p-1] > grpno[q-1]:
        r = p
        p = q
        q = r
    
    if grpno[p-1] != grpno[q-1]:
        ngrp[grpno[p-1]] += ngrp[grpno[q-1]]
        ngrp[grpno[q-1]] = 0
        grpno[q-1]=grpno[p-1]
   
        # members[p-1] += members[q-1]

# for i in range(N):
#     print("i=",i)
#     print(members[i])
#     print("group_no=",grpno[i])
#     print("#member=",ngrp[i])

print(max(ngrp))

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import Counter


# Union-Find木
class Union_Find():
    def __init__(self, N=1):
        self.par = [i for i in range(N)]  # 親ノード
        self.rank = [0] * N               # ランク

    # 経路圧縮
    def root(self, x):
        if self.par[x] == x:
            return x
        else:
            r = self.root(self.par[x])
            self.par[x] = r
            return r

    # xとyが同じグループに属するか判定
    def issame(self, x, y):
        return self.root(x) == self.root(y)

    # xとyの属するグループを1つにまとめる
    def merge(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        else:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            elif self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            return True


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, M = list(map(int, _in[0].split(' ')))  # type:list(int)
    A_B_arr = []
    for i in range(M):
        _ = list(map(int, _in[i+1].split(' ')))  # type:list(int)
        A_B_arr.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    uf = Union_Find(N)
    for a, b in A_B_arr:
        a -= 1
        b -= 1
        uf.merge(a, b)
    cnt = Counter(uf.par)
    ans = cnt.most_common()[0][1]
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n,m=map(int, input().split())
alist=[]
for i in range(m):
  a,b=map(int, input().split())
  c=[a,b]
  c.sort()
  alist.append(c)
clist=[[] for i in range(n)]
dlist=[0]*n
for i in alist:
  if i[1] not in clist[i[0]-1]: 
    clist[i[0]-1].append(i[1])
    dlist[i[0]-1]+=1
ans=[0]*(n+1)
for i in range(n-1,-1,-1):
  ans[i]=dlist[i]
  for j in clist[i]:
    ans[i]+=ans[j]
    ans[j]=0
print(max(ans))

Submission status: Wrong Answer

Solution code:
def resolve():
    n, m = map(int, input().split())
    s = [{j} for j in range(n)]
    for _ in range(m):
        a,b  = map(int, input().split())
        a-=1
        b-=1
        s[a].add(b)
        s[b].add(a)
    ans=0
    for i in range(len(s)):
        ans=max(len(s[i]),ans)
    print(ans)
resolve()

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = list()
B = list()
for _ in range(M):
    a, b = map(int, input().split())
    A.append(a-1)
    B.append(b-1)

largest = 0
group = [set([i]) for i in range(N)]
for a, b in zip(A, B):
    a, b = sorted([a, b])
    group[a].update(group[b])
    group[b] = group[a]
    group[a].add(b)

result = max([len(g) for g in group])
print(result)

Submission status: Wrong Answer

Solution code:
N, M=map(int,input().split())
groupnumber=[0 for i in range(N)]
grouplist=[]
counter=0
maxmembers=0
for i in range(M):
  a,b=map(int,input().split())
  a-=1
  b-=1
  if groupnumber[a]==0 and groupnumber[b]==0:
    counter+=1
    groupnumber[a]=counter
    groupnumber[b]=counter
    
    grouplist+=[[a,b]]
  elif groupnumber[a]==0 and groupnumber[b]!=0:
    groupnumber[a]=groupnumber[b]
    tmp=groupnumber[a]-1
    grouplist[tmp]+=[b]
    
  elif groupnumber[a]!=0 and groupnumber[b]==0:
    groupnumber[b]=groupnumber[a]
    tmp=groupnumber[b]-1
    grouplist[tmp]+=[a]
  else:
    if groupnumber[a]!=groupnumber[b]:
      tmp1=groupnumber[a]-1
      tmp2=groupnumber[b]-1
      if grouplist[tmp2]!=[] and grouplist[tmp2]!=[]:
        grouplist[tmp1]+=grouplist[tmp2]
        grouplist[tmp2]=[]
for i in grouplist:
  tmp=len(i)
  if tmp>maxmembers:
    maxmembers=tmp
print(maxmembers)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from collections import deque
from collections import Counter
import math

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

n,m = readInts()
root = [i for i in range(n+1)]
ab = []
for i in range(m):
	a,b = sorted(readInts())
	root[b] = root[a]



print(Counter(root).most_common(1)[0][1])

Submission status: Wrong Answer

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

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

G = {}
for i in range(M):
  ai, bi = map(int, readline().split())
  if ai in G:
    if type(G[ai]) is int:
      G[G[ai]].add(bi)
    else:
      G[ai].add(bi)
  elif bi in G:
    if type(G[bi]) is int:
      G[G[bi]].add(ai)
    else:
      G[bi].add(ai)
  else:
    G[ai] = {ai, bi}
    G[bi] = ai
ans = 1
for i in G:
  if type(G[i]) is not int:
    if len(G[i]) > ans:
      ans = len(G[i])
print(ans)

Submission status: Wrong Answer

Solution code:
def friends(arr):
    import collections
    graph = collections.defaultdict(set)
    for a in arr:
        graph[a[0]].add(a[1])
        graph[a[1]].add(a[0])
    maxi = 0
    for k,v in graph.items():
        maxi = max(maxi, len(v)+1)
    return maxi

def start():
    n,m = [int(x) for x in input().split(" ")]
    arr = []
    while m:
        arr.append([int(x) for x in input().split(" ")])
        m-= 1
    print(friends(arr))
start()

Submission status: Wrong Answer

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

friends = [0] * n
query = []

for i in range(m):
  a,b = map(int, input().split())
  if a > b:
    query.append((b, a))
  else:
    query.append((a,b))

good_query = list(map(list, set(map(tuple, query))))
tmp = 1
for i in good_query:

  if friends[i[0] - 1] == 0 and  friends[i[1] - 1] == 0:
    friends[i[0] - 1] = tmp
    friends[i[1] - 1] = tmp
    tmp += 1
  elif friends[i[0] - 1] == 0:
    friends[i[0] - 1] = friends[i[1] - 1]
  elif friends[i[1] - 1] == 0:
    friends[i[1] - 1] = friends[i[0] - 1]
  else:
    index_num = [n for n, v in enumerate(friends) if v == friends[i[0] - 1]]
    duplicated = friends[i[1] - 1]
    for i in index_num:
      friends[i] = duplicated

counted = collections.Counter(friends)
print(counted.most_common()[0][1])

Submission status: Wrong Answer

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

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

    for i in range(n):
        ab_list[i - 1] = set(ab_list[i - 1])

    ans = 0
    for l in ab_list:
        if len(l) > ans:
            ans = len(l)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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 = [0]+[len(i) for i in group]
    amari = done.count(-1)
    ans = max(people)
    if sum(people) > amari:
        print(ans)
    else:
        print(amari)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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

#AB = [tuple(map(int, input().split())) for i in range(M)]
#丸暗記。隣接リストの初期化
graph = [[i+1] for i in range(N)]

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

  if a not in graph[b-1]:
    graph[b-1].append(a)

ans = -1
for g in graph:
  ans = max(ans, len(g))
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
def solve():
  N,M = map(int,input().split())
  ABlist = [[0 for _ in range(2)] for _ in range(M)]
  WA = [0]*N
  for i in range(N):
    WA[i] = i+1
  for i in range(M):
    A, B = map(int,input().split())
    if A>B:
      A,B =B,A
    ABlist[i][0] = A
    ABlist[i][1] = B
  ABlist.sort(key=lambda x: (x[0],x[1]))
  for i in range(M):
    A = ABlist[i][0]
    B = ABlist[i][1]
    if WA[B-1]<WA[A-1]:
      WA[A-1] = WA[B-1]
    else:
      WA[B-1] = WA[A-1]
  c = collections.Counter(WA)
  print(c.most_common()[0][1])
solve()

Submission status: Wrong Answer

Solution code:
class UnionFind(): # 0インデックス
    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とyは-=1して使う
        '''
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

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

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

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

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

if __name__ == "__main__":
    N, M = map(int, input().split()) # N人、M個の関係
    union_find = UnionFind(N)
    for _ in range(M):
        A, B = map(int, input().split())
        A -= 1
        B -= 1
        union_find.union(A, B)

    group_dict = union_find.all_group_members()

    answer = 0
    l = len(union_find.all_group_members())
    print(l)
    for i in range(l):
        temp = union_find.size(i)
        answer = max(answer, temp)
    print(answer)

Submission status: Wrong Answer

Solution code:
# /usr/bin/python3
# -*- coding: utf-8 -*-
from queue import Queue
from queue import LifoQueue as Stack
from math import sqrt, floor, ceil, log2, log10, pi
from fractions import gcd
from itertools import permutations, combinations
from operator import itemgetter
from functools import cmp_to_key
from bisect import bisect_left


INF=1001001001
__MOD__=(10**9)+7
yn = 'YNeos'
judge = False
cnt = 0
ans = None


def lcm(a, b):
    return (a*b) // gcd(a,b)

def intinput():
    return int(input())

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

def lineinputs(func=intinput):
    datas = []
    while True:
        try:
            datas.append(func())
        except EOFError:
            break
    return datas

def bindex(a,x):
    i = bisect_left(a,x)
    if i != len(a) and a[i] == x:
        return i
    return None

class ModInt():
    def __init__(self, x):
        self.__x = (x % __MOD__)
    def __add__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x + other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x + other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __radd__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x + self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x + self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __sub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x - other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x - other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rsub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x - self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x - self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __mul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rmul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __truediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rtruediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __pow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(self.__x, other.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(self.__x, other.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")
    def __rpow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(other.__x, self.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(other.__x, self.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")

    def __modinv(self, m=__MOD__):
        a = self.__x
        if a == 0:
            raise ZeroDivisionError()
        if gcd(a, m) != 1:
            raise Exception("%sの逆数は求まりません。" % a)
        b, u, v = m, 1, 0
        while b != 0:
            t = a//b;
            a -= t*b
            a, b = b, a
            u -= t * v
            u, v = v, u
        u %= m
        if u < 0:
            u += m
        return u
    def __int__(self):
        return self.__x
    def __str__(self):
        return str(self.__x)



if __name__ == '__main__':
    N, M = mulinputs()
    if M == 0:
        print(1)
        exit()
    # b = []
    # first = True
    # for _ in range(M):
    #     A, B = input().split()
    #     is_match = False
    #     for s in b:
    #         if A in s or B in s:
    #             s.add(A)
    #             s.add(B)
    #             is_match = True
    #             break
    #     if not is_match:
    #         b.append(set([A,B]))
    b = [None] * (N+1)
    for _ in range(M):
        A, B = map(int,input().split())
        if not b[A] and b[B]:
            b[B].add(A)
            b[A] = b[B]
        elif b[A] and not b[B]:
            b[A].add(B)
            b[B] = b[A]
        elif not b[A] and not b[B]:
            t = set([A,B])
            b[A] = t
            b[B] = t
        else:
            b[A].add(B)
            b[B].add(A)
    # 出力
    ans = 0
    for bb in b:
        if not bb:
            continue
        ans = max(ans, len(bb))
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n, m = map(int, input().split())
L = []
for _ in range(m):
    a, b = map(int, input().split())
    if a > b:
        a, b = b, a
    L.append([a, b])
L.sort()

friends = [i for i in range(n + 1)]
for a, b in L:
    if friends[a] > friends[b]:
        friends[a] = friends[b]
    elif friends[a] < friends[b]:
        friends[b] = friends[a]
C = Counter(friends)
print(max(C.values()))

Submission status: Wrong Answer

Solution code:
import os

n,m = (int(x) for x in input().split())

if m==0:
    print(1)
    exit()

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

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
if m == 0:
    print(1)
    import sys
    sys.exit()

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

dist = [-1]*n
from collections import deque
q = deque([])

def bfs(vert,num):
    q.append(vert)
    while q:
        v = q.popleft()
        for i in graph[v]:
            if dist[i]!=-1:
                continue
            dist[i]=num
            q.append(i)


for j in range(n):
    if dist[j]==-1:
        bfs(j,j)

dist = list(dist)
from collections import Counter
e = Counter(dist)
print(e.most_common()[0][1])

Submission status: Wrong Answer

Solution code:
class Gr:
    def __init__(self, id):
        self.id = id

    def get_id(self):
        return self.id

    def set_id(self, id):
        self.id = id


def main():
    n, m = [int(e) for e in input().split()]
    AB = [[int(e) for e in input().split()] for i in range(m)]

    Gn = [None] * (n + 1)
    gid = 1
    for a, b in AB:
        if Gn[a] is None and Gn[b] is None:
            Gn[a] = Gr(gid)
            Gn[b] = Gr(gid)
            gid += 1
        elif Gn[a] is not None and Gn[b] is None:
            Gn[b] = Gr(Gn[a].get_id())
        elif Gn[a] is None and Gn[b] is not None:
            Gn[a] = Gr(Gn[b].get_id())
        else:
            Gn[b].set_id(Gn[a].get_id())

    C = [0] * (m + 1)
    for gn in Gn:
        if gn is not None:
            C[gn.get_id()] += 1

    print(max(C))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
par = [-1]*(n+1)
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x]) #経路圧縮
        return par[x]
def same(x,y):
    return find(x) == find(y)
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
      return 0
    else:
      if par[x] > par[y]:
        x,y = y,x
      par[x] += par[y]
      par[y] = x
def size(x):
    return -par[find(x)]

max_size=0
for _ in range(m):
  a,b=map(int,input().split())
  unite(a,b)
  max_size=max(size(b),max_size)

print(max_size)