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().strip().split())

dp=[0 for n in range(N)]
i=1
for _ in range(M):
    A,B=map(int,input().strip().split())
    if dp[A-1]==0 and dp[B-1]==0:
        dp[A-1]=i
        dp[B-1]=i
        i+=1
    else:
        if dp[A-1]!=0:
            dp[B-1]=dp[A-1]
        else:
            dp[A-1]=dp[B-1]

l=[0 for n in range(i)]
for n in range(N):
    if dp[n]!=0:
        l[dp[n]-1]+=1
print(max(l))

Submission status: Wrong Answer

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

members = [-1] * N

group_count = 0
groups = [0] * N
for m in range(M):
    A, B = map(int, input().split())
    A = A - 1
    B = B - 1
    if members[A]==-1 and members[B]==-1:
        members[A] = members[B] = group_count
        groups[group_count] = 2
        group_count += 1
    
    elif members[A]!=-1 and members[B]==-1:
        members[B] = members[A]
        groups[members[A]] += 1
    
    elif members[B]!=-1 and members[A]==-1:
        members[A] = members[B]
        groups[members[B]] += 1
    
    else:
        groups[members[A]] += groups[members[B]]
        groups[members[B]] = 0
        mA = members[A]
        mB = members[B]

        for idx, mem in enumerate(members):
            if mem == mB:
                members[idx] = mA

ans = max(groups)
if ans == 0:
    print(1)
else:
    print(ans)

Submission status: Wrong Answer

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

l = []  # 同値類のリスト
d = {}  # 各人がいるlのindex
tmp = 0

for i in range(M):
    A, B = map(int, input().split())
    if (d.get(A) == None) and (d.get(B) == None):
        d[A] = tmp
        d[B] = tmp
        tmp += 1
        l.append([A, B])
    elif (d.get(A) != None) and (d.get(B) == None):
        d[B] = d[A]
        l[d[A]].append(B)
    elif (d.get(A) == None) and (d.get(B) != None):
        d[A] = d[B]
        l[d[B]].append(A)
    else:
        continue

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

ans = max(ans, N - len(d))

print(ans)

Submission status: Wrong Answer

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

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

    for i in range( m ):
        a , b = map( int , input().split() )
        flag = 0
        for j in range( len(Sets) ):
            if a in Sets[j] or b in Sets[j]:
                Sets[j].add(a)
                Sets[j].add(b)
                flag = 1
                break
        if flag == 0:
            Sets.append( set([ a,b ]) )
    
    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 = [int(e) for e in input().split()]

d = {}

for i in range(m):
    a, b = [int(e) for e in input().split()]
    
    if a > b:
        a, b = b, a

    if not a in d:
        d[a] = set([a])
    d[a].add(b)
    if b in d:
        d[a].update(d[b])

    d[b] = d[a]

r = 0
for v in d.values():
    if len(v) > r:
        r = len(v)

print(r)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

node = [i for i in range(n)]
r = []
for _ in range(m):
   a, b = map(int, input().split())
   a, b = a-1, b-1
   if a > b:
      a, b = b, a
   r.extend([(a, b)])
r = set(r)
r = sorted(r, key=lambda x: x[0])

for a, b in r:
   x = min(node[a], a)
   node[a] = x
   node[b] = x

cnt = Counter(node)
print(cnt.most_common()[0][1])

Submission status: Wrong Answer

Solution code:
from collections import Counter
N, M = list(map(int, input().split()))
groups = {i:-1 for i in range(N)}
cnt = 0
for _ in range(M):
    a, b = list(map(int, input().split()))
    a-=1
    b-=1
    if groups[a]==-1 and groups[b]==-1:
        groups[a] = cnt
        groups[b] = cnt
        cnt+=1
    elif groups[a]!=-1:
        groups[b] = groups[a]
    elif groups[b]!=-1:
        groups[a] = groups[b]
for n,m in Counter(groups.values()).most_common():
    if n==-1:
        continue
    print(m)
    break

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
groups = [set(map(int, input().split())) for _ in range(M)]
new = []
ans = 1
already = set()
if M > 0:
    ans = 2
    new.append(groups[0])
    already |= groups[0]

for i in range(1, len(groups)):
    if len(already&groups[i]) == 0:
        new.append(groups[i])
    else:
        for j in range(len(new)):
            tmp = new[j]&groups[i]
            if len(tmp) > 0:
                new[j] |= groups[i]
                ans = max(ans, len(new[j]))
                break
    already |= groups[i]

