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:
# /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 = 1
    for bb in b:
        if not bb:
            continue
        ans = max(ans, len(bb))
    print(ans)

Submission status: Wrong Answer

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

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

ans = -1
for i in range(n):
    ans = max(len(set(groups[i]))+1, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import defaultdict
readline = stdin.readline
read = stdin.buffer.read
def r_map(): return map(int, readline().rstrip().split())
def r_list(): return list(r_map())

# import numpy as np
# from numba import jit

def main():
    N, M = r_map()
    p_dic = defaultdict(lambda: None)
    f_dic = defaultdict(lambda : 1)
    for _ in range(M):
        a, b = r_map()
        if a < b:
            if p_dic[a] is None:
                p_dic[a] = {b}
            else:
                p_dic[a].add(b)
        else:
            if p_dic[b] is None:
                p_dic[b] = {a}
            else:
                p_dic[b].add(a)
    for i in range(1 , N + 1):
        if p_dic[i] is None:
            continue
        l = list(p_dic[i])
        l.sort()
        for j in l:
            if p_dic[j] is None:
                p_dic[j] = p_dic[i].copy()
                p_dic[j].remove(j)
            else:
                p_dic[j] = p_dic[j].union(p_dic[i])
                p_dic[j].remove(j)
    ans = 1
    for i in range(1, N + 1):
        if p_dic[i] is None:
            continue
        l = list(p_dic[i])
        l.sort()
        for j in l:
            if f_dic[i] == f_dic[j]:
                f_dic[j] += 1
                ans = max(ans, f_dic[j])
    print(ans)

if __name__ == "__main__":
    main()

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

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

    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] = Gn[a]
            gid += 1
        elif Gn[a] is not None and Gn[b] is None:
            Gn[b] = Gn[a]
        elif Gn[a] is None and Gn[b] is not None:
            Gn[a] = Gn[b]
        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:
def main3():
    N, M = map(int, input().split())
    person = [set() for i in range(N)]

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

    ans = 0
    for i in range(N):
        ans = max(ans, len(person[i]) + 1)

    print(ans)

if __name__ == "__main__":
    main3()

Submission status: Wrong Answer

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

for _ in range(M):
  a,b = map(int,input().split())
  a,b = a-1, b-1
  e[a][b]=1
  e[b][a]=1
d=[0]*(N+1)
end_q=[]
def conn(s):
  q=[s]
  an=0
  while len(q)>0:
    qq=q.pop(0)
    d[qq]=1
    an+=1
    for i in range(N):
      if e[qq][i]==1 and d[i]==0:
        q.append(i)
  return an
ans=0
for a in range(N):
  if d[a]==1:
    continue
  else:
    ans=max(ans,conn(a))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

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


group_dict = defaultdict(lambda : None)
group_counter = 0
group_member = [0]*(n+1)

update_dict = defaultdict(lambda : None)

group = []
for i in range(m):
    a,b = friend_list[i]

    a_group = group_dict[a]
    b_group = group_dict[b]
    target_group = -1
    if a_group != None:
        target_group = a_group
    if b_group != None:
        target_group = b_group

    if target_group == -1:
        target_group = group_counter
        group_counter+=1

    if a_group != None and b_group != None:
        target_group = min(a_group,b_group)
        update_dict[max(a_group,b_group)] = min(a_group,b_group)
    
    group_dict[a] = target_group
    group_dict[b] = target_group


for k in group_dict:

    new_k = update_dict[group_dict[k]]
    prev = None
    while prev != new_k and new_k != None:
        prev = new_k
        new_k = update_dict[new_k]
    if prev != None:
        change = prev
    else:
        change = group_dict[k]
    group_member[change] += 1

