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:
import os
import sys
import math
import heapq
from decimal import *
from io import BytesIO, IOBase
from collections import defaultdict, deque

def r():
    return int(input())
def rm():
    return map(int,input().split())
def rl():
    return list(map(int,input().split()))

n,m = rm()
a = []
for i in range(m):
    a.append(rl())
b = defaultdict(int)
c = defaultdict(int)
visi = defaultdict(int)

for i in a:
    mi, ma = min(i[0], i[1]), max(i[0], i[1])
    if visi[(mi,ma)]==1:
        continue
    visi[(mi,ma)]=1
    if c[i[0]]==0 and c[i[1]]==0:
        c[i[0]]=i[0]
        c[i[1]]=i[0]
        b[i[0]]+=1
    elif c[i[0]]==0:
        c[i[0]]=c[i[1]]
        b[c[i[1]]]+=1
    elif c[i[1]]==0:
        c[i[1]]=c[i[0]]
        b[c[i[0]]]+=1
    elif c[c[i[0]]]!=c[c[i[1]]]:
        if b[c[c[i[0]]]]>b[c[c[i[1]]]]:
            b[c[c[i[0]]]]+=b[c[c[i[1]]]]+1
            b[c[c[i[1]]]]=0
            c[c[i[1]]]=c[c[i[0]]]
        else:
            b[c[c[i[1]]]]+=b[c[c[i[0]]]]+1
            b[c[c[i[0]]]]=0
            c[c[i[0]]]=c[c[i[1]]]

maxi = 0
for i in b.keys():
    maxi = max(maxi, b[i])
if maxi==0:
    print(0)
else:
    print(maxi+1)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
e = list(set([tuple(sorted(map(int, input().split()))) for _ in range(m)]))
e.sort()
g = {k: k for k in range(1, n+1)}
p = {k: 0 for k in range(1, n+1)}

for a, b in e:
  l = min([g[a], g[b]])
  g[a] = g[b] = l

for a, b in e[::-1]:
  l = min([g[a], g[b]])
  g[a] = g[b] = l
  
for v in g.values():
  p[v] += 1
  
print(max(p.values()))

Submission status: Wrong Answer

Solution code:
def main():
    N, M = [int(n) for n in input().split()]
    A = []
    B = []
    for m in range(M):
        tmp = [int(n) for n in input().split()]
        A.append(tmp[0])
        B.append(tmp[1])

    from collections import defaultdict

    d = defaultdict(set)

    for m in range(M):
        d[A[m]].add(B[m])
        d[B[m]].add(A[m])

    max_friends = 0
    for k, v in d.items():
        if len(v) > max_friends:
            max_friends = len(v)
    print(max_friends+1)

main()

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(key= lambda x : x[0])

friends = [i for i in range(n + 1)]
pre_a, pre_b = 0, 0
for a, b in L:
    if (pre_a, pre_b) != (a, b):
        friends[b] = friends[a]
    pre_a, pre_b = a, b
C = Counter(friends)
print(max(C.values()))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
M=set(tuple(map(int,input().split())) for _ in range(m))
d={i:set() for i in range(1,n+1)}

for a,b in M:
    d[a].add(b)
    d[b].add(a)
    d[a]|=d[b]
    d[b]|=d[a]

MAX = 0
for i in d.values():
    MAX=  max(MAX,len(i))
print(MAX)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
dict={}
for i in range(n):
    dict[i+1]=[]

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

max=0
for i in range(n):
    if len(set(dict[i+1])) > max:
        max=len(set(dict[i+1]))
    