print(ans)

Submission status: Wrong Answer

Solution code:
class union_find:
    def __init__(self, N):
        # 子なら親のインデックス、親ならunionのサイズを負数で格納
        self.par = [-1 for i in range(N)]
    
    def root(self, i):
        if self.par[i] < 0:
            return i
        else:
            # 経路圧縮
            self.par[i] = self.root(self.par[i])
            return self.par[i]
    
    def same(self, a, b):
        return self.root(a) == self.root(b)
    
    def unite(self, a, b):
        if not self.same(a, b):
            self.par[self.root(a)] += self.par[self.root(b)]
            self.par[b] = self.root(a)

N, M = list(map(int, input().split()))
UF = union_find(N)
for _ in range(M):
    A, B = list(map(lambda x: int(x) - 1, input().split()))
    UF.unite(A, B)
print(-min(UF.par))

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

AB = []
pos = [i for i in range(N)]
for _ in range(M):
    tmp = list(map(int,input().split()))
    tmp.sort()
    AB.append(tmp)

AB.sort()
for i in range(M):
    a,b = AB[i]
    if pos[b-1]>=pos[a-1]:
        pos[b-1] = pos[a-1]
    else:
        pos[a-1] = pos[b-1]

c = Counter(pos)
ans = c[0]
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

group_list = []

for i in range(M):
    a, b = input().split(" ")
    flag = False
    for s in group_list:
        
        if (a in s) or (b in s):
            s.add(a)
            s.add(b)
            flag = True
    if not flag:
        group_list.append(set([a, b]))

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

mat=[ set() for _ in range(n)]

for _ in range(m):
  a,b = map(int,input().split())
  a-=1
  b-=1
  mat[a].add(b)
  mat[b].add(a)
  
ans = 1
visited = [False]*n
count = 0
q = []
tmp = 0

while count < n:
  if len(q)==0:
    ans = max(ans,tmp)
    for i in range(n):
      if visited[i]==False:
        q.append(i)
        tmp = 1
        count +=1
        break
  
  st = q.pop(0)
  visited[st] = True
  
  for a in mat[st]:
    if visited[a] == False:
      q.append(a)
      tmp += 1
      count+=1
ans = max(ans,tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    dic = collections.defaultdict(set)
    for _ in range(M):
        a, b = il()
        dic[a].add(b)
        dic[b].add(a)
    ret = 0
    for k, v in dic.items():
        ret = max(ret, len(v) + 1)
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

# from typing import Optional
# from typing import List
# from typing import Dict
# from typing import Tuple
# from typing import Sequence


def main():
    args = input().split()
    N = int(args[0])
    M = int(args[1])

    groupList = list()
    # fSet = set()
    for i in range(M):
        args = list(map(lambda x: int(x), input().split()))
        # fSet.add(args)

        isHit = False
        for group in groupList:
            if args[0] in group:
                group.add(args[1])
                isHit = True
                break
            elif args[1] in group:
                group.add(args[0])
                isHit = True
                break

        if not isHit:
            groupList.append({args[0], args[1]})

    maxNum = 0
    for group in groupList:
        maxNum = max(maxNum, len(group))

    print(maxNum)


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())
  if a < b:
    li[a].append(b)
  else:
    li[b].append(a)
  
ans = 0
for i in range(1, N+1):
  l = li[i]
  for x in li[i]:
    for y in li[x]:
      if y == i:
        pass
      elif y in li[i]:
        pass
      else:
        l.append(y)
  ans = max(ans, len(set(l))+1)
print(ans)

Submission status: Wrong Answer

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

from collections import deque
 
def bfs():
  ans = 0
  done = set()
  for i in range(N):
    if i in done: continue
    queue = deque([i])
    num = 0
    while queue:
      p = queue.popleft()
      for p2 in F[p]:
        if p2 in done: continue
        done.add(p2)
        queue.append(p2)
        num += 1
    ans = max(ans,num)
  return ans
print(bfs())

Submission status: Wrong Answer

Solution code:
import numpy as np

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

ABs = [list(map(int, input().split())) for _ in range(M)]

#print(ABs)

checker = []
for _ in range(N):
    checker.append(set())

#for AB in ABs:
#    checker[AB[0] - 1].append(AB[1])
#    checker[AB[1] - 1].append(AB[0])


for AB in ABs:
    checker[AB[0] - 1].add(AB[1])
    checker[AB[1] - 1].add(AB[0])

checkerSet = []