print(max(group_member))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
class DisjointSet():
    def __init__(self, size):
        self.size = size
        self.rank = [None] * size
        self.parents = [None] * size
        for i in range(size):
            self.makeSet(i)

    def makeSet(self, x):
        self.parents[x] = x
        self.rank[x] = 0

    def findSet(self, x):
        if x != self.parents[x]:
            self.parents[x] = self.findSet(self.parents[x])
        return self.parents[x]

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

    def unite(self, x, y):
        self.link(self.findSet(x), self.findSet(y))

    def link(self, x, y):
        if self.rank[x] > self.rank[y]:
            self.parents[y] = x
        else:
            self.parents[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

N, M = map(int, input().split())
ds = DisjointSet(N)
for _ in range(M):
    a, b = map(int, input().split())
    ds.unite(a-1, b-1)

setdict = defaultdict(int)
for i in range(N):
    setdict[ds.findSet(i)] += 1

# clist = list(sorted(list(setdict.values())))
clist = set(setdict.values())
ans = 0
r = 0
for c in clist:
    ans += (c-r)
    r = c

# print(clist)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import collections
class DJS:
    def __init__(self, n):
        self.p = defaultdict(int)
        self.rank = defaultdict(int)
        for i in range(n):
            self.makeSet(i)

    def makeSet(self,x):
        self.p[x] = x
        self.rank[x] = 0

    def findSet(self,x):
        if x != self.p[x]:
            self.p[x] = self.findSet(self.p[x])
        return self.p[x]
    
    def unite(self, x, y):
        self.link(self.findSet(x),self.findSet(y))
    
    def link(self, x, y):
        if self.rank[x] > self.rank[y]:
            self.p[y] = x
        else:
            self.p[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1
        

    def same(self, x, y):
        return self.findSet(x) == self.findSet(y)
n,m = map(int,input().split())
djs = DJS(n)
for i in range(m):
    a,b = map(int,input().split())
    djs.unite(a-1,b-1)
tmp= collections.Counter(djs.p.values())
ret = max(list(tmp.values()))
print(ret)

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 not a in d:
        d[a] = set([a])
    if not b in d:
        d[b] = set([b])    

    if len(d[a]) > len(d[b]):
        d[a].update(d[b])
        d[a].add(b)
        for i in d[b] - d[a]:
            d[i] = d[a]
        d[b] = d[a]
    else:
        d[b].update(d[a])
        d[b].add(a)
        for i in d[a] - d[b]:
            d[i] = d[b]
        d[a] = d[b]

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

print(r)

Submission status: Wrong Answer

Solution code:
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 main():
    N, M = map(int, input().split())
    unf = UnionFind(N)
    for i in range(M):
        A, B = map(int, input().split())
        if not unf.same(A-1, B-1):
            unf.union(A-1, B-1)
    
    groups = unf.all_group_members()

    sizes = []
    for k, i in groups.items():
        sizes.append(len(groups[k]))
    
    group_nums = len(sizes)

    excessive_member = 0
    for s in sizes:
        excessive_member += max(s-group_nums, 0)
    
    if excessive_member == 0:
        print(max(sizes))
    else:
        print(group_nums+excessive_member)
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
par=[i for i in range(N+1)]
size=[1 for i in range(N+1)]
def find(x):
    if x!=par[x]:
        par[x]=find(par[x])
    return par[x]
def union(x,y):
    if find(x)!=find(y):
        par[y] = par[x]
        size[x] += size[y]
res=N
for i in range(M):
    s,e=map(int,input().split())
    union(s,e)
print(max(size))

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]=list(set(s[b]+s[a]))
        s[b]=list(set(s[a]+s[b]))
    ans=0
    for i in range(n):
        if i not in s[i]:
            ans=max(len(s[i])+1,ans)
        else:
            ans = max(len(s[i]), ans)
    print(ans)
resolve()

Submission status: Wrong Answer

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

from collections import defaultdict

# union find
class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n
 
    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x
 
    def find(self, x, y):
        return self._root(x) == self._root(y)
 
    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1

uf = UnionFind(N)

for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if a > b:
        c = b
        b = a
        a = c

    uf.union(a, b)

# member = defaultdict(int)
r = min(uf.table)
if r != -1:
    mm = abs(r)
    ic = 0
    for n in uf.table:
        if n == -1:
            ic += 1

    if ic%mm != 0:
        mm += 1
else:
    mm = 1

print(mm)

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)
    for f in friends[a]:
        friends[f].add(b)
        friends[b].add(f)
    for f in friends[b]:
        friends[f].add(a)
        friends[a].add(f)
   
for f in friends.values():
    len_f=len(f)
    if len_f > mx:
        mx=len_f
#print(friends)
print(mx)

Submission status: Wrong Answer

Solution code:
from collections import deque, defaultdict

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

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

vertexes = set()
edges = defaultdict(set)
for a, b in AB:
    edges[a].add(b)
    edges[b].add(a)
    vertexes.add(a)
    vertexes.add(b)

res = 0
while vertexes:
    v = vertexes.pop()
    compos = 1
    q = deque()
    q.append(v)
    while q:
        now = q.popleft()
        for neighbor in edges[now]:
            if neighbor in vertexes:
                vertexes.discard(neighbor)
                q.append(neighbor)
                compos += 1
    
    res = max(compos, res)

