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:
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[v]!=-1:
      continue
    if vis[temp]==-1:
      vis[temp]=1
    vis[temp] += 1
    vis[v] = vis[temp]
    Q.appendleft(v)
print(max(vis))

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())
    f[a-1].append(b)
    f[b-1].append(a)
    f[a-1] += f[b-1]
    f[b-1] += f[a-1]


x = map(lambda A : len(set(A)) , f)
print(max(x))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N, M = map(int, input().split())
friend = defaultdict(set)
leader = []
for i in range(M):
    Ai, Bi = map(int, input().split())
    friend[Ai].add(Bi)
    friend[Bi].add(Ai)
print(friend)
already = {}
answer = 0
for i in range(1, N + 1):
    if i in already:
        continue
    if i not in friend:
        continue

    queue = []
    for f in friend[i]:
        already[f] = True
        queue.append(f)
    already[i] = True
    size = 0
    while len(queue) > size:
        item = queue[size]
        size += 1
        if item in friend:
            for f in friend[item]:
                if f not in already:
                    already[f] = True
                    queue.append(f)
    if size > answer:
        answer = size
print(answer + 1)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
friends = {}
if N <= 2:
    print (N)
else:
    for _ in range(M):
        f, s = map(int, input().split())
        if f in friends.keys():
            friends[f].append(s)
        else:
            friends[f] = [s]
        if s in friends.keys():
            friends[s].append(f)
        else:
            friends[s] = [f]
    biggest = 1
    for i, v in enumerate(friends):
        friends[v] = set(friends[v])
        biggest = max(len(friends[v]), biggest)
    print(biggest + 1)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
rel = [[i] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    rel[a].append(b)
    rel[a].extend(rel[b])
    rel[b].append(a)
    rel[b].extend(rel[a])

ans = 0
for i in rel:
    ans = max(len(set(i)),ans)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd
d=dd(list)

N,M=map(int, input().split())
for _ in range(M):
    f=0
    i,j=map(int, input().split())
    if i>j:
        i,j=j,i
    if j in d[i]:
        continue
    
    for a in range(i):
        if i in d[a] :
            if j not in d[a]:
                d[a].append(j)
            f=1
            continue
    if f==1:
        continue
    d[i].append(j)

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

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:set([x]) for x in range(1,N+1)}
for _ in range(M):
  A,B = (int(x) for x in input().rstrip('\n').split())
  f[A] |= f[B]
  f[B] = f[A]
print(max(len(x) for x in f.values()))

Submission status: Wrong Answer

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

		if group[m - 1] == group[M - 1] == -1:
			group[M - 1] = m - 1
		elif group[m - 1] == -1 and group[M - 1] != -1:
			group[m - 1] = group[M - 1]
		elif group[m - 1] != -1 and group[M - 1] == -1:
			group[M - 1] = group[m - 1]
		else:
			q = min([group[m - 1], group[M - 1]])
			while group[q] != -1:
				q = group[q]
			else:
				group[m - 1] = q
				group[M - 1] = q

	group_member = [0] * N
	for i in range(len(group)):
		if group[i] == -1:
			group_member[i] += 1
		else:
			group_member[group[i]] += 1 
	print(max(group_member))

main()

Submission status: Wrong Answer

Solution code:
import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque, defaultdict
from fractions import gcd
from functools import reduce
from itertools import groupby, combinations
from heapq import heapify, heappush, heappop

# sys.setrecursionlimit(5000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return list(map(lambda x: x + d, A))
def ldec(A, d=1): return list(map(lambda x: x - d, A))

N, M = nn()
T = nm(M)

T = sorted(T, key=lambda x: x[0])

d = defaultdict(list)
team = defaultdict(list)
memo = array1(N+1, -1)

c = 0
for i in range(M):
    a, b = T[i]
    if memo[a] == -1 and memo[b] == -1:
        team[c].append(a)
        team[c].append(b)
        memo[a] = c
        memo[b] = c
        c += 1
    elif memo[a] == -1:
        team[memo[b]].append(a)
        memo[a] = memo[b]
    elif memo[b] == -1:
        team[memo[a]].append(b)
        memo[b] = memo[a]

#print(memo)
#pprint(team)