for check in checker:
    checkerSet.append(set(check))

#print(checkerSet)

ans = 0

for anscheck in checkerSet:
    ans = max(ans, len(anscheck)+1)

print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
A=[0]*M
tomo=[0]*N
for i in range(M):
    A[i]=list(map(int,input().split()))
    if(A[i][1]<A[i][0]):
        temp=A[i][1]
        A[i][1]=A[i][0]
        A[i][0]=temp
A=list(map(list,set(map(tuple,A))))

for i in range(len(A)):

    tomo[A[i][0]-1]=tomo[A[i][0]-1]+1
    tomo[A[i][1]-1]=tomo[A[i][1]-1]+1

print(1+max(tomo))

Submission status: Wrong Answer

Solution code:
from collections import Counter
N, M = map(int,input().split())
par = []
rank = [0] * N
for i in range(N): par.append(i)
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: return 0
    if rank[x] < rank[y]: par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]: rank[x] += 1
def same(x,y):
    return find(x) == find(y)

for i in range(M):
    A, B = map(int,input().split())
    A -= 1
    B -= 1
    unite(A,B)
print(Counter(par).most_common()[0][1])

Submission status: Wrong Answer

Solution code:
import sys
import itertools
from pprint import pprint

if __name__ == '__main__':
    N, M = list(map(lambda x: int(x), sys.stdin.readline().split()))
    matrix = [[0 for i in range(N)] for j in range(N)]
    for _ in range(M):
        a, b = list(map(lambda x: int(x), sys.stdin.readline().split()))
        matrix[a-1][b-1] = 1
        matrix[b-1][a-1] = 1
    
    for i in range(N):
        x = []
        for j in range(N):
            if matrix[i][j] == 1:
                x.append(j)
        for p in range(len(x)):
            for q in range(p+1, len(x)):
                matrix[p][q] = 1
                matrix[q][p] = 1

    # つながっている最大のグラフを求めればいい
    print(max([sum(matrix[i]) for i in range(N)])+1)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
from math import floor, sqrt, factorial, hypot, log  # log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter, defaultdict, deque
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint


def ceil(a, b): return (a + b - 1) // b


inf = float('inf')
mod = 10 ** 9 + 7


def pprint(*A):
    for a in A:     print(*a, sep='\n')


def INT_(n): return int(n) - 1


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


def MF(): return map(float, input().split())


def MI_(): return map(INT_, input().split())


def LI(): return list(MI())


def LI_(): return [int(x) - 1 for x in input().split()]


def LF(): return list(MF())


def LIN(n: int): return [I() for _ in range(n)]


def LLIN(n: int): return [LI() for _ in range(n)]


def LLIN_(n: int): return [LI_() for _ in range(n)]


def LLI(): return [list(map(int, l.split())) for l in input()]


def I(): return int(input())


def F(): return float(input())


def ST(): return input().replace('\n', '')


def main():
    N, M = LI()
    par = [i for i in range(N + 1)]
    par_size = [1 for _ in range(N + 1)]
    def find(x):
        if par[x] == x:
            return x
        else:
            par[x] = find(par[x])
            return par[x]

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

    def unite(x, y):
        if same(x, y):
            return 0
        par[x] = find(y)
        par_size[find(y)] += 1
    for _ in range(M):
        A, B = LI()
        unite(A, B)
    ans = 0
    for p in par_size:
        ans = max(ans, p)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
class UnionFind:
  def __init__(self, n):
    self.parent = [i for i in range(n)]
    self.height = [0 for i 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_i] == self.height[root_j]:
          self.height[root_i] += 1
                
  def is_in_group(self, i, j):
    if self.get_root(i) == self.get_root(j):
      return True
    else:
      return False
          
N, M = map(int, input().split())
uf = UnionFind(N)
for i in range(M):
  a, b = map(int, input().split())
  uf.unite(a-1, b-1)
X = [0]*N
for i in range(N):
  X[uf.parent[i]] += 1
print(max(X)-1)

Submission status: Wrong Answer

Solution code:
n, m=map(int, input().split(" "))
a= [list(map(int, input().split(" "))) for i in range(m)]
fr = [[1]]
for i, j in a:
  for k in fr:
    if i in k:
      k.append(j)
      break
    elif j in k:
      k.append(i)
      break
    else:
      fr.append([i, j])
fr_set = []
maxi = 0
for i in fr:
  maxi = max(maxi, len(list(set(i))))