print(max+1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

def main():

    input = sys.stdin.readline

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

    A = [0] * M
    B = [0] * M

    friend_list = [ set() for _ in range(N)]
    friend_list_len = 0

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

    for i in range(M):
        for j in range(friend_list_len):
            flag = False
            if A[i] in friend_list[j]:
                friend_list[j].add(B[i])
                flag = True
            if B[i] in friend_list[j]:
                friend_list[j].add(A[i])
                flag = True
            if flag:
                break                
        else:
            friend_list[friend_list_len].add(A[i])
            friend_list[friend_list_len].add(B[i])
            friend_list_len += 1

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

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

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

def unite(x, y):
  x = find(x)
  y = find(y)
  if x > y:
    par[x] = y
  else:
    par[y] = x
if M > 0:  
  for i in range(M):
    a, b = map(int, input().split())
    unite(a - 1, b - 1)
  
  ans = [0] * N
  Max = 0
  for i in par:
    ans[i] += 1
  for i in ans:
    if i > Max:
      Max = i
  
  print(Max)
else:
  print(1)

Submission status: Wrong Answer

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

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

group_list = []
inverted_dict = {}

for i in range(M):
    a, b = input().split(" ")
    flag = False
    if a in inverted_dict:
        idx = inverted_dict[a]
        group_list[idx].add(b)
    elif b in inverted_dict:
        idx = inverted_dict[b]
        group_list[idx].add(a)
    else:
        idx = len(group_list)
        inverted_dict[a] = idx
        inverted_dict[b] = idx
        group_list.append(set([a, b]))

max_group = 1
for g in group_list:
    max_group = max(max_group, len(g))
print(max_group)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
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)

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

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

direction = [-1]+[False]*n
d = defaultdict(set)

for i in range(m):
    a,b = map(int,input().split())
    if direction[a] == False and direction[b] == False:
        direction[a] = a
        direction[b] = a
        d[a].add(a)
        d[a].add(b)
    elif direction[a] == False:
        direction[a] = direction[b]
        d[direction[b]].add(a)
    elif direction[b] == False:
        direction[b] = direction[a]
        d[direction[a]].add(b)
    else:
        for j in d[b]:
            direction[j] = a
            d[a].add(j)
    # print(d)
maxi = 1
for alist in d.values():
    maxi = max(maxi,len(alist))
print(maxi)

Submission status: Wrong Answer

Solution code:
allsets = []
n,t = list(map(int,input().split()))
for _ in range(t):
    a,b = list(map(int,input().split()))
    if a < b and [a,b] not in allsets:
        allsets.append([a,b])
    elif b < a and [b,a] not in allsets:
        allsets.append([b,a])
# print(allsets)
hmap = {}
visitedNode = {}
for a,b in allsets:
    if a in visitedNode:
        if b not in hmap[visitedNode[a]]:
            hmap[visitedNode[a]].append(b)
        del visitedNode[a]
        continue
    if a in hmap:
        hmap[a].append(b)
        visitedNode[b] = a
    else:
        hmap[a] = [b]
        visitedNode[b] = a
# print(hmap)
res = 0
for k,v in hmap.items():
    res = max(res,len(v)+1)
print(res)

Submission status: Wrong Answer

Solution code:
n,m=list(map(int, input().split()))
a=[]
b=[]
for j in range(m):
    a1,b1=[int(j) for j in input().split()]
    a.append(a1)
    b.append(b1)
k=[[]for i in range(n)]
for i in range(m):
    x=a[i]-1
    y=b[i]-1
    k[x].append(y)
    k[y].append(x)
zz=0
for j in range(n):
    l=set(k[j])
    f=len(l)
    if f>zz:
        zz=f
print(zz+1)

Submission status: Wrong Answer

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


def root(a):
    if a == tree[a]:
        return a
    b = root(tree[a])
    tree[a] = b
    return tree[a]


def same(a, b):
    return root(a) == root(b)


def unite(a, b):
    if same(a, b):
        pass
    ra, rb = root(a), root(b)
    if ra > rb:
        ra, rb = rb, ra
    tree[rb] = ra


for _ in range(m):
    a, b = map(lambda x: int(x) - 1, input().split())
    unite(a, b)

d = {}
for t in tree:
    if t not in d:
        d[t] = 1
    else:
        d[t] += 1
ans = 0
for v in d.values():
    if v == 0:
        continue
    ans = max(ans, v)
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
	N, M = [int(n) for n in input().split(" ")]
	friends = []
	for i in range(M):
		a, b = [int(x) for x in input().split(" ")]
		m = min([a, b])
		M = max([a, b])
		friends.append({
			"min" : m,
			"max" : M
		})
	friends.sort(key=lambda f: (f["min"], f["max"]))
	group = [-1] * N
	for f in friends:
		M = f["max"]
		m = f["min"]
		if group[m - 1] == group[M - 1] == -1:
			group[M - 1] = m - 1
		elif group[m - 1] == -1 and group[M - 1] != -1:
			group[m - 1] = group[M - 1]
		elif group[m - 1] != -1 and group[M - 1] == 1:
			group[M - 1] = group[m - 1]
		else:
			group[M - 1] = group[m - 1]
	group_member = [0] * N
	for i in range(len(group)):
		if group[i] == -1:
			group_member[i] += 1
		else:
			group_member[group[i]] += 1
	print(max(group_member))