print(res)

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]
    ans = max(people)
    amari = done.count(-1)
    if amari >= ans:
        print(amari)
    else:
        print(ans)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
INF = 10**18
sys.setrecursionlimit(10**6)

def li():
    return [int(x) for x in input().split()]

N, M = li()
L = []
for i in range(M):
    a, b = sorted(li())
    L.append((a, b))

L = set(L)

cnts = [0] * (N+1)

for l in L:
    a, b = l
    cnts[a] += 1
    cnts[b] += 1
# print(cnts)
p = cnts.index(max(cnts))
# print(p)

others = []
for l in L:
    a, b = l
    if a == p:
        others.append(b)
    elif b == p:
        others.append(a)

anothers = []
for other in others:
    for l in L:
        a, b = l
        if a == other:
            anothers.append(b)
        elif b == other:
            anothers.append(a)

# print(others)
# print(anothers)

all = list(set(others + anothers))
if p in all:
    all.remove(p)
ans = len(all) + 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter
#import sys
#sys.setrecursionlimit(2*10**5)

input = lambda : sys.stdin.readline().rstrip()

def main(pairs, n, m):
    gids = [None] * (n+1)

    graph = {}
    for node in range(1, n+1):
        graph[node] = []

    for a, b in pairs:
        graph[a].append(b)

    first = True
    next_gid = 0
    for a in range(1, n+1):
        bs = graph[a]

        if first:
            first = False
            cur_gid = next_gid
            gids[a] = cur_gid
            next_gid += 1
        else:
            if gids[a] is None:
                cur_gid = next_gid
                gids[a] = cur_gid
                next_gid += 1
            else:
                cur_gid = gids[a]

        for b in bs:
            gids[b] = cur_gid


    #print("gids", gids)

    #def get_gid(in_i, cur_gid):
    #    gids[in_i] = cur_gid
    #    kids = graph[in_i]
    #    for kid in kids:
    #        if gids[kid] is None:
    #            get_gid(kid, cur_gid)


    #cur_gid = 0
    #for i in range(1, n+1):
    #    if gids[i] is None:
    #        get_gid(i, cur_gid)
    #        cur_gid += 1

    out = Counter(gids[1:]).most_common(1)[0][1]
    print(out)

if True:
    n, m = map(int, input().split(" "))
    pairs = set([tuple(sorted(map(int, input().split(" ")))) for i in range(m)])
else:
    import random
    n = random.randint(2, 2*10**5)
    m = random.randint(0, 2*10**5)
    pairs = set([tuple(sorted([random.randint(1, n), random.randint(1, n)])) for i in range(m)])

main(pairs, n, m)

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 and bi in G:
    G[ai] = G[ai] | G[bi]
    G[bi] = G[ai]
  elif ai in G:
    G[ai].add(bi)
    G[bi] = G[ai]
  elif bi in G:
    G[bi].add(ai)
    G[ai] = G[bi]
  else:
    G[ai] = {ai, bi}
    G[bi] = G[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:
# -*- coding: UTF-8 -*-

class UnionFind:
    def __init__(self, size):
        self.rank=[0]*size
        self.cc  =[0]*size
        self.par =[int(i) for i in range(size)]
        self.grp =size

    def find(self, x):
        if x==self.par[x]: return x

        self.par[x]=self.find(self.par[x])
        #print(self.par)
        return self.par[x]

    def same(self, x, y): #2つの頂点が同じグループであるかを判定する
        return self.find(x)==self.find(y)

    def unite(self, x, y): #辺で接続されている2つの頂点を投げて統合する
        x,y=self.find(x),self.find(y)
        if x==y:
            return

        self.grp-=1
        if self.rank[x]<self.rank[y]:
            self.par[x]=y
        else:
            self.par[y]=x
            if self.rank[x]==self.rank[y]:
                self.rank[x]+=1

    def gm(self):
        for i in self.par:
            self.find(i)
        for i in self.par:
            self.cc[i]+=1
#        print(self.par,self.cc)
        return max(self.cc)

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)
print(uf.gm())

Submission status: Wrong Answer

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

q = [0]*(n+1)

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

dist = [-1] * (n+1)
dist[0] = 0
dist[1] = 0

d = deque()
a = 0
for l,j in enumerate(q):
    b = set()
    if j == 0:
        d.append(l)
        while d:
            v = d.popleft()
            for i in graph[v]:
                b.add(i)
                if dist[i] != -1:
                    continue
                dist[i] = dist[v] + 1
                d.append(i)
                q[i] = -1
        a = max(a,len(b))

