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:
# -*- 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.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)
b=[1]*n
ans=0
print(uf.gm())

Submission status: Wrong Answer

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

print(ret)

Submission status: Wrong Answer

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

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

friend.sort()

for a, b in friend:
  group_idx[b - 1] = group_idx[a - 1]

groups = [0 for i in range(n)]

for i in range(n):
  groups[group_idx[i]] += 1

print(max(groups))

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

AB = []
lst = [0] * (N + 1)


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

    AB.append((a, b))

AB.sort(key=lambda x: (x[0], x[1]))

c = 0
for a, b in AB:
    if lst[a] == 0 and lst[b] == 0:
        c += 1
        lst[a] = c
        lst[b] = c
    elif lst[a] != 0:
        x = lst[a]
        lst[b] = x
    elif lst[b] != 0:
        x =lst[b]
        lst[a] = x


counter = Counter(lst[1:])
max_ = 0
for v in counter.values():
    max_ = max(max_, v)

print(max_)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
s2t = defaultdict(list)

humans, links = input().split(" ")
for i in range(int(links)):
  s, t = input().split(" ")
  s2t[s].append(t)

print(2)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
d = {}
for i in range(1,N+1):
    d[i] = []
for i in range(M):
    A,B = map(int,input().split())
    d[A].append(B)
    d[B].append(A)
ans = 0
for a in range(1,N+1):
    ans = max(ans,len(list(set(d[a]))))