#print(fr, maxi)
print(maxi)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
par = [i for i in range(N+1)]
def find(x):
    if par[x] == x:
        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
    par[x] = y

ab = [list(map(int, input().split())) for _ in range(M)]
ab.sort()
for a,b in ab:
    unite(a,b)

from collections import Counter
ca = Counter(par[1:])
# print(par)
print(ca.most_common(1)[0][1])

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
count = [0] * n
for idx in range(m):
    a, b = map(int, input().split())
    if count[a - 1] != 0 and count[b - 1] != 0:
        pass
    else:
        count[a - 1] += 1
        count[b - 1] += 1

excluded_friends = count.count(0)
if excluded_friends > max(count):
    print(excluded_friends)
else:
    print(max(count) + 1)

Submission status: Wrong Answer

Solution code:
N,Q = map(int,input().split())
par = [i for i in range(N+1)]
rank = [0]*(N+1)
def find(x):
    if par[x] == x:
        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
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x]==rank[y]:rank[x]+=1

for i in range(Q):
    a,b = map(int,input().split())
    unite(a,b)

from collections import*
C=Counter(par)
print(max(C.values()))

Submission status: Wrong Answer

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

fr_set_list = []
for i in range(m):
    pair = input().split(" ")
    fr1 = int(pair[0])
    fr2 = int(pair[1])
    for j in range(len(fr_set_list)):
        if fr1 in fr_set_list[j] or fr2 in fr_set_list[j]:
            fr_set_list[j].add(fr1)
            fr_set_list[j].add(fr2)
            continue
    fr_set_list.append(set([fr1, fr2]))

max_len = 0
for fr_set in fr_set_list:
    if max_len < len(fr_set):
        max_len = len(fr_set)

print(max_len)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10*100)

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

Submission status: Wrong Answer

Solution code:
class Graph:
    def __init__(self,v):
        from collections import defaultdict
        self.v = v
        self.graph = defaultdict(list) 
        self.count = 0
        self.mx = 0

    def addEdge(self,a,b):
        if b in self.graph[a]:
            return
        if a in self.graph[b]:
            return
        self.graph[a].append(b)
        self.graph[b].append(a)

    def dfs(self,node,visited):
        if visited[node]:
            return self.count
        else:
            visited[node] = True
            self.count += 1
        
        for nbr in self.graph[node]:
            if not visited[nbr]:
                visited[nbr] = True
                self.count += 1
                self.dfs(node,visited)

    def solve(self):
        visited = [False]*(self.v+1)

        for i in range(1,self.v+1):
            if not visited[i]:
                self.dfs(i,visited)

            self.mx = max(self.mx, self.count)
            self.count = 0
        return self.mx

if __name__ == "__main__":
    n,m = map(int, input().split())
    
    g = Graph(n)
    for i in range(m):
        a,b = map(int, input().split())
        g.addEdge(a,b)
    
    print( g.solve() )

Submission status: Wrong Answer

Solution code:
m,n=map(int,input().split())
a_list=[0 for i in range(m)]
m_list=[]
for i in range(n) :
  a,b = map(int, input().split())
  if a>b :
    m_list.append(str(a)+str(b))
  else :
    m_list.append(str(b) + str(a))

m_list=list(set(m_list))

for s in m_list :
  a_list[int(s[0])-1]+=1
  a_list[int(s[1])-1]+=1




print(max(a_list)+1)

Submission status: Wrong Answer

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[a]=a

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

def union_set(a,b):
    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)
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)
# 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: Wrong Answer

Solution code:
N,M = map(int,input().split())
a = [0]*M
b = [0]*M
fri = []
fri2 = [[] for i in range(N)]
for i in range(M):
    a[i],b[i] = map(int, input().split())
    fri.append([min(a[i],b[i]),max(a[i],b[i])])
    fri2[a[i]-1].append(b[i])
    fri2[b[i]-1].append(a[i])

ans = 0

for j in range(N):
    temp = len(list(set(fri2[j])))
    ans = max(ans,temp)
    
print(ans+1)

Submission status: Wrong Answer

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 and friendlist[b]!=0:
        continue
    elif 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
maxa = 0
for i in range(n):
    count[friendlist[i]] += 1
    maxa = max([count[friendlist[i]],maxa])

print(maxa)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(m)]
for i in range(m):
    if ab[i][0] > ab[i][1]:
        t = ab[i][0]
        ab[i][0] = ab[i][1]
        ab[i][1] = t
ab.sort()