main()

Submission status: Wrong Answer

Solution code:
import collections
def solve():
  N,M = map(int,input().split())
  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
    WA[B-1] = WA[A-1]
  c = collections.Counter(WA)
  print(c.most_common()[0][1])
solve()

Submission status: Wrong Answer

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

def AddFriends(Alist):
  Fmap=[[0,0]]
  
  for A in Alist:
    a=A[0]
    b=A[1]
    
    NoPair=True
    
    for listF in Fmap:
      if a in listF:
        NoPair=False
        if b in listF:
          pass
        else:
          listF.append(b)
        break
          
      if b in listF:
        NoPair=False
        if a in listF:
          pass
        else:
          listF.append(a)
          
        break
    if NoPair:
      Fmap.append(A)
        
  return Fmap 
  

Fmap=AddFriends(Alist)
#print(Fmap)
maxLenF=2
 
for i in Fmap:
  if len(i)>maxLenF:
    maxLenF=len(i)
print(maxLenF)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
lst = [0] * N
num = 1
for i in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    if lst[A] != 0 and lst[B] != 0:     # 集合の結合(完全グラフ化)
        for j in range(N):
            if lst[j] == lst[B]:
                lst[j] = lst[A]
    elif lst[A] == 0 and lst[B] == 0:
        lst[A] = num
        lst[B] = num
        num += 1
    else:
        if lst[A] == 0:
            lst[A] = lst[B]
        else:
            lst[B] = lst[A]
    # print(A, B, lst)

cnt_lst = [0] * num
for i, value in enumerate(lst):
    cnt_lst[value] += 1
# print(cnt_lst)
ans = 0
for i, value in enumerate(cnt_lst):
    if i != 0: ans = max(ans, value)
print(ans)

Submission status: Wrong Answer

Solution code:

n,q=map(int,input().split())
parents=[i for i in range(n)]
deepth=[0 for _ in range(n)]
dict={}

def find(x):
    if parents[x]==x:
        return x
    return find(parents[x])

def unite(x,y):
    px=find(x)
    py=find(y)
    if deepth[px]>deepth[py]:
        parents[py]=px
        deepth[px]=max(deepth[px],deepth[py]+1)
    else:
        parents[px]=py
        deepth[py]=max(deepth[py],deepth[px]+1)

def same(x,y):
    if find(x)==find(y):
        return True
    else:
        return False

for _ in range(q):
    x,y=map(int,input().split())
    if same(x-1,y-1):
        continue
    else:
        unite(x-1,y-1)
    
ans=0
for i in range(n):
    if parents[i] in dict:
        dict[parents[i]]+=1   
    else:
        dict[parents[i]]=1
    ans=max(ans,dict[parents[i]])

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from collections import deque


def main():
    N, M = map(int, input().split())
    A = [0] * M
    B = [0] * M

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

    friends = defaultdict(set)

    for i in range(M):
        a, b = A[i], B[i]
        friends[a].add(b)
        friends[b].add(a)

    seen = [False] * N
    trees = []

    def dfs(start):
        todo = deque([start])
        cnt = 0
        while len(todo) > 0:
            v = todo.pop()
            cnt += 1
            for next_v in friends[v]:
                if seen[v]:
                    continue
                else:
                    todo.append(next_v)
                    seen[next_v] = True

        return cnt

    for v in range(N):
        if seen[v]:
            continue
        else:
            c = dfs(v)
            trees.append(c)

    # print(trees)
    print(max(trees))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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 li[i]:
    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: Wrong Answer

Solution code:
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(m)]
f=[[] for i in range(n)]
for  i in range(m):
    if ab[i][1] in f[ab[i][0]-1]:
        pass
    else:
        f[ab[i][0]-1].append(ab[i][1])
    if ab[i][0] in f[ab[i][1]-1]:
        pass
    else:
        f[ab[i][1]-1].append(ab[i][0])
ans=0
for i in range(n):
    ans=max(len(f[i]),ans)
print(ans+1)

Submission status: Wrong Answer

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]:
            if i in d: 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: Wrong Answer

Solution code:
from collections import deque

