Problem:


Score : 400 points

Problem Statement

There are N persons called Person 1 through Person N.

You are given M facts that "Person A_i and Person B_i are friends." The same fact may be given multiple times.

If X and Y are friends, and Y and Z are friends, then X and Z are also friends. There is no friendship that cannot be derived from the M given facts.

Takahashi the evil wants to divide the N persons into some number of groups so that every person has no friend in his/her group.

At least how many groups does he need to make?

Constraints

2 \leq N \leq 2\times 10^5

0 \leq M \leq 2\times 10^5

1\leq A_i,B_i\leq N

A_i \neq B_i

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
\vdots
A_M B_M

Output

Print the answer.

Sample Input 1

5 3
1 2
3 4
5 1

Sample Output 1

3

Dividing them into three groups such as \{1,3\}, \{2,4\}, and \{5\} achieves the goal.

Sample Input 2

4 10
1 2
2 1
1 2
2 1
1 2
1 3
1 4
2 3
2 4
3 4

Sample Output 2

4

Sample Input 3

10 4
3 1
4 1
5 9
2 6

Sample Output 3

3



Sample input:
5 3
1 2
3 4
5 1


Sample output:
3

Submission status: Wrong Answer

Solution code:
# 接続最大クラスタのサイズが答え？

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

from collections import defaultdict
d = defaultdict(set)

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

def bfs(i):
    obs = {i}
    passed = {i}

    # get next_obs
    before = {i}
    while True:
        after = set()
        for i in before:
            after |= d[i]
        before = after - passed
        passed |= after
        if len(after) == 0:
            return passed
    return len(passed)

print(max([bfs(i) for i in range(1, N+1)]))

Submission status: Wrong Answer

Solution code:
import copy
N,M = [int(i) for i in input().split()]
AB = []
ans = 1
for i in range(M):
  AB.append([int(i) for i in input().split()])
#print(AB)
rel = [[] for i in range(N)]
#print(rel)
for x in AB:
  #print(rel[x[0]-1],x[1]-1)
  rel[x[0]-1].append(x[1]-1)
  rel[x[1]-1].append(x[0]-1)
#print(rel)
rel = [list(set(x)) for x in rel]

check = [0 for i in range(N)]
##print(check)
q = copy.deepcopy(rel[0])
check[0] = 1
checkstart = copy.deepcopy(check)
while(check != [1 for i in range(N)]):
  #print("check =",check)
  #print("rel=",rel)
  #print("q =",q)
  qlen = 0
  if(check == checkstart):
    qlen = 1
  while(q != []):
    #print("q =",q)
    ima = q.pop()
    qlen += 1
    #print("qlen =",qlen)
    #print("ima =",ima)
    #print("check[ima] =" ,check[ima])
    if check[ima] == 0:
      check[ima] = 1 
      for x in rel[ima]:
        if check[x] == 0:
          q.append(x)
          q = list(set(q))
  for j in range(N):
    if check[j] == 0:
      q.append(j)
      q = list(set(q))
      break
  ans = max(ans, qlen)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

N,M = map(int,input().split())
hint_list = [list(map(int,input().split())) for i in range(M)]
friend_list = []

def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

hint_list = get_unique_list(hint_list)

if M == 0:
    print(0)
else:
    for i in range(1,N+1):
        i_list = []
        j_list = []
        for j in range(len(hint_list)):
            if i in hint_list[j]:
                i_list.append(hint_list[j])
                j_list.append(j)
            else:
                pass
            
        i_list = list(set(sum(i_list,[])))
        if i_list != []:
            new_j_list = []
            for i in range(len(j_list)):
                new_j_list.append(j_list[i]-i)
            for i in range(len(new_j_list)):
                del hint_list[new_j_list[i]]
            hint_list.append(i_list)
        else:
            pass
    
    friend_len = []
    for i in range(len(hint_list)):
        friend_len.append(len(hint_list[i]))
    
    print(max(friend_len))

Submission status: Wrong Answer

Solution code:
from collections import deque