l = [i for i in range(n+1)]
for i in range(m):
    if l[ab[i][0]] > l[ab[i][1]]:
        l[ab[i][0]] = l[ab[i][1]]
    else:
        l[ab[i][1]] = l[ab[i][0]]

ans_l = [0 for i in range(n+1)]
for i in range(n+1):
    ans_l[l[i]] += 1

print(max(ans_l))

Submission status: Wrong Answer

Solution code:
from collections import Counter
N, M = list(map(int, input().split()))
groups = {i:-1 for i in range(N)}
cnt = 0
for _ in range(M):
    a, b = list(map(int, input().split()))
    a-=1
    b-=1
    if groups[a]==-1 and groups[b]==-1:
        groups[a] = cnt
        groups[b] = cnt
        cnt+=1
    elif groups[a]!=-1:
        groups[b] = groups[a]
    elif groups[b]!=-1:
        groups[a] = groups[b]

print(Counter(groups.values()).most_common()[0][1])

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())
    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:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

#bisect.bisect_left(list,key)はlistのなかでkey未満の数字がいくつあるかを返す
#つまりlist[i] < x となる i の個数
#bisect.bisect_right(list, key)はlistのなかでkey以下の数字がいくつあるかを返す
#つまりlist[i] <= x となる i の個数
#これを応用することで
#len(list) - bisect.bisect_left(list,key)はlistのなかでkey以上の数字がいくつあるかを返す
#len(list) - bisect.bisect_right(list,key)はlistのなかでkeyより大きい数字がいくつあるかを返す
#これらを使うときはあらかじめlistをソートしておくこと！
n,m = MI()
graph = [[j] for j in range(n+1)]
for i in range(m):
    a,b = MI()
    graph[a].append(b)
    graph[b].append(a)
ans = 0
for i in range(n+1):
  ans = max(ans,len(set(graph[i])))
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = (int(i) for i in input().split())
edges = {i:[] for i in range(N)}
for i in range(M):
    A, B = (int(i) for i in input().split())
    edges[A-1].append(B-1)
    edges[B-1].append(A-1)
result = 0
for i in range(N):
    nset = set()
    nodes = set(edges[i])
    for j in edges[i]:
        nodes = nodes | set(edges[j])
    result = max(result, len(nodes))
print(result)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
numbers=[set() for _ in range(N)]
for _ in range(M):
    a,b=map(int,input().split())
    A=sorted([a,b])
    numbers[A[0]-1].add(A[1]-1)
    numbers[A[1]-1].add(A[0]-1)
ans=1
suuji=0
for number in numbers:
    suuji=max(suuji,len(number))
print(ans+suuji)

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)]
j=1
shozoku=[0]*n
for i in range(m):
    if shozoku[ab[i][0]-1]==0:
        if shozoku[ab[i][1]-1]==0:
            shozoku[ab[i][0]-1]+=j
            shozoku[ab[i][1]-1]+=j
            f[j-1].append(ab[i][0])
            f[j-1].append(ab[i][1])
            j+=1
        else:
            shozoku[ab[i][0]-1]+=shozoku[ab[i][1]-1]
            f[shozoku[ab[i][1]-1]-1].append(ab[i][0])
    else:
        if shozoku[ab[i][1]-1]==0:
            shozoku[ab[i][1]-1]+=shozoku[ab[i][0]-1]
            f[shozoku[ab[i][0]-1]-1].append(ab[i][1])
ans=0
for i in range(n):
    ans=max(len(f[i]),ans)
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
friends = {}
for _ in range(m):
    a, b = map(int, input().split())
    friends.setdefault(a, []).append(b)
    friends.setdefault(b, []).append(a)
maxVal = 0
for value in friends.values():
    ans = len(set(value)) + 1
    maxVal = max(maxVal, ans)
print(maxVal)

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 = -math.inf
for i in b.keys():
    maxi = max(maxi, b[i])
print(maxi+1)

Submission status: Wrong Answer

Solution code:
from math import gcd, sqrt, cos, radians, pi, floor, ceil
from collections import defaultdict as d
from itertools import combinations as c
from string import ascii_lowercase as a

n, m = map(int, input().split())
dico = d(set)

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

visited = [0] * (n + 1) 
maxi = 0

for i in range(1, n + 1):
	if not visited[i]:
		u = dico[i]
		visited[i] = 1
		for v in dico[i]:
			u = u.union(dico[v])
			visited[v] = 1
		maxi = max(maxi, len(u))
		
print(maxi)