print(ans+1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
check = [0] * (N+1)
friends = [set()]
counter = 0
for i in range(M):
    A,B = map(int,input().split())
    if check[A] == 0 and check[B] == 0:
        counter += 1
        check[A] = counter
        check[B] = counter
        friends.append(set([A,B]))
    else:
        if check[A] == 0:
            check[A] = check[B]
            friends[check[B]].add(A)
        elif check[B] == 0:
            check[B] = check[A]
            friends[check[A]].add(B)
        elif A != B:
            if len(friends[check[A]]) > len(friends[check[B]]):
                friends[check[A]] = friends[check[A]] | friends[check[B]]
                for p in friends[check[B]]:
                    check[p] = check[A]
            else:
                friends[check[B]] = friends[check[A]] | friends[check[B]]
                for p in friends[check[A]]:
                    check[p] = check[B]
m = 0
for f in friends:
    if len(f) > m:
        m = len(f)
print(m)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
line = [[] for i in range(N)] # 
for i in range(M):
    x,y = map(int,input().split())
    line[x-1].append(y-1)
    line[y-1].append(x-1)
output = 1
for i in range(N):
    if len(set(line[i])) > output:
        output = len(set(line[i]))
print(output+1)

Submission status: Wrong Answer

Solution code:
import sys


inint = lambda: int(sys.stdin.readline())
inintm = lambda: map(int, sys.stdin.readline().split())
inintl = lambda: list(inintm())
instrm = lambda: map(str, sys.stdin.readline().split())
instrl = lambda: list(instrm())

n, m = inintm()

p = [0]*(n+1)

ans = 0

for i in range(m):
    a, b = inintm()
    if p[a] == 0 and p[b] == 0:
        if ans == 0:
            ans += 2
        p[a] = 1
        p[b] = 1
    elif (p[a] == 1 and p[b] == 0) or (p[a] == 0 and p[b] == 1):
        ans += 1
        p[a] = 1
        p[b] = 1

print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
ans = [[set(),0]]
count = 1
spe = set()
for j in range(M):
    A_j, B_j = map(int, input().split())
    for i in range(len(ans)):
        if A_j not in spe and B_j not in spe:
            ans.append([{A_j, B_j}, 2])
            spe.add(A_j)
            spe.add(B_j)
            count = max(count, ans[-1][1])
            break
        if A_j in ans[i][0] or B_j in ans[i][0]:
            if A_j not in ans[i][0]:
                ans[i][1] += 1
            if B_j not in ans[i][0]:
                ans[i][1] += 1
            ans[i][0].add(A_j)
            ans[i][0].add(B_j)
            spe.add(A_j)
            spe.add(B_j)
            count = max(count, ans[i][1])
            break
print(count)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
 
AB = [list(map(int, input().split())) for _ in range(M)]
 
friend = list()
for a, b in AB:
  a_set = -1
  b_set = -1
  a_f = False
  b_f = False
  for i, f in enumerate(friend):
    if a in f:
      a_set = i
      a_f = True
      if b_f:
        break
    elif b in f:
      b_set = i
      b_f = True
      if a_f:
        break
  if a_set == b_set == -1:
    friend.append({a, b})
  elif a_set == -1:
    friend[b_set].add(a)
  elif b_set == -1:
    friend[a_set].add(b)
  else:
    friend[a_set] = friend[a_set] | friend[b_set]
    friend.pop(b_set)

ans = 0
for f in friend:
  ans = max(len(f), ans)
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N, M = [int(n) for n in input().split()]
    from collections import defaultdict
    d = defaultdict(set)
    for m in range(M):
        a, b = [int(n) for n in input().split()]
        d[a].add(b)
        d[b].add(a)
        for f in d[a]:
            d[b].add(f)
        for f in d[b]:
            d[a].add(f)

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

main()

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 = max(a_group,b_group)
        update_dict[min(a_group,b_group)] = max(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 new_k != None:
        change = prev
    else:
        change = group_dict[k]
    group_member[change] += 1

print(max(group_member))

Submission status: Wrong Answer

Solution code:
# union find, bfs

import sys
from collections import deque
si = sys.stdin.readline


def main():
    [n, m] = [int(e) for e in si().split()]
    if not m:
        print(n)
        return

    visited = [False]*(n+1)
    fm = [set() for _ in range(n+1)]
    mx, comp = 0, 0

    while m:
        m -= 1
        [a, b] = [int(e) for e in si().split()]
        fm[a].add(b)
        fm[b].add(a)

    for i in range(1, n+1):
        if visited[i]:
            continue
        visited[i] = True
        comp += 1
        q = deque()
        q.append(i)
        cnt = 1
        while q:
            curr = q.popleft()
            for e in fm[curr]:
                if not visited[e]:
                    visited[e] = True
                    q.append(e)
                    cnt += 1
        mx = max(mx, cnt)
    if comp == n:
        print(1)
    else:
        print(mx)

if __name__ == '__main__':
    main()

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 m in range(M):
        C.add(tuple(map(int, input().split())))
    main(N, M, C)

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)

maxi = 1

for i in range(1, n + 1):
	maxi = max(maxi, len(dico[i]) + 1)
		
print(maxi)

Submission status: Wrong Answer

Solution code:
from typing import Set, List, Dict

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

G: List[Set[int]] = []
lookup_tab: Dict[int, int] = {}
for _ in range(M):
    a, b = map(int, input().split())
    if a not in lookup_tab and b not in lookup_tab:
        G.append({a, b})
        lookup_tab[a] = len(G) - 1
        lookup_tab[b] = len(G) - 1
    elif a in lookup_tab and b not in lookup_tab:
        gid = lookup_tab[a]
        lookup_tab[b] = gid
        G[gid].add(b)
    elif b in lookup_tab and a not in lookup_tab:
        gid = lookup_tab[b]
        lookup_tab[a] = gid
        G[gid].add(a)

if G:
    print(max([len(g) for g in G]))
else:
    print(1)

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] == lst[B]:
        pass
    elif 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:
from collections import defaultdict

def dfs(node):
    if node in visited:
        return False
    visited.add(node)
    for neighbor in adj_list[node]:
        dfs(neighbor)
    return True

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

A, B = [], []

adj_list = defaultdict(set)
visited = set([])

count = 0

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

#for node in range(1, N+1):
#    if dfs(node):
#        count += 1

print(max(map(lambda x: len(x)+1, adj_list.values())) if adj_list else N)

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).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, 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')