ans = 0
for i in range(len(team)):
    t = len(team[i])
    if t > ans:
        ans = t

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

def main():
    N, M = map(int, input().split())
    friendslist = [set() for _ in range(N)]
    for i in range(M):
        A, B = map(int, input().split())
        friendslist[A-1].add(B-1)
        friendslist[B-1].add(A-1)
    ans = 0
    for s in friendslist:
        ans = max(len(s)+1, ans)
    print(ans)
    

if __name__ == "__main__":
    main()

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())
        unf.union(A-1, B-1)
    
    groups = unf.all_group_members()

    sizes = []
    total_ = 0
    for k, i in groups.items():
        sizes.append(len(groups[k]))
        total_ += len(groups[k])
    
    
    group_nums = len(sizes) + N - total_

    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())
A = list()
B = list()
for _ in range(M):
    a, b = map(int, input().split())
    A.append(a-1)
    B.append(b-1)

largest = 1
group = []
people = [-1] * N
for a, b in zip(A, B):
    if people[a] != -1:
        people[b] = people[a]
        group[people[a]].add(b)
    elif people[b] != -1:
        people[a] = people[b]
        group[people[b]].add(a)
    else:
        group.append(set([a, b]))
        people[a] = len(group)-1
        people[b] = people[a]
    largest = max(len(group[people[a]]), largest)

print(largest)

Submission status: Wrong Answer

Solution code:
import copy
import sys
from collections import deque
N, M = map(int,input().split())
checked = [False] * N
dq = deque([0])
path = [[] for _ in range(N)]
for s in sys.stdin.readlines():
    a, b = list(map(lambda x: int(x)-1, s.split()))
    path[a].append(b)
    path[b].append(a)
ans = 1
dq = deque([[i,1] for i in range(N)])
while dq:
   i, d= dq.popleft()
   if checked[i]:
      continue
   ans = max(d, ans)
   checked[i] = True
   for j in range(len(path[i])):
      h = path[i][j]
      l = d + len(path[i])
      if not checked[h]:
         dq.appendleft([h, l])
print(ans)

Submission status: Wrong Answer

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

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

if len(set(par))==1:
  print(0)
  exit()
print(max_size)

Submission status: Wrong Answer

Solution code:
import sys
from copy import deepcopy
input = sys.stdin.readline


def readstr():
    return input().strip()


def readint():
    return int(input())


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


def readstrs():
    return input().split()


def main():
    N, M = readnums()
    ab = [tuple(readnums()) for _ in range(M)]
    al = {i: set() for i in range(1, N + 1)}
    for a, b in ab:
        if not al:
            al[a].add(b)
            al[b].add(a)
        else:
            if b not in al[a]:
                al[a].add(b)
            if a not in al[b]:
                al[b].add(a)

    al2 = deepcopy(al)
    for k, v in al.items():
        for vv in v:
            al2[k] |= al[vv]

    ans = max(list(map(lambda x: len(x), al2.values())))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
li = [0]*(n+1)
flag = 1
ans = 0
for _ in range(m):
    a, b = map(int, input().split())
    if li[a] or li[b]:
        s = max(li[a],li[b])
        li[a] = s
        li[b] = s
    else:
        li[a] = flag
        li[b] = flag
        flag += 1
for i in range(len(li)):
    if li[i] == 0:
        li[i] = -i
from collections import Counter
result = Counter(li)
print(result.most_common(1)[0][1])

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)
    for j in set(line[y-1]):
        line[x-1].append(j)
        
    line[y-1].append(x-1)
    for j in set(line[x-1]):
        line[y-1].append(j)
    
output = 1
for i in range(N):
    if len(set(line[i])) > output:
        output = len(set(line[i]))
print(output)

Submission status: Wrong Answer

Solution code:
n,q=map(int,input().split())
track=(n+1)*[0]
l=[]
for i in range(q):
    j, k = map(int, input().split())
    j, k = min(j, k), max(j, k)
    l.append([j,k])
l.sort()

for i in l:
    j=i[0]
    k=i[1]
    if track[j]==0 and track[k]==0:
        track[j]={k:1}
        track[k]=-j
    elif type(track[j]) is int and track[j]<0:
        track[-track[j]][k]=1
        track[k]=track[j]
    elif type(track[j]) is int and track[k]<0:
        track[-track[k]][j]=1
        track[j]=track[k]
    else:
        track[j][k]=1