N,M=map(int,input().split())
rinsetu=[set() for _ in range(N+1)]
for i in range(M):
    a,b=map(int,(input().split()))
    rinsetu[a].add(b)
    rinsetu[b].add(a)

grp=[]
color=["white"]*(N+1)
color[0]="black"
for i in range(1,N+1):
    if color[i]=="white":
        d = deque()
        d.append(i)
        a = set()
        a.add(i)
        while(d):
            k=d.popleft()
            color[k]="black"
            for j in rinsetu[k]:
                if color[j]=="white":
                    d.append(j)
                    a.add(j)
        grp.append(a)
print(len(max(grp)))

Submission status: Wrong Answer

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

ls=[[] for i in range(n+1)]
for i in range(m):
    a,b = map(int, input().split())
    ls[a].append(b)
    ls[b].append(a)

ans=0
for i in ls:
    ans=max(ans,len(set(i)))
print(ans+1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n,m = map(int,input().split())
flist = list()
for i in range(m):
  flist.append(list(map(int,input().split())))
G = defaultdict(set)
for f in flist:
    if len(G.keys())== 0:
        G[f[0]].add(f[0])
        G[f[0]].add(f[1])
    else:
        for i in range(len(G.keys())):
            tmp_ = list(G.keys())[i]
            if f[0] in G[tmp_] or f[1] in G[tmp_]:
                G[tmp_].add(f[0])
                G[tmp_].add(f[1])
                break
            elif i == len(G.keys()) - 1:
                G[f[0]].add(f[0])
                G[f[0]].add(f[1])
ret = -1
for k in G.keys():
    ret = max(len(G[k]),ret)
print(ret)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(m)]
d={k:set() for k in range(1,n+1)}
for a,b in l:
    for v in d[a]^{b}:
        d[v].add(b)
    d[a].add(b)
    for v in d[b]^{a}:
        d[v].add(a)
    d[b].add(a)
ans=0
for s in d.values():
    print(s)
    ans=max(ans,len(s))
print(ans)

Submission status: Wrong Answer

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

def main():
    n , m = map( int, input().split() )
    Sets = []

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

    for i in range( m ):
        a , b = map( int , input().split() )
        if Dicto[a] == -1 and Dicto[b] == -1:
            Sets.append( set( [a,b] ) )
            x_i = len(Sets)
            Dicto[ a ] = x_i - 1
            Dicto[ b ] = x_i - 1
        elif Dicto[ a ] != -1:
            Sets[ Dicto[a] ].add( b )
        elif Dicto[ b ] != -1:
            Sets[ Dicto[b] ].add( a )
    
    max_len = 0

    for i in range( len(Sets) ):
        if max_len < len( Sets[i] ):
            max_len = len( Sets[i] )

    print(max_len)


main()

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
e = list(set([tuple(sorted(map(int, input().split()))) for _ in range(m)]))
e.sort()
g = {k: k for k in range(1, n+1)}
p = {k: 0 for k in range(1, n+1)}

for a, b in e:
  l = min([g[a], g[b]])
  g[a] = g[b] = l

for v in g.values():
  p[v] += 1
  
print(max(p.values()))

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

    # 出力
    ans = 0
    for bb in b:
        ans = max(ans, len(bb))
    print(ans)

Submission status: Wrong Answer

Solution code:
N, M = [int(i) for i in input().split()]
L = []
for i in range(M):
  a, b = [int(j) for j in input().split()]
  for j in range(len(L)):
    ifa = a in L[j]
    ifb = b in L[j]
    if (not ifb) and ifa:
      L[j].append(b)
      break
    elif (not ifa) and ifb:
      L[j].append(a)
      break
    elif ifa and ifb:
      break
  else:
    L.append([a, b])

lenmax = 0
for i in range(len(L)):
  if lenmax < len(L[i]):
    lenmax = len(L[i])
print(lenmax)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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


n, m = map(int, input().split())
uf = UnionFind(n)
for _ in range(m):
    a, b = map(lambda x: int(x) - 1, input().split())
    uf.union(a, b)

max_group = 0
for f in uf.parents:
    max_group = max(max_group, abs(f))