N,M = map(int,input().split())
hint_list = [list(map(int,input().split())) for i in range(M)]
friend_list = []

def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

hint_list = get_unique_list(hint_list)

if M == 0:
    print(0)
else:
    for i in range(1,N+1):
        i_list = []
        j_list = []
        for j in range(len(hint_list)):
            if i in hint_list[j]:
                i_list.append(hint_list[j])
                j_list.append(j)
            else:
                pass
            
        i_list = list(set(sum(i_list,[])))
        if i_list != []:
            new_j_list = []
            for i in range(len(j_list)):
                new_j_list.append(j_list[i]-i)
            for i in range(len(new_j_list)):
                del hint_list[new_j_list[i]]
            hint_list.append(i_list)
        else:
            pass
    
    friend_len = []
    print(hint_list)
    for i in range(len(hint_list)):
        friend_len.append(len(hint_list[i]))
    
    print(max(friend_len))

Submission status: Wrong Answer

Solution code:
# 接続最大クラスタのサイズが答え？

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

from collections import defaultdict
d = defaultdict(set)

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

def dfs(i, obs=set()):
    # set_obs = d[i] | {i}
    obs |= {i}
    for j in d[i]:
        if j not in obs:
            obs |= bfs(j, obs)
    return obs

def next_obs(obs, passed):
    next_obs = set()
    for i in obs:
        next_obs |= d[i]
    return next_obs - obs

def bfs(i):
    obs = {i}
    passed = {i}

    # get next_obs
    while True:
        next_obs = set()
        for i in obs:
            next_obs |= d[i]
        next_obs -= passed
        passed |= next_obs
        if len(next_obs) == 0:
            return passed


    return obs | set(next_obs(obs, obs))

print(max(len(bfs(i)) for i in range(1, N+1)))

Submission status: Wrong Answer

Solution code:
# 接続最大クラスタのサイズが答え？

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

from collections import defaultdict
d = defaultdict(set)

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

def dfs(i, obs=set()):
    # set_obs = d[i] | {i}
    obs |= {i}
    for j in d[i]:
        if j not in obs:
            obs |= bfs(j, obs)
    return obs

def next_obs(obs):
    next_obs = set()
    for i in obs:
        next_obs |= d[i]
    return next_obs - obs

def bfs(i):
    obs = {i}
    return obs | set(next_obs(obs))

print(max(len(bfs(i)) for i in range(1, N+1)))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
friend = [[] for _ in range(n+1)]
cnt = [0 for _ in range(n+1)]

for i in range(m):
    a, b = map(int, input().split())
    if not b in friend[a]:
        friend[a].append(b)
        friend[b].append(a)
        cnt[a] += 1
        cnt[b] += 1
print(max(cnt)+1)

Submission status: Wrong Answer

Solution code:
import collections as col
from collections import defaultdict as dd

d=dd(list)

N,M=map(int, input().split())
p=[-1]*N
cnt=[0]*N
p[0]=1
cnt[0]=1
for _ in range(M):
    i,j=map(int, input().split())
    if i>j:
        i,j=j,i
    d[i].append(j)

for i in d:
    for j in d[i]:
        if p[i-1]==-1:
            if p[j-1]==-1:
                if i<j:
                    p[i-1]=i
                    p[j-1]=i
                else:
                    p[i-1]=j
                    p[j-1]=j
            else:
                p[i-1]=p[j-1]
        else:
            if p[j-1]==-1:
                p[j-1]=p[i-1]
            else:
                if p[i-1]<p[j-1]:
                    temp1=p[j-1]
                    temp2=p[i-1]
                else:
                    temp1=p[j-1]
                    temp2=p[i-1]
                #p=[temp2 if k==temp1 else k for k in p]

ans=col.Counter(p)

if ans.most_common()[0][0]==-1:
    print(ans.most_common()[1][1])
else:
    print(ans.most_common()[0][1])

Submission status: Wrong Answer

Solution code:
from collections import deque

N,M = map(int,input().split())
hint_list = [list(map(int,input().split())) for i in range(M)]
friend_list = []