ans=1
for i in track:
    if type(i) is dict:
        ans=max(ans,1+len(i))
print(ans)

Submission status: Wrong Answer

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

import networkx as nx
G = nx.Graph()
G.add_edges_from(a)
nx.connected_components(G)

max_size = 0

for component in nx.connected_components(G):
    if len(component) > max_size:
        max_cluster = component
        max_size = len(max_cluster)
print(max_size)

Submission status: Wrong Answer

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

largest = 0
group = []
people = [-1] * N
for a, b in zip(A, B):
    if people[a] != -1:
        people[b] = people[a]
        group[people[a]].add(b)
    elif people[b] != -1:
        people[a] = people[b]
        group[people[b]].add(a)
    else:
        group.append(set([a, b]))
        people[a] = len(group)-1
        people[b] = people[a]
    largest = max(len(group[people[a]]), largest)

print(largest)

Submission status: Wrong Answer

Solution code:
import sys
import math
import collections
import decimal
import itertools
from collections import deque
from functools import reduce
import heapq
import copy
import numpy as np
#n = int(input())
n, m = map(int, sys.stdin.readline().split())
#s = input()
#a = list(map(int, sys.stdin.readline().split()))

group = [0 for i in range(n)]
l = []
for i in range(m):
    a, b = map(int, sys.stdin.readline().split())
    if a < b:
        c = a
        d = b
    else:
        c = b
        d = a
    l.append([c, d])

l.sort(key=lambda x:(x[0], x[1]))
change = [i+1 for i in range(n)]
cur = 0
for i in range(m):
    e = l[i][0]
    f = l[i][1]
    if group[e-1] == 0 and group[f-1] == 0:
        group[e-1] = cur + 1
        group[f-1] = cur + 1
        cur += 1
    elif group[e-1] == 0 and group[f-1] != 0:
        group[e-1] = group[f-1]
    elif group[f-1] == 0 and group[e-1] != 0:
        group[f-1] = group[e-1]
    elif group[e-1] != group[f-1]:
        x = min(group[e-1], group[f-1])
        y = max(group[e-1], group[f-1])
        change[y-1] = change[x-1]

h = collections.Counter(group)

k = max(change)
p = [0 for i in range(k)]
for i in range(1, n):
    p[change[i]-1] += h[i]

print(max(p))

Submission status: Wrong Answer

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

AB=[0]*n
Mindex=[0]*n
Minfo=[0]*(m+1)

MinfoIndex=1

for A in Alist:
  a=A[0]-1
  b=A[1]-1
  
  if AB[a]+AB[b]==0:
    AB[a]+=1
    AB[b]+=1
    Mindex[a]=MinfoIndex
    Mindex[b]=MinfoIndex
    Minfo[MinfoIndex]+=2
    MinfoIndex+=1
  else:
    if AB[a]>0 and AB[b]>0:
      pass
    elif AB[a]>0:
      AB[b]+=1
      Mindex[b]=Mindex[a]
      Minfo[Mindex[b]]+=1
    elif AB[b]>0:
      AB[a]+=1
      Mindex[a]=Mindex[b]
      Minfo[Mindex[b]]+=1   
    
if m >0:
  print(max(Minfo))
else:
  print(1)

Submission status: Wrong Answer

Solution code:
N, M = list(map(int, input().split()))
A = [[0, 0]]

for i in range(M):
    j, k = list(map(int, input().split()))
    for z  in range(len(A)):
        if j in A[z] and k in A[z]:
            break
        elif j in A[z] and k not in A[z]:
            A[z].append(k)
            break
        elif j not in A[z] and k in A[z]:
            A[z].append(j)
            break
    A.append([j, k])

result = 0
for i in range(len(A)):
    if result < len(A[i]):
        result = len(A[i])
print(result)

Submission status: Wrong Answer

Solution code:
class UnionFind():
    #https://note.nkmk.me/python-union-find/ 
    #note.nkmk.me  2019-08-18 
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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