print(max_group)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
def main():
    from collections import deque

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

    seen = [False] * N
    friends_group = []
    for i in range(N):
        q = deque([i])
        tmp_group = [i]
        while q:
            now = q.popleft()
            if seen[i]:
                continue
            seen[now] = True
            for j in friends_input[now]:
                if not seen[j]:
                    q.append(j)
                    tmp_group.append(j)
        friends_group.append(tmp_group)
    ans = 0
    for i in friends_group:
        ans = max(ans, len(i))
    print(ans)
    # print(friends_group)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque

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

graph = defaultdict(set)
visited = set()
result = []

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

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

# print(graph)

def dfs(node, vis):
	stack = [node]

	while stack:
		node = stack.pop()

		vis.add(node)
		visited.add(node)

		for nbrs in graph[node]:
			if nbrs not in vis:
				visited.add(nbrs)
				vis.add(nbrs)

	return vis


for i in range(1, n+1):
	if i not in visited:
		vis = dfs(i, set())
		result.append(vis)


answer = max(result, key=len)

# print(f'{result=} {len(answer)=}')
print(len(answer))

Submission status: Wrong Answer

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

friends = [0] * n
query = []

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):
  a,b = map(int, input().split())
  if a > b:
    query.append((b, a))
  else:
    query.append((a,b))

good_query = get_unique_list(query)
for i in good_query:
  friends[i[0] - 1] += 1
  friends[i[1] - 1] += 1

print(max(friends)+1)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
F=[-1 for _ in range(N)]
G=[]

for i in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    if F[a]==-1 and F[b]==-1:
        G.append([a,b])
        F[a]=F[b]=len(G)-1
    elif F[a]==-1 and F[b]!=-1:
        F[a]=F[b]
        G[F[b]].append(a)
    elif F[a]!=-1 and F[b]==-1:
        F[b]=F[a]
        G[F[a]].append(b)
    else:
        if F[a]!=F[b]:

            G[F[a]]+=G[F[b]]
            for g in G[F[b]]:
                F[g]=F[a]
ans=0
for j in G:
    ans=max(ans,len(j))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
def input(): return sys.stdin.readline().rstrip()


def main():
    n, m = map(int, input().split())
    li = {}
    if m == 0:
        print(n)
        return

    for _ in range(m):
        a, b = sorted(map(int, input().split()))
        if a not in li:
            li[a] = {b}
        else:
            li[a].add(b)
    i = max(li, key=lambda k: len(li[k]))
    print(len(li[i]) + 1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
F = {}
for _ in range(M):
    A, B = map(int, input().split())
    if not A in F.keys():
        F[A] = []
    if not B in F.keys():
        F[B] = []
    F[A].append(B)
    F[B].append(A)
ans = 0
for f in F.values():
    ans = max(ans, len(list(set(f)))+1)
print(ans)

Submission status: Wrong Answer

Solution code:
def main(N, M, C):
    lst = [set() for n in range(N)]
    for c in C:
        lst[c[0]-1].add(c[1])
        lst[c[1]-1].add(c[0])
    print(max({len(st) for st in lst})+1)


if __name__ == '__main__':
    N, M = list(map(int, input().split()))
    C = set()
    for _ in range(M):
        C.add(tuple(map(int, input().split())))
    main(N, M, C)

Submission status: Wrong Answer

Solution code:
from collections import *
n,m=map(int,input().split())
if(m==0):
    print(0)
else:
    f={}
    d=[]
    for i in range(m):
        l=list(map(int,input().split()))
        q=sorted(l)
        r=tuple(q)
        if(r not in f):
            f[r]=1
            d.append(q)
    dd=defaultdict(int)
    for i in d:
        dd[i[0]]+=1
        dd[i[1]]+=1
    k=max(dd.values())
    print(k+1)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,m=map(int,input().split())
d={}
ans=0
for i in range(m):
  a,b=map(int,input().split())
  if a in d:
    d[a].append(b)
  else:
    d[a]=deque([b])
  if b in d:
    d[b].append(a)
  else:
    d[b]=deque([a])
for i in d.values():
  ans=max(len(list(set(i))),ans)
print(ans+1)

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
frnd = [set([i]) for i in range(n+1)]
mx = 0
for _ in range(m):
  f1,f2 = map(int, input().split())
  frnd[f1] |= frnd[f2]
  frnd[f2] |= frnd[f1]
  mx = max(mx,len(frnd[f1]))
  for i in frnd[f1]-set([f1,f2]):
    frnd[i] |= frnd[f1]
print(mx)