def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

hint_list = get_unique_list(hint_list)

if M == 0:
    print(N)
else:
    for i in range(1,N+1):
        i_list = []
        j_list = []
        for j in range(len(hint_list)):
            if i in hint_list[j]:
                i_list.append(hint_list[j])
                j_list.append(j)
            else:
                pass
            
        i_list = list(set(sum(i_list,[])))
        if i_list != []:
            new_j_list = []
            for i in range(len(j_list)):
                new_j_list.append(j_list[i]-i)
            for i in range(len(new_j_list)):
                del hint_list[new_j_list[i]]
            hint_list.append(i_list)
        else:
            pass
    
    friend_len = []
    for i in range(len(hint_list)):
        friend_len.append(len(hint_list[i]))
    
    print(max(friend_len))

Submission status: Wrong Answer

Solution code:
from collections import deque

N,M = map(int,input().split())
hint_list = [list(map(int,input().split())) for i in range(M)]
friend_list = []

def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

hint_list = get_unique_list(hint_list)

if M == 0:
    print(N)
else:
    for i in range(1,N+1):
        i_list = []
        j_list = []
        for j in range(len(hint_list)):
            if i in hint_list[j]:
                i_list.append(hint_list[j])
                j_list.append(j)
            else:
                pass
            
        i_list = list(set(sum(i_list,[])))
        if i_list != []:
            new_j_list = []
            for i in range(len(j_list)):
                new_j_list.append(j_list[i]-i)
            for i in range(len(new_j_list)):
                del hint_list[new_j_list[i]]
            hint_list.append(i_list)
        else:
            pass
        print(hint_list)
    
    friend_len = []
    for i in range(len(hint_list)):
        friend_len.append(len(hint_list[i]))
    
    print(max(friend_len))

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
communities = [0 for i in range(N)]
same = []
same_count = [[0 for i in range(N//2)] for j in range(N//2)]
num = 1
for i in range(M):
  A, B = map(int,input().split())
  ca = communities[A-1]
  cb = communities[B-1]
  if ca == 0 and cb == 0:
    communities[A-1] = num
    communities[B-1] = num
    num += 1
  elif ca == 0 or cb == 0:
    communities[A-1] = max(ca, cb)
    communities[B-1] = max(ca, cb)
  elif ca != cb:
    minc = min(ca, cb)
    maxc = max(ca, cb)
    if same_count[minc][maxc] == 0:
      same.append([minc, maxc])
      same_count[minc][maxc] = 1
  else:
    continue

communities.sort()
if communities[-1] == 0:
  max_members = 1
else:
  members = [0 for i in range(communities[-1])]
  for i in range(N):
    if communities[i] > 0:
      members[communities[i]-1] += 1
  for i in range(len(same)):
    members[same[i][0]-1] += members[same[i][1]-1]
  max_members = max(members)
print(max_members)

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
communities = [0 for i in range(N)]
same = []
num = 1
for i in range(M):
  A, B = map(int,input().split())
  ca = communities[A-1]
  cb = communities[B-1]
  if ca == 0 and cb == 0:
    communities[A-1] = num
    communities[B-1] = num
    num += 1
  elif ca == 0 or cb == 0:
    communities[A-1] = max(ca, cb)
    communities[B-1] = max(ca, cb)
  elif ca != cb:
    minc = min(ca, cb)
    maxc = max(ca, cb)
    if [minc, maxc] not in same:
      same.append([minc, maxc])
  else:
    continue

communities.sort()
if communities[-1] == 0:
  max_members = 1
else:
  members = [0 for i in range(communities[-1])]
  for i in range(N):
    if communities[i] > 0:
      members[communities[i]-1] += 1
  for i in range(len(same)):
    members[same[i][0]-1] += members[same[i][1]-1]
  max_members = max(members)
print(max_members)

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
communities = [0 for i in range(N)]
same = []
num = 1
for i in range(M):
  A, B = map(int,input().split())
  ca = communities[A-1]
  cb = communities[B-1]
  if ca == 0 and cb == 0:
    communities[A-1] = num
    communities[B-1] = num
    num += 1
  elif ca == 0 or cb == 0:
    communities[A-1] = max(ca, cb)
    communities[B-1] = max(ca, cb)
  elif ca != cb:
    same.append([min(ca, cb), max(ca, cb)])
  else:
    continue

communities.sort()
if communities[-1] == 0:
  max_members = 1
else:
  members = [0 for i in range(communities[-1])]
  for i in range(N):
    if communities[i] > 0:
      members[communities[i]-1] += 1
  for i in range(len(same)):
    members[same[i][0]-1] += members[same[i][1]-1]
  max_members = max(members)
print(max_members)

Submission status: Wrong Answer

Solution code:
import collections as col
from collections import defaultdict as dd

d=dd(list)

N,M=map(int, input().split())
p=[-1]*N
cnt=[0]*N
p[0]=1
cnt[0]=1
for _ in range(M):
    i,j=map(int, input().split())
    if i>j:
        i,j=j,i
    d[i].append(j)

for i in d:
    for j in d[i]:
        if p[j-1]!=-1:
            if p[i-1]==-1:
                p[i-1]=p[j-1]
            continue
        if p[i-1]==-1:
            p[j-1]=i
        else:
            p[j-1]=p[i-1]

ans=col.Counter(p)

if ans.most_common()[0][0]==-1:
    print(ans.most_common()[1][1])
else:
    print(ans.most_common()[0][1])

Submission status: Wrong Answer

Solution code:
from collections import deque
N,M=map(int,input().strip().split())
l=list()
dp=[list() for _ in range(N)]
for _ in range(M):
    a,b=map(int,input().strip().split())
    l.append((a,b))
    dp[a-1].append(b)
    dp[b-1].append(a)

#友人がいないものを-1とする。
id=[-1 for _ in range(N)]
for e in l:
    id[e[0]-1]=0
    id[e[1]-1]=0

i=1
for n in range(1,N+1):
    if id[n-1]==0:
        q=deque([n])
        while q:
            tmp=q.popleft()
            id[tmp-1]=i
            for e in dp[tmp-1]:
                if id[e-1]==0:
                    id[e-1]=i
                    q.append(e)
        i+=1
MAX=0
for j in range(i):
    MAX=max(MAX,id.count(j))
print(MAX)

Submission status: Wrong Answer

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

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

max_ans = 0
for i in range(n):
    ans = len(friends[i])
    max_ans = max(max_ans, ans)

print(max_ans+1)

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
communities = [0 for i in range(N)]
same = []
num = 1
for i in range(M):
  A, B = map(int,input().split())
  if communities[A-1] == 0 and communities[B-1] == 0:
    communities[A-1] = num
    communities[B-1] = num
    num += 1
  elif communities[A-1] == 0:
    communities[A-1] = communities[B-1]
  elif communities[B-1] == 0:
    communities[B-1] = communities[A-1]
  elif communities[A-1] != communities[B-1]:
    same.append(min(communities[A-1], communities[B-1]))
    same.append(max(communities[A-1], communities[B-1]))
  else:
    continue

if len(communities) > 0:
  communities.sort()
  members = [0 for i in range(num)]
  for i in range(N):
    if communities[i] == 0:
      continue
    else:
      members[communities[i]-1] += 1
for i in range(len(same)//2):
  members[same[2*i]-1] += members[same[2*i+1]-1]
print(max(members))

Submission status: Wrong Answer

Solution code:
import collections as col
from collections import defaultdict as dd

d=dd(list)

N,M=map(int, input().split())
p=[-1]*N
cnt=[0]*N

for _ in range(M):
    i,j=map(int, input().split())
    if i>j:
        i,j=j,i
    d[i].append(j)

for i in d:
    for j in d[i]:
        
        if p[j-1]!=-1:
            continue
        if p[i-1]==-1:
            p[j-1]=i
            cnt[i]+=1
        else:
            p[j-1]=p[i-1]
            cnt[p[i-1]]+=1

cnt.sort(reverse=True)
print(cnt[0]+1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(1 << 25)  # 再起上限引き上げ

G = defaultdict(lambda: [])

#load data
N,M = map(int,input().split())
color = {key:0 for key in range(N)}
#graphをdefaultdictで保持することにする
for _ in range(M):
    s,t = map(int,input().split())
    G[s-1].append(t-1)
    G[t-1].append(s-1)
#print(G)
#隣接リストを基にたどり着ける友達をグループ化する。
def dfs(node:int, co:int):
    #終了条件、既に訪問済みなら訪問しない
    if color[node] != 0:
        return
    #処理
    color[node] = co
    for n in G[node]:
        dfs(n,co)

    return

#全てのnodeを開始点としてdfsで色分けしてみる
c = 1
for node in G.keys():
    dfs(node,c)
    c += 1

ans_list = [0]*(N)
for i in range(N):
    ans_list[color[i]] += 1

ans_list[0] = 0
print(max(ans_list))

Submission status: Wrong Answer

Solution code:

from collections import deque

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

for i in range(m):
    a, b = map(int, input().split())
    if b < a:
        c = b
        d = a
    else:
        c = a
        d = b
    l.add((c, d))

l = list(l)
l = [list(l[i]) for i in range(len(l))]

flg = [0]*len(l)
flg2 = [0]*n
q = deque([])
max_a = 0

for i in range(len(l)):
    friends = []
    if not flg[i]:
        flg[i] = 1
        if not flg2[l[i][0]-1]:
            q.append(l[i][0])
            friends.append(l[i][0])
            flg2[l[i][0] - 1] = 1
        if not flg2[l[i][1]-1]:
            q.append(l[i][1])
            friends.append(l[i][1])
            flg2[l[i][1] - 1] = 1
    while q:
        x = q.popleft()
        for j in range(len(l)):
            if x in l[j] and not flg[j]:
                flg[j] = 1
                if not flg2[l[j][0]-1]:
                    q.append(l[j][0])
                    friends.append(l[j][0])
                    flg2[l[j][0]-1] = 1
                if not flg2[l[j][1]-1]:
                    q.append(l[j][1])
                    friends.append(l[j][1])
                    flg2[l[j][1]-1] = 1
    a = len(friends)
    max_a = max(a, max_a)

print(max_a)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
relation=[0]*n
gn=0
for i in range(m):
    a,b=map(int,input().split())
    a=a-1
    b=b-1
    if relation[a]==0 and relation[b]==0:
        gn+=1
        relation[a]=gn
        relation[b]=gn
    if relation[a]!=0 and relation[b]==0:
        relation[b]=relation[a]
    if relation[b]!=0 and relation[a]==0:
        relation[a]=relation[b]
    else:
        gn+=1
        A=relation[a]
        B=relation[b]
        for i in relation:
            if i==A or i==B:
                i=gn
gn_list=list(set(relation))
ans=0
for n in gn_list:
    c=relation.count(n)
    if c>ans:
        ans=c
print(ans)

Submission status: Wrong Answer

Solution code:
import collections as col
from collections import defaultdict as dd

d=dd(list)

N,M=map(int, input().split())
p=[-1]*N
cnt=[0]*N

for _ in range(M):
    i,j=map(int, input().split())
    if i>j:
        i,j=j,i
    d[i].append(j)


for i in d:
    for j in d[i]:
        if p[j-1]!=-1:
            continue
        if p[i-1]==-1:
            p[j-1]=i
            cnt[i]+=1
        else:
            p[j-1]=p[i-1]
            cnt[p[i-1]]+=1

cnt.sort(reverse=True)

print(cnt[0]+1)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
relation=[0]*n
for i in range(m):
    a,b=map(int,input().split())
    a=a-1
    b=b-1
    if relation[a]&2**b==0:
        relation[a]+=2**b
    if relation[b]&2**a==0:
        relation[b]+=2**a
    relation[a]=relation[a]|relation[b]
    relation[b]=relation[a]
m=0
for i in range(n):
   c=bin(relation[i]).count("1")
   if m<c:
       m=c
print(m)

Submission status: Wrong Answer

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

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

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

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

def unite(x,y):
  x = find(x)
  y = find(y)
  if x == y:
    return 0
  par[x] = y

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

ans = max(par)
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
friends=[[] for _ in range(n+1)]
ff=[[] for _ in range(n+1)]
ans=0
for i in range(m):
    a,b=map(int,input().split())
    friends[a].append(b)
    friends[b].append(a)

for i in range(1,n+1):
    l=friends[i].copy()
    for f in friends[i]:
        l+=friends[f]
    ff[i]=list(set(l))
    ans=max(ans,len(ff[i]))
print(ans)

Submission status: Wrong Answer

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

gl = []
for x in range(n):
    friendset = set()
    friendset.add(str(x+1))
    gl.append(friendset)

max = 0

for x in gl:
    for y in dummy:
        if y[0] in x or y[1] in x:
            x.add(y[0])
            x.add(y[1])
            if max < len(x):
                max = len(x)

'''
for x in gl:
    for y in gl:
        if not x.isdisjoint(y):
            x = x | y
'''
print(max)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
friend=[]
for _ in range(M):
    a,b=map(int,input().split())
    if friend==[]:
        friend.append({a,b})
    for x,i in enumerate(friend):
        if (a in i)&(b in i):
            break
        elif a in i:
            friend[x].add(b)
            break
        elif b in i:
            friend[x].add(a)
            break
        elif x==len(friend)-1:
            friend.append({a,b})
maxmax=0
for i in friend:
    if maxmax<len(i):
        maxmax=len(i)
print(maxmax)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque


def LI():
    return list(map(int, input().split()))


N, M = LI()
friend = [set() for _ in range(N)]
ans = 0
miru = set()
if M == 0:
    print(0)
    sys.exit()
for i in range(M):
    a, b = map(int, input().split())
    friend[a-1].add(b-1)
    friend[b-1].add(a-1)
    miru.add(a-1)
    miru.add(b-1)
looked = [0]*N
d = deque()
count = 0
d.append(a-1)
miru.discard(a-1)
while d:
    x = d.pop()
    for i in friend[x]:
        if looked[i] != 0:
            continue
        count += 1
        looked[i] = 1
        d.append(i)

    if len(d) == 0:
        ans = max(count, ans)
        if len(miru) == 0:
            break
        y = miru.pop()
        d.append(y)
        looked[y] = 1
        count = 1
        miru.discard(y)

print(ans)

Submission status: Wrong Answer

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

ans = max(map(len, G))+1
print(ans)

Submission status: Wrong Answer

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

N,M = map(int, input().split())
lis = [0]*(N+1)
A = [0]*M; B = [0]*M
for i in range(M):
    a,b = map(int, input().split())
    a,b = min(a,b), max(a,b)
    
    lis_a = lis[a]
    if lis_a == 0:
        lis[a] = a
        if lis[b] == 0:
            lis[b] = a
        else:
            lis[lis[b]] = a
            lis[b] = a
    else:
        if a < lis_a:
            lis[a] = a
            lis[lis_a] = a
            lis[lis[b]] = a
            lis[b] = a
        else:
            lis[a] = lis_a
            lis[lis[b]] = lis_a
            lis[b] = lis_a

cntlis = [0]*(N+1)
for x in lis[1:]:
    cntlis[x] += 1
print(max(cntlis[1:]))

Submission status: Wrong Answer

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


def root(x):
    if x == par[x]:
        return x
    y = root(par[x])
    par[x] = y
    return y


def union(x, y):
    rx, ry = root(x), root(y)
    if rx != ry:
        if par[rx] > par[ry]:
            rx, ry = ry, rx
        par[ry] = rx


for _ in range(m):
    a, b = map(lambda x: int(x) - 1, input().split())
    union(a, b)
d = {}
for p in par:
    if p not in d:
        d[p] = 1
    else:
        d[p] += 1

print(max(d.values()))

Submission status: Wrong Answer

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


def root(x):
    if x == par[x]:
        return x
    y = root(par[x])
    par[x] = y
    return y


def union(x, y):
    rx, ry = root(x), root(y)
    if rx != ry:
        if rx > ry:
            rx, ry = ry, rx
        par[ry] = rx


for _ in range(m):
    a, b = map(lambda x: int(x) - 1, input().split())
    union(a, b)
d = {}
for p in par:
    if p not in d:
        d[p] = 1
    else:
        d[p] += 1

print(max(d.values()))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

N,Q = map(int,input().split())
par = [i for i in range(N)]
rank = [0]*(N+1)
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x]) #経路圧縮
        return par[x]
def same(x,y):
    return find(x) == find(y)
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x]==rank[y]:rank[x]+=1

for _ in range(Q):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  unite(a,b)
from collections import Counter
ca=Counter(par)
ans=0
for c in ca.values():
  ans=max(ans,c)
print(ans)

Submission status: Wrong Answer

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

N,Q = map(int,input().split())
par = [i for i in range(N+1)]
rank = [0]*(N+1)
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x]) #経路圧縮
        return par[x]