# 初期入力
import sys
input = sys.stdin.readline  #文字列では使わない
N,M = map(int, input().split())
G =UnionFind(N)
ans =0
for i in range(M):
    a,b = map(int, input().split())
    #a,b =min(a,b),max(a,b)
    G.union(a-1,b-1)
    ans =max(ans,G.size(a-1))
print(ans)

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] = {}

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

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

Submission status: Wrong Answer

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

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

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


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

    if a in grp:
        if b not in grp:
            grp[b] = grp[a]
            ngrp[grp[b]] += 1
    elif b in grp:
        if a not in grp:
            grp[a] = grp[b]
            ngrp[grp[a]] += 1
    else:
        grp[a] = uniq_grp
        grp[b] = grp[a]
        ngrp[grp[a]] += 2

        uniq_grp += 1

ret = 0
for k in ngrp:
    ret = max(ret, ngrp[k])
print(ret)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
li = [0]*(n+1)
flag = 1
for _ in range(m):
    a, b = map(int, input().split())
    if li[a] and li[b]:
        li[a] = li[b]
    elif li[a] or li[b]:
        s = max(li[a],li[b])
        li[a] = s
        li[b] = s
    else:
        li[a] = flag
        li[b] = flag
        flag += 1
for i in range(len(li)):
    if li[i] == 0:
        li[i] = -i
from collections import Counter
result = Counter(li)
print(result.most_common(1)[0][1])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

edges = defaultdict(set)
for _ in range(m):
  a, b = map(int, input().split())
  edges[a].add(b)
  edges[b].add(a)
  
for _ in range(m):
  for k, v in edges.items():
    for e in v:
      edges[k] = edges[k] | edges[e]

result = 0
for k, v in edges.items():
  size = len(v)
  if result < size:
    result = size
print(result)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n,m = map(int,input().split())
group = {}
for i in range(1,n+1):
    group[i] = i
for _ in range(m):
    a,b = map(int,input().split())
    k = min(group[a],group[b])
    group[a] = k
    group[b] = k
p = Counter(group.values())
print(max(p.values()))

Submission status: Wrong Answer

Solution code:
def main():
    N,M = map(int,input().split())
    A = [[0,0] for i in range(M)]
    for i in range(M):
        A[i] = list(map(int,input().split()))
        list.sort(A[i])
    
    list.sort(A)
    
    List = [-1 for i in range(N)]
    host = 0
    guest = 0
    for i in range(M):
        a = A[i][0]-1
        b = A[i][1]-1
        if List[a] == -1 and List[b] == -1:
            host = a
            guest = b
            List[host] = host
        elif List[a] != -1:
            host = List[a]
            guest = b
        elif List[b] != -1:
            host = List[b]
            guest = a
        List[guest] = host
        
    ans = [0 for i in range(N)]
    for i in range(N):
        L = List[i]
        if L != -1:
            ans[L] += 1
            
    print(max(ans))
        
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import collections

N,M = list(map(int, input().split()))
team_table = [0 for i in range(N)]
color = 0

for i in range(M):
    A,B = list(map(int, input().split()))
    if (team_table[A-1] == 0)&(team_table[B-1] == 0):
        color = A
        team_table[A-1] = color 
        team_table[B-1] = color
    elif (team_table[A-1] == 0)&(team_table[B-1] != 0):
        team_table[A-1] = team_table[B-1]
    elif (team_table[A-1] != 0)&(team_table[B-1] == 0):
        team_table[B-1] = team_table[A-1]

if M != 0:
    ans_table = []
    for t in team_table:
        if t != 0:
            ans_table.append(t)

    ans = collections.Counter(ans_table).most_common()[0][1]