class UnionFind:
    def __init__(self, N):
        self.tree = list(range(N))

    def root(self, N):
        if self.tree[N] == N:
            return N
        else:
            self.tree[N] = self.root(self.tree[N])
            return self.tree[N]

    def same(self, x, y):
        return self.root(self.tree[x]) == self.root(self.tree[y])

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.tree[x] = y


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

    N, M = il()
    uf = UnionFind(N)
    for _ in range(M):
        a, b = il()
        a -= 1
        b -= 1
        uf.unite(min(a, b), max(a, b))
    print(max(collections.Counter(uf.tree).values()) + 1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
union = []
sets = []
for i in range(n+1):
    union.append(i)
    sets.append({i})
 
def root(n):
    global union
    if union[n] == n:
        return n
    res = union[union[n]]
    union[n] = res
    return res
 
def isSameRoots(n, m):
    nRoot = root(n)
    mRoot = root(m)
    return nRoot == mRoot
 
def unit(n, m):
    global union
    global sizeU
    global sets
    nRoot = root(n)
    mRoot = root(m)
    sets[nRoot] = sets[nRoot] | sets[mRoot]
    union[mRoot] = root(nRoot)
 
for i in range(m):
    inA, inB = map(int, input().split())
    aaa = min(inA, inB)
    bbb = max(inA, inB)
    if not isSameRoots(aaa, bbb):
        unit(aaa, bbb)
ans = 0
for i in range(1, n+1):
  ans = max(len(sets[root(i)]), ans)
print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
lis = [i for i in range(n)]
li = [sorted(list(map(int,input().split()))) for i in range(m)]
li.sort(key=lambda x:x[1])
li.sort(key=lambda x:x[0])
for i in range(m):
    a = li[i][0]-1
    b = li[i][1]-1
    lis[a] = min(lis[a],lis[b])
    lis[b] = min(lis[a],lis[b])
ans = 0
cnt = 1
lis.sort()
for i in range(n-1):
    if lis[i] == lis[i+1]:
        cnt += 1
    else:
        ans = max(ans,cnt)
        cnt = 1
print(max(ans,cnt))

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
a =[0] * (2*10**5+1)
con = []
ans = 0
for i in range(m):
    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]:
                if c in con[i]:
                    continue
                else:
                    con[i].append(c)
            elif c in con[i]:
                if b in con[i]:
                    continue
                else:
                    con[i].append(b)
            else:
                con.append([b,c])
            ans = max(ans,len(con[i]))
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

members = np.array([-1] * N).astype(np.int)

group_count = 0
groups = [0] * N
group_dict = {}
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_dict[group_count] = [A, B]
        group_count += 1
    
    elif members[A]!=-1 and members[B]==-1:
        members[B] = members[A]
        groups[members[A]] += 1
        group_dict[members[A]].append(B)
    
    elif members[B]!=-1 and members[A]==-1:
        members[A] = members[B]
        groups[members[B]] += 1
        group_dict[members[B]].append(A)
    
    else:
        if members[A] != members[B]:
            groups[members[A]] += groups[members[B]]
            groups[members[B]] = 0
            group_dict[members[A]] = group_dict[members[A]] +  group_dict[members[B]]
            group_dict[members[B]] = []
            members[group_dict[members[B]]] = members[A]

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

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
freind = set()
freindlist = []
for i in range(M):
    A,B = map(int,input().split())
    if A not in freind and B not in freind:
        freind.add(A)
        freind.add(B)
        freindlist.append({A,B})
    elif A in freind:
        freind.add(B)
        for i in range(len(freindlist)):
            if A in freindlist[i]:
                freindlist[i].add(B)
    elif B in freind:
        freind.add(A)
        for i in range(len(freindlist)):
            if B in freindlist[i]:
                freindlist[i].add(A)
Answer = 0
for i in range(len(freindlist)):
    j = len(freindlist[i])
    Answer = max(Answer, j)
print(Answer)

Submission status: Wrong Answer

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

g = [0]*N
n = [0]*N

num = 1