def same(x,y):
    return find(x) == find(y)
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x]==rank[y]:rank[x]+=1

for _ in range(Q):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  unite(a,b)
from collections import Counter
ca=Counter(par)
ans=0
for c in ca.values():
  ans=max(ans,c)
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
f=[[i] for i in range(n)]
for i in range(m):
	a,b=map(int,input().split())
	f[b-1]+=f[a-1]
	f[a-1]+=f[b-1]
print(max([len(set(i)) for i in f]))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
f=[[i] for i in range(n)]
for i in range(m):
	a,b=map(int,input().split())
	if a not in f[b-1]:
		f[b-1]+=f[a-1]
	if b not in f[a-1]:
		f[a-1]+=f[b-1]
print(max([len(set(i)) for i in f]))

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_sama(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb:
            return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]:
                self.rank[ra] += 1
        self.count += 1
    def print_info(self):
        print("parent", self.parent)
        print("rank", self.rank)
        print("count", self.count)

from collections import Counter
N, M = map(int,input().split())
uf = UnionFind(N)
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    uf.unite(a,b)
print(Counter(uf.parent).most_common(1)[0][1])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(4100000)
import math
import itertools
INF = float('inf')
from heapq import heapify, heappop, heappush
import collections


n,m = map(int, input().split())
par = [i for i in range(n)]
rank = [0]*n

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

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

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

    count = [0]*n
    for p in par:
        count[par[p]] += 1
    print(max(count))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(4100000)