else:
    ans = 1
 
        
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    import collections
    n, m = map(int, input().split())
    dic1 = dict() 
    if m == 0:
        print(1)
        exit()
    a, b = map(int, input().split())
    dic1[a] = 1
    dic1[b] = 1
    

    for _ in range(m-1):
        a, b = map(int, input().split())
        if a not in dic1 and b not in dic1:
            dic1[a] = max(dic1.values()) + 1
            dic1[b] = dic1[a]
        elif a in dic1 and b not in dic1:
            dic1[b] = dic1[a]
        elif a not in dic1 and b in dic1:
            dic1[a] = dic1[b]
    #print(dic1)
    ansdic = dict()
    for k, v in dic1.items():
        if v not in ansdic:
            ansdic[v] = 1
        else:
            ansdic[v] += 1
    print(max(ansdic.values()))

    

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
freind = set()
freindlist = []
log = dict()
mea = 0
sig = 0
inputlist = []
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})
        log[str(A)] = mea
        log[str(B)] = mea
        mea += 1
    elif A in freind:
        freind.add(B)
        sig = log[str(A)] 
        freindlist[sig].add(B)
        log[str(B)] = sig
    elif B in freind:
        freind.add(A)
        sig = log[str(B)] 
        freindlist[sig].add(A)
        log[str(A)] = sig
    inputlist.append([A,B])
for j in range(M):
    A,B = inputlist[j][0],inputlist[j][1]
    if A not in freind and B not in freind:
        freind.add(A)
        freind.add(B)
        freindlist.append({A,B})
        log[str(A)] = mea
        log[str(B)] = mea
        mea += 1
    elif A in freind:
        freind.add(B)
        sig = log[str(A)] 
        freindlist[sig].add(B)
        log[str(B)] = sig
    elif B in freind:
        freind.add(A)
        sig = log[str(B)] 
        freindlist[sig].add(A)
        log[str(A)] = sig
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())
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])
        else:
          if shozoku[ab[i][1]-1]!=shozoku[ab[i][0]-1]:
            f[shozoku[ab[i][0]-1]-1].extend(f[shozoku[ab[i][1]-1]-1])
            f[shozoku[ab[i][1]-1]-1]=f[shozoku[ab[i][0]-1]-1]
ans=1
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())
e = list(set([tuple(sorted(map(int, input().split()))) for _ in range(m)]))
e.sort()
g = {k: k for k in range(1, n+1)}
p = {k: 0 for k in range(1, n+1)}

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

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

print(max(p.values()))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
sets = [{i+1} for i in range(n)]
count = 0
for _ in range(m):
  a, b = map(int, input().split())
  if b in sets[a-1]:
    pass
  else:
    sets[a-1].add(b)
    sets[b-1].add(a)
print(max(len(s) for s in sets))

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

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
friends = {}
for _ in range(M):
    f, s = map(int, input().split())
    if f in friends.keys():
        friends[f].append(s)
    else:
        friends[f] = [s]
    if s in friends.keys():
        friends[s].append(f)
    else:
        friends[s] = [f]
biggest = 1
for i, v in enumerate(friends):
    friends[v] = set(friends[v])
    biggest = max(len(friends[v]), biggest)
print(biggest + 1)

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)

mm = abs(min(uf.table))
ic = 0
for n in uf.table:
    if n == -1:
        ic += 1
if mm < ic:
    mm += 1

print(mm)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# def get_group_num(sum, nums):
#     if len(nums) == 1:
#         return sum + nums[0]
#     pass

def main():
    n, m = map(int, input().split())
    friends_list = []
    num_check = {}
    for i in range(m):
        check=True
        a,b = map(int, input().split())
        for i, friends_set in enumerate(friends_list):
            if a in friends_set or b in friends_set:
                friends_list[i].add(a)
                friends_list[i].add(b)
                check = False
                break
        if check:
            friends_list.append({a, b})
    group_num = len(friends_list)
    max = 0
    for friends_set in (friends_list):
        length = len(friends_set)
        if length > max:
            max = length
    print(max)
    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import collections
n, m = map(int, input().split())
gp = [[] for i in range(n+1)]
seen = [0 for i in range(n+1)]
ans = []

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

for i in range(1, n+1):
  if seen[i] == 1:
    continue
  else:
    que = [i]
    cnt = 0
    while que:
      now = que.pop(0)
      for g in gp[now]:
        if seen[g] == 1:
          continue
        else:
          que.append(g)
          seen[g] = 1
          cnt += 1
    ans.append(cnt) 
        
print(max(ans))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(m)]
edges = [[] for _ in range(n)]
for a, b in AB:
    edges[a - 1].append(b)
    edges[b - 1].append(a)

ans = 0
for edge in edges:
    ans = max(ans, len(set(edge))+1)
print(ans)