for i in range(len(c)):
    
    if g[c[i][0]-1] != 0 and g[c[i][1]-1] != 0:
        pass
    elif g[c[i][0]-1] != 0:
        g[c[i][1]-1] = g[c[i][0]-1]
        n[g[c[i][0]-1]-1] += 1
    elif g[c[i][1]-1] != 0:
        g[c[i][0]-1] = g[c[i][1]-1]
        n[g[c[i][1]-1]-1] += 1
    else:
        g[c[i][0]-1] = num
        g[c[i][1]-1] = num
        n[num-1] += 2
        num += 1

print(max(n) or 1)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n, m = [int(i) for i in input().split()]
people = [-1] * n
num = 1
ab = [0] * m

for i in range(m):
    ab[i] = [int(i) for i in input().split()]

ab.sort()

for a, b in ab:
    a -= 1
    b -= 1
    if people[a] == -1 and people[b] == -1:
        people[a] = num
        people[b] = num
        num += 1
    elif people[a] == -1 or people[b] == -1:
        if people[a] == -1: people[a] = people[b]
        else: people[b] = people[a]

ab = [i for i in ab if i != -1]
print(max(Counter(people).values()))

Submission status: Wrong Answer

Solution code:
import math
import itertools
import sys


n, m = map(int, input().split())
ans = 0
li = [[] for i in range(n)]
print(li)
for i in range(len(li)):
    li[i].append(i+1)
for i in range(m):
    a, b = map(int, input().split())
    for j in li:
        if(a in j and b not in j):
            j.append(b)
        if(b in j and a not in j):
            j.append(a)
for i in li:
    ans = max(ans, len(i))
print(ans)

Submission status: Wrong Answer

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

F = {v: [] for v in range(1, N+1)}

for f in AB:
    a = f[0]
    b = f[1]
    F[a].append(b)
    F[b].append(a)

groups = []

p = [-1 for _ in range(N+1)]
p[0] = 0
ans = 0

for i in range(1, N+1):
    if p[i] == 1:
        continue
    p[i] = 1
    group = [i]
    for j in F[i]:
        p[j] = 1
        if j not in group:
            group.append(j)
    ans = max(ans, len(group))
#print(p)
print(ans)

Submission status: Wrong Answer

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

xs=[-1]*n

abs = set()
for _ in range(m):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    abs.add((a,b))
    abs.add((b,a))
abs = sorted(list(abs), key=lambda x:x[0])

ma = {}
for a,b in abs:
    if xs[a] == -1 and xs[b] == -1:
        min_ = min(a,b)
        xs[a] = min_
        xs[b] = min_
        if min_ not in ma:
            ma[min_] = set()
        ma[min_].add(a)
        ma[min_].add(b)
    elif xs[a] != -1 and xs[b] != -1 and xs[a] != xs[b]:
        min_, max_ = sorted([xs[a], xs[b]])
        if ma.get(max_):
            for i in ma[max_]:
                xs[i] = min_
            del ma[max_]

        #xs = list(map(lambda x:x if ma.get(x) is None else ma[x], xs))
    else:
        new = [xs[k] for k in [a,b] if xs[k] != -1][0]
        xs[a] = new
        xs[b] = new

    # print(xs)

from collections import Counter

xs = [x for x in xs if x != -1]

if xs != []:
    print(max(Counter(xs).values()))