import math
import itertools
INF = float('inf')
from heapq import heapify, heappop, heappush
import collections


n,m = map(int, input().split())
par = [i for i in range(n)]
rank = [0]*n

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

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

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

    count = [0]*n
    for p in par:
        count[p] += 1
    print(max(count))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(4100000)
import math
import itertools
INF = float('inf')
from heapq import heapify, heappop, heappush
import collections


n,m = map(int, input().split())
par = [i for i in range(n)]
rank = [0]*n

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

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

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

    count = [0]*n
    for p in par:
        count[p-1] += 1
    print(max(count))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(4100000)
import math
import itertools
INF = float('inf')
from heapq import heapify, heappop, heappush
import collections


n,m = map(int, input().split())
par = [i for i in range(n)]
rank = [0]*n

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

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

def main():
    for _ in range(m):
        a,b = map(int, input().split())
        unite(a-1,b-1)
    counter = collections.Counter(par)

    ans = counter.most_common()[0][1]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from networkx import*
#print(max(map(len,connected_components(Graph(map(str.split,[*open(0)][1:]))))))
#(n,m),*t=map(str.split,open(0));print(max(map(len,connected_components(Graph(t[:int(m)])))))
n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]
G = Graph()
G.add_edges_from(edges)
ccs = connected_components(G)
#ans = max(map(len, ccs))
#print(ans)