print(a)

Submission status: Wrong Answer

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

N,M= (int(x) for x in input().rstrip('\n').split())
f = {x:{x} for x in range(1,N+1)}
for _ in range(M):
  A,B = (int(x) for x in input().rstrip('\n').split())
  if f[A] != f[B]:
    f[A] |= f[B]
    f[B] = f[A]
print(max(len(x) for x in f.values()))

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:
a,b = list(map(int, input().split()))
friend_li = [[] for _ in range(a)]

result = 0

for i in range(b):
  c,d = list(map(int, input().split()))
  friend_li[c-1].append(d-1)
  friend_li[d-1].append(c-1)

for element in friend_li:
  len_ = len(list(set(element)))
  if len_ > result:
    result = len_
print(result+1)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
F = [[] for _ in range(N)]
for i in range(M):
    A,B = map(int,input().split())
    A -= 1
    B -= 1
    F[A].append(B)
    F[B].append(A)
a = [1 for _ in range(N)]
l = []
b = [0 for _ in range(N)]
for j in range(N):
    mem = 1
    a[j] = 0
    nex = F[j]
    for q in range(3):
        que = nex
        nex = []
        for k in que:
            if a[k] == 1:
                a[k] = 0
                mem += 1
                nex.extend(F[k])
        if nex == []:
            break
    l.append(mem)
print(max(l))

Submission status: Wrong Answer

Solution code:
def resolve():
    '''
    code here
    '''
    N, M = [int(item) for item in input().split()]

    edges = [[int(item) for item in input().split()] for _ in range(M)]
    links = [set() for _ in range(N+1)]

    res_list = [[] for i in range(N+1)]

    for a, b in edges:
        links[a].add(b)
        links[b].add(a)



    cnt = 1
    for i in range(1, N+1):
        for j in range(1, N+1):
            if i in res_list[j]:
                continue
            else:
                res_list[j] += [i]
                res_list[j] += links[i]
                break
                
    res = 0
    for item in res_list:
        if item:
            res += 1

    print(min(N, res +1))

        


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
import itertools
n, m = map(int, input().split())
f = []
if m == 0:
  ans = 1
else:
    d = {}
    for i in range(m):
      a, b = map(int, input().split())
      if a in d:
        f[d[a]].append(b)
        d[b] = d[a]
      elif b in d:
        f[d[b]].append(a)
        d[a] = d[b]
      else:
        f.append([a, b])
        d[a] = len(f) - 1
        d[b] = len(f) - 1
    arr = []
    for i in range(len(f)):
      arr.append(len(list(set(f[i]))))
    ans = max(arr)
print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
ans = 1
s = []
for i in range(n):
    s.append(set([i+1]))
if m == 0:
    print(1)
else:
    for i in range(m):
        a,b = map(int,input().split())
        s[a-1] = s[a-1]|s[b-1]
        s[b-1] = s[a-1]|s[b-1]
    for j in s:
        ans = max(ans,len(j))
    print(ans)

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

F = []
for i in range(M):
    a, b = [int(x) for x in input().split()]
    if a > b:
        a, b = b, a
    F.append([a, b])
F.sort()

for a, b in F:
    if a in grp:
        if b not in grp:
            grp[b] = grp[a]
            ngrp[grp[b]] += 1
            ret = max(ret, ngrp[grp[b]])
        else:
            if grp[a] != grp[b]:
                grp[a]
    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())
con = []
ans = 0
for i in range(m):
    check = True
    b,c = map(int,input().split())
    if i == 0:
        con.append([b,c])
    else:
        for i in range(len(con)):
            if b in con[i]:
                check = False
                if c in con[i]:
                    break
                else:
                    con[i].append(c)
                    break
            elif c in con[i]:
                check = False
                con[i].append(b)
                break
            
        if check:
            con.append([b,c])
for i in range(len(con)):
    ans = max(ans,len(con[i]))
print(ans)

Submission status: Wrong Answer

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

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

G = {}
for i in range(1, M):
  ai, bi = map(int, readline().split())
  if ai in G and bi in G:
    G[ai] = G[ai] | G[bi]
    G[bi] = G[ai]
  elif ai in G:
    G[ai].add(bi)
    G[bi] = G[ai]
  elif bi in G:
    G[bi].add(ai)
    G[ai] = G[bi]
  else:
    G[ai] = {ai, bi}
    G[bi] = G[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)