else:
    print(1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict

input = sys.stdin.readline


def ST():
    return input().rstrip()


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


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


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


N, M = MI()

d = defaultdict(set)

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

for _ in range(M):
    a, b = MI()
    d[a].add(b)
    d[b].add(a)

ans = 0
for k, value in d.items():
    tmp = set()
    tmp |= value
    for v in value:
        tmp |= d[v]
    ans = max(ans, len(tmp))

print(ans)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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


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

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
ls = [[i+1] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    ls[a-1].append(b)
    ls[b-1].append(a)
maximum = 0
for i in range(len(ls)):
    ls[i] = list(set(ls[i]))
for i in range(len(ls)):
    if len(ls[i]) > maximum:
        maximum = len(ls[i])
print(maximum)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [0] * n
        self.chi = [0] * n
        for i in range(n):
            self.par[i] = i
            self.chi[i] = 1
        self.max_child = 0
    def root(self, x):
        if self.par[x] == x:
            return x
        rx = self.root(self.par[x])
        self.par[x] = rx
        #if self.chi[x] < self.chi[rx]:
        #    self.chi[x] = self.chi[rx]
        return self.par[x]
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return
        #print("rx = ", rx, "ry = ", ry)
        #print("self.chi[rx] = ", self.chi[rx])
        #print("self.chi[ry] = ", self.chi[ry])
        self.par[rx] = ry
        self.chi[ry] += self.chi[rx]
        if self.max_child < self.chi[ry]:
            self.max_child = self.chi[ry]
    def same(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        return rx == ry

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

u = UnionFind(n)
for i in range(m):
    a, b = map(int, input().split())
    u.unite(a-1, b-1)
    #print("self.par[", a-1, "] = ", u.par[a-1])
    #print("self.par[", b-1, "] = ", u.par[b-1])
    #print("self.chi[", a-1, "] = ", u.chi[a-1])
    #print("self.chi[", b-1, "] = ", u.chi[b-1])
    

print(u.max_child)
#for i in range(n):
#    print(u.par[i])

Submission status: Wrong Answer

Solution code:
def abc177d():
    n, m = map(int, input().split())
    check = [-1] * n
    pair = []
    group_no = 0
    group = {}
    for i in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        if check[a] == check[b]:
            if check[a] == -1:
                group[group_no] = {a, b}
                check[a] = check[b] = group_no
                group_no += 1
        elif check[a] == -1:
            group[check[b]].add(a)
        elif check[b] == -1:
            group[check[a]].add(b)
        else:
            re = min(check[a], check[b])
            de = max(check[a], check[b])
            for v in group[de]:
                check[v] = re
            group[re] = group[re] | group[de]
            del group[de]
    max_val = 1
    for k in group:
        max_val = max(max_val,len(group[k]))
    print(max_val)
abc177d()

Submission status: Wrong Answer

Solution code:
from collections import deque
n,m = map(int,input().split())
l = [set([]) for i in range(n+1)]
for i in range(m):
  a,b = map(int,input().split())
  l[a].add(b)
  l[b].add(a)
Q = deque()
for i in range(n):
  Q.append(i+1)
vis = [-1]*(n+1)
vis[1] = 1
while Q:
  temp = Q.popleft()
  for v in l[temp]:
    if vis[temp]!=-1:
      continue
    vis[v] = vis[temp]+1
    Q.appendleft(v)
print(max(vis)+1)

Submission status: Wrong Answer

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


friends=[]
num=0
people=[-1]*n
ans=0

for f in F:
    a=f[0]-1
    b=f[1]-1
    #print(a,b)

    if people[a]==-1 and people[b]==-1:
        friends.append({a,b})
        people[a]=num
        people[b]=num
        num+=1

    elif people[a]!=-1 and people[b]!=-1:
        A=people[a]
        B=people[b]
        friends[A] = friends[A].union(friends[B])
        for i in friends[B]:
            people[i]=A

    elif people[a]!=-1:
        friends[people[a]].add(b)
        people[b]=people[a]

    elif people[b]!=-1:
        friends[people[b]].add(a)
        people[a]=people[b]

    #print(friends)

for i in friends:
    if len(i)>ans:
        ans=len(i)
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
mInfos = [list(map(int, input().split())) for _ in range(M)]
zentai =[]
for i in range(M):
    mInfo = mInfos[i]
    p1 = mInfo[0]
    p2 = mInfo[1]
    naiflag = True
    for z in zentai:
        if p1 in z or p2 in z:
            z.append(p1)
            z.append(p2)
            naiflag = False
            break
    if naiflag:
        zentai.append([p1,p2])
mi = -1
for z in zentai:
    sz =set(z)
    mi = max(mi,len(sz))
print(mi)