Problem:


Score : 400 points

Problem Statement

There are N persons called Person 1 through Person N.

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

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

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

At least how many groups does he need to make?

Constraints

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

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

1\leq A_i,B_i\leq N

A_i \neq B_i

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
\vdots
A_M B_M

Output

Print the answer.

Sample Input 1

5 3
1 2
3 4
5 1

Sample Output 1

3

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

Sample Input 2

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

Sample Output 2

4

Sample Input 3

10 4
3 1
4 1
5 9
2 6

Sample Output 3

3



Sample input:
5 3
1 2
3 4
5 1


Sample output:
3

Submission status: Wrong Answer

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

relations = {}

group_num = 1

for _ in range(M):
    Ai, Bi = map(int, input().split())
    exist_a = Ai in relations
    exist_b = Bi in relations

    if exist_a and exist_b:
        a = relations[Ai]
        b = relations[Bi]
        relations[Ai] = a | b
        relations.pop(Bi)
    elif exist_a:
        a = relations[Ai]
        a.add(Bi)
    elif exist_b:
        b = relations[Bi]
        b.add(Ai)
    else:
        found = False
        for group in relations.values():
            if Ai in group or Bi in group:
                group.add(Ai)
                group.add(Bi)
                found = False
        if not found:
            relations[Ai] = {Ai, Bi}

for group in relations.values():
    group_num = max(len(group), group_num)

print(group_num)

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 = 1
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
    if len(d) == 0:
        ans = max(count, ans)
        if len(miru) == 0:
            break
        miru = list(miru)
        y = miru[0]
        d.append(y)
        looked[y] = 1
        count = 1
        miru = set(miru)
        miru.discard(y)


print(ans)

Submission status: Wrong Answer

Solution code:

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


s = set()
L = []
ans = 0
for i in range(m):
    t1,t2 = map(int,input().split())
    if len(s) == 0:
        s.add(t1)
        s.add(t2)
    elif t1 in s or t2 in s:
        s.add(t1)
        s.add(t2)
    else:
        L.append([t1,t2])
else:
    ans = len(s)

#print(s,L,ans)

L2 = L
while len(L2) > 0:
    s = set() 
    L = []
    for i in range(len(L2)):
        t1= L2[i][0]
        t2= L2[i][1]
        if len(s) == 0:
            s.add(t1)
            s.add(t2)
        elif t1 in s or t2 in s:
            s.add(t1)
            s.add(t2)
        else:
            L.append([t1,t2])
    else:
        if ans < len(s):
            ans = len(s)
        L2 = L
#    print(L2)

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
 
n, m = map(int,input().split())

sub_total = [0] * n
joken = [[0] * n] * n
for i in range(m):
    a, b = map(int,input().split())
    mi = min(a,b)
    ma = max(a,b)
    if joken[mi - 1][ma - 1] == 0:
        joken[mi - 1][ma - 1] = 1
        sub_total[mi - 1] += 1
        sub_total[ma - 1] += 1

print(max(sub_total) + 1)

Submission status: Wrong Answer

Solution code:
import collections
N, M = map(int, input().split())
D = dict([(i,i) for i in range(1,N+1)])

L = []

for i in range(M):
    A, B = map(int, input().split())
    if A > B:
        A,B = B,A
    L += [(A,B)]

L = list(set(L))
L.sort()

#print(L)

for i in L:
    A,B = i
    m = min([D[A], D[B]])
    D[A] = m
    D[B] = m
    #print(D)
D = collections.Counter(D.values())
print(max(D.values()))

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] != 0 and lst[B] != 0:     # 集合の結合(完全グラフ化)
        if lst[A] != lst[B]:
            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)
if num == 1:
    ans = 1
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int, input().split())
l = {0}
L = [{}]
for m in range(M):
  A,B = map(int, input().split())
  if not (A in l) and not (B in l):
    L.append({A,B})
    l.add(B)
    l.add(A)
  else:
    An = 0
    Bn = 0
    for n in range(len(L)):
      if A in L[n]:
        An = n
      if B in L[n]:
        Bn = n
    if An == 0:
      As = {A}
    else:
      As = L[An]
    if Bn == 0:
      Bs = {B}
    else:
      Bs = L[Bn]
    L.append(As.union(Bs))
    if An != 0:
      L[An] = {}
    if Bn != 0:
      L[Bn] = {}      
print(max([len(m) for m in L]))

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
mInfos = [list(map(int, input().split())) for _ in range(M)]
gl = [0]*N
mc = [0]*N
gc = 0
guru = []
for i in range(M):
    mInfo = mInfos[i]
    p1 = mInfo[0]
    p2 = mInfo[1]
    naiflag = True
    if gl[p1-1] == 0 and gl[p2-1] == 0:
        gl[p1 - 1] = gc + 1
        gl[p2 - 1] = gc + 1
        mc[gc] = 2
        gc += 1
    elif gl[p1-1] != 0 and gl[p2-1] == 0:
        gl[p2 - 1] = gl[p1-1]
        mc[p1-1] += 1
    elif gl[p2-1] != 0 and gl[p1-1] == 0:
        gl[p1 - 1] = gl[p2 - 1]
        mc[p2 - 1] += 1
    else:
        if gl[p2-1] == gl[p1-1]:
            continue
        gl = [gl[p1-1] if j == gl[p2-1] else j for j in gl]
        #print(gl)
        mc[p1 - 1] += mc[p2 - 1]
        mc[p2 - 1] = 0
        gc -= 1
mi = 0
#print(gl)
for i in range(1,gc+1):
    dd = gl.count(i)
    mi = max(mi,dd)
print(mi)

Submission status: Wrong Answer

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

def main():
    import bisect, collections, copy, heapq, itertools, math, string
    import sys
    def I():
        return int(sys.stdin.readline().rstrip())

    def MI():
        return map(int, sys.stdin.readline().rstrip().split())

    def LI():
        return list(map(int, sys.stdin.readline().rstrip().split()))

    def S():
        return sys.stdin.readline().rstrip()

    def LS():
        return list(sys.stdin.readline().rstrip().split())

    def main():
        from collections import deque
        N, M = MI()
        fri_list = []
        num_list = [0] * (N + 1)
        for i in range(M):
            a, b = MI()
            if num_list[a] == 0 and num_list[b] == 0:
                fri_list.append([a, b])
            elif num_list[a] == 0 or num_list[b] == 0:
                for l in fri_list:
                    if a in l:
                        l.append(b)
                    elif b in l:
                        l.append(a)
            else:
                continue
            num_list[a] = num_list[b] = 1

        len_list = []
        for l in fri_list:
            x = len(l)
            len_list.append(x)
        ans = max(len_list)
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
if M == 0:
  print(0)
else:
  friends = [list(map(int, input().split())) for _ in range(M)]
  pairs = [[] for _ in range(N+1)]
  friendships = [1 for __ in range(N+1)]
  for x, y in friends:
    if x < y:
      pairs[x].append(y)
    else:
      pairs[y].append(x)
  for i, pair in enumerate(pairs):
    if len(pair) > 0:
      nums = set(pair)
      sets = [friendships[i]]
      for num in nums:
        if friendships[i] == friendships[num]:
          count = 1
          while(True):
            if count in sets:
              count +=1
            else:
              break
          friendships[num] = count
        sets.append(friendships[num])
  print(max(friendships))

Submission status: Wrong Answer

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

friend_list = [set()]
input_list = []

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

input_list.sort()

for inp in input_list:
    found = False
    for friend_set in friend_list:
        if inp[0] in friend_set:
            friend_set.add(inp[1])
            found = True
            break
        # elif b in friend_set:
        #     friend_set.add(a)
        #     found = True
        #     break
    if not found:
        friend_set = set()
        friend_set.add(inp[0])
        friend_set.add(inp[1])
        friend_list.append(friend_set)

ans = 0
for friend_set in friend_list:
    ans = max(len(friend_set), ans)

print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
F = {}
for _ in range(M):
    A, B = map(int, input().split())
    if not A in F.keys():
        F[A] = []
    if not B in F.keys():
        F[B] = []
    F[A].append(B)
    F[B].append(A)
if F.keys() == 0:
    print(1)
else:
    ans = 1
    for f in F.values():
        ans = max(ans, len(list(set(f)))+1)
    print(ans)

Submission status: Wrong Answer

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

for i in range(M):
  a,b=AB[i]
  T[a].append(b)

for i in range(M):
  a,b=AB[i]
  T[a]=list(set(T[a]+T[b]))

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

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
A = [[] for i in range(N)]
checkd = [False]*N
for _ in range(M):
    a,b = (map(lambda a: int(a)-1, input().split()))
    if a <= b:
        A[a].append(b)
    else:
        A[b].append(a)
nextS = set(range(N))
ans = 0
while len(nextS)>0:
    s = nextS.pop()
    if checkd[s]: 
        continue
    count = 0
    que = [s]
    while len(que)>0:
        nn = que.pop(0)
        if checkd[nn]:
            continue
        checkd[nn] = True
        nextS.discard(nn)
        count += 1
        que += A[nn]
    ans = max(count,ans)


print(ans)

Submission status: Wrong Answer

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

n,m=map(int,input().split())
p = [tuple(sorted(list(map(int,input().split())))) for ii in range(m)]
p=set(p)

m=len(p)

g=[-1]*(n+1)
r=0

p2=list()

rr=[2]
#print(g)
import numpy as np
for pii in p:
  if g[pii[0]]<0 and g[pii[1]]<0:
    g[pii[0]]=r
    g[pii[1]]=r
    if r>0:
      rr.append(2)
    r+=1
  elif g[pii[0]]>=0 and g[pii[1]]>=0:
    g0=g[pii[0]]
    g1=g[pii[1]]
    if g0!=g1:
      p2.append((g[pii[0]],g[pii[1]]))
  elif g[pii[0]]>=0:
    g[pii[1]]=g[pii[0]]
    rr[g[pii[0]]]+=1
  elif g[pii[1]]>=0:
    g[pii[0]]=g[pii[1]]
    rr[g[pii[1]]]+=1
  #print(g)
  #print(pii,r,rr)
#print(g)
#print(p2)
for p2ii in p2:
  g0=g[p2ii[0]]
  g1=g[p2ii[1]]
  if g0!=g1:
    #print(g0,g1)
    if rr[g0]>rr[g1]:
      g0,g1=g1,g0
      rr[g1]+=rr[g0]
      rr[g0]=0

#print(rr)
print(max(rr))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
if M == 0:
    print(1)
else:
    D = {}
    count = 0
    friends = []
    while count < M:
        A, B = map(int,input().split())
        if A not in D and B not in D:
            friends = friends + [[A,B]]
            D[A] = len(friends) - 1
            D[B] = len(friends) - 1
        elif A in D and B not in D:
            friends[D[A]] = friends[D[A]] + [B]
            D[B] = D[A]
        elif B in D and A not in D:
            friends[D[B]] = friends[D[B]] + [A]
            D[A] = D[B]
        count += 1
    print(max(len(f) for f in friends))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
friends_set_list = [set() for i in range(N+1)]
friends_subset_list = [set() for i in range(N+1)]
for i in range(M):
    A, B = map(int, input().split())
    friends_set_list[A].add(B)
    friends_set_list[B].add(A)
    friends_subset_list[A] |= friends_set_list[B]
    friends_subset_list[B] |= friends_set_list[A]
ans = 0 
for i in range(N):
    friends_set_list[i] |= friends_subset_list[i]
    num = len(friends_set_list[i])
    if num > ans:
        ans = num

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

N, M = map(int, input().split())
g = {i:set() for i in range(N)}
v = [-1 for i in range(N)]
for _ in range(M):
  a, b = map(int, input().split())
  a, b = a-1, b-1
  g[a].add(b)
  g[b].add(a)

Q = deque()
ans = 0
for a in g:
  if v[a]==-1:
    v[a] = 1
    ans_tmp = 1
    Q.append(a)
    while len(Q)>0:
      na = Q.popleft()
      for nb in g[a]:
        if v[nb] == -1:
          v[nb] = 1
          ans_tmp += 1
          Q.append(nb)
    ans = max(ans, ans_tmp)
print(ans)

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] = sorted([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]
    elif people[a] != people[b]:
        t = max(people[a], people[b])
        u = min(people[a], people[b])
        for i in range(n):
            if people[i] == t: people[i] = u

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

Submission status: Wrong Answer

Solution code:
def main():
    n,m=map(int,input().split())
    g=[set([i]) for i in range(n)]
    ab=[tuple(map(lambda x: int(x)-1,input().split())) for _ in range(m)]
    for a,b in ab:
        g[a] |= g[b]
        g[b] |= g[a]
    print(max(len(a) for a in g))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, M = (int(x) for x in input().split())
import collections
Parent = [i for i in range(N)]
def fp(i):
    global Parent
    if Parent[i] == i:
        return i
    else:
        Parent[i] = fp(Parent[i])
        return Parent[i]

for _ in range(M):
    a, b = (int(x) for x in input().split())
    c, d = min(a,b)-1, max(a,b)-1
    Parent[c] = Parent[d] = min(fp(c), fp(d))

Groupsize = collections.defaultdict(lambda:0)
for i in range(N):
    i = fp(i)
    Groupsize[i] +=1
ans = max(gs for gs in Groupsize.values())
print(ans)

Submission status: Wrong Answer

Solution code:
fst_line = input().split(" ")
p_num = int(fst_line[0])
joken_num = int(fst_line[1])

if joken_num == 0:
    print(1)

else:
    joken_list = []
    for i in range(joken_num):
        temp = input().split(" ")
        temp_list = [int(n) for n in temp]
        if(temp_list[1] < temp_list[0]):
            tmp = temp_list[1]
            temp_list[1] = temp_list[0]
            temp_list[0] = tmp
        
        temp_line = (str(temp_list[0])+" "+str(temp_list[1]))
        
        joken_list.append(temp_line)
    
    #joken_list.sort()
    #print(joken_list)
    
    del_list=[]
    for i in range(joken_num - 1):
        if(joken_list[i]==joken_list[i+1]):
            del_list.append(i+1)
    del_list.sort(reverse = True)
    for i in range(len(del_list)):
        del joken_list[del_list[i]]
    
    #print(joken_list)
    
    group_list = []
    for i in range(p_num):
        group_list.append(i)
        
    num_joken_list = []
    for i in range(len(joken_list)):
        temp = joken_list[i].split(" ")
        temp_list = []
        temp_list.append(int(temp[0]))
        temp_list.append(int(temp[1]))
        num_joken_list.append(temp_list)
        
    num_joken_list.sort()
    #print(num_joken_list)
    
    #print(group_list)
    for i in range(len(num_joken_list)):
        a = num_joken_list[i][0]
        b = num_joken_list[i][1]
        #print(a,end=" ")
        #print(b)
        #print(group_list[b - 1],end=" ")
        group_list[b - 1] = group_list[a - 1]
        #print(group_list[b - 1])    
        
    group_list.sort()
    #print(group_list)
    
    max_num = 1
    temp = 1
    for i in range(p_num - 1):
        if group_list[i]==group_list[i+1]:
            temp +=1
        else:
            if temp > max_num:
                max_num = temp
            temp = 1
    
    if temp > max_num:
        max_num = temp
        
    print(max_num)

Submission status: Wrong Answer

Solution code:
from sys import stdin
def main():
  N, M = map(int, input().split())
  lst = [list(map(int, stdin.readline().split())) for _ in range(M)]
  
  f_lst = [[] for i in range(N)]
  count = [0] * N
  
  for A, B in lst:
    if not B in f_lst[A-1] and not A in f_lst[B-1]:
      f_lst[A-1].append(B)
      f_lst[B-1].append(A)
      count[A-1] += 1
      count[B-1] += 1
  print(max(count)+1)

main()

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(M)]
ANS = {i: [] for i in range(N)}
for i in range(M):
    ANS[AB[i][0]-1].append(AB[i][1]-1)
    ANS[AB[i][1]-1].append(AB[i][0]-1)
ans = sorted(ANS.items(), key=lambda x: len(set(x[1])))
print(len(set(ans[-1][1]))+1)

Submission status: Wrong Answer

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

# import numpy as np
# from numba import jit

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:

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


s = set()
L = []
ans = 0
for i in range(m):
    t1,t2 = map(int,input().split())
    if len(s) == 0:
        s.add(t1)
        s.add(t2)
    elif t1 in s or t2 in s:
        s.add(t1)
        s.add(t2)
    else:
        L.append([t1,t2])
else:
    ans = len(s)

#print(s,L,ans)

L2 = L
while len(L2) > 0:
    s = set() 
    L = []
    for i in range(len(L)):
        t1= L2[0][0]
        t2= L2[0][1]
        if len(s) == 0:
            s.add(t1)
            s.add(t2)
        elif t1 in s or t2 in s:
            s.add(t1)
            s.add(t2)
        else:
            L.append([t1,t2])
    else:
        if ans < len(s):
            ans = len(s)
        L2 = L
#    print(L2)

print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
C = [{i + 1} for i in range(N)] #友人グループ
ans = 1
for i in range(M):
    A, B = map(int, input().split())
    D = {A, B} # A B 含む友人グループ
    E = []
    for d in C:
        
        if d & D != set():
            D = d | D
            C.remove(d)
            
        
    a = len(D)
    if a > ans:
        ans = a
    C.append(D)

print(ans)

Submission status: Wrong Answer

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

listA3=[]
listB3=[]
listA2=[]
listB2=[]
for i in range(m):
  a,b=map(int, input().split())
  list1.append((a,b))
list1=set(list1)

for i in list1:
  a2=str(i[0])
  b2=str(i[1])
  listA2.append(a2)
  listB2.append(b2)
  
for i in range(n):
  a3=listA2.count(str(i))
  listA3.append(int(a3))
  b3=listB2.count(str(i))
  listB3.append(int(b3))

ans=0
ans=max(listB3+listA3)

if ans==1:
  print(m)
else:
  ans=ans+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)
    if lis[a] == 0:
        lis[a] = a
    else:
        lis[b] = lis[a]

lis.sort()
maxcnt = 0
cnt = 0
prev = -1
for i in range(1,N+1):
    if lis[i] == 0:
        continue
    if prev == -1:
        prev = lis[i]
        cnt += 1
    elif lis[i] == prev:
        cnt += 1
    else:
        maxcnt = max(maxcnt, cnt)
        cnt = 0
print(maxcnt)

Submission status: Wrong Answer

Solution code:
def resolve():
  N, M = map(int, input().split(" "))
  checked = [False] * (N + 1)
  # frend_labels = [0] * (N + 1)
  # frend_labels_counter = [0] * (N + 1)
  num_of_friend = [0] * (N + 1)
  friends = [None] * (N + 1)

  maximam_group = 0
  for _ in range(M):
    A, B = map(int, input().split(" "))

    if friends[A] == None and friends[B] == None:
      friends[A] = set()
      friends[A].add(A)
      friends[A].add(B)
      friends[B] = set()
      friends[B].add(A)
      friends[B].add(B)
    elif friends[A] == None:
      friends[B].add(A)
      friends[A] = friends[B]
    elif friends[B] == None:
      friends[A].add(B)
      friends[B] = friends[A]
    else:
      union = friends[A] | friends[B]
      friends[A] = union
      friends[B] = union

    if len(friends[A]) > maximam_group:
      maximam_group = len(friends[A])

  # for friend in friends:
  #   print(friend)
  print(maximam_group)

if __name__ == "__main__":
  resolve()

Submission status: Wrong Answer

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


for i in range(m) :
  a_list[i]=len(list(set(a_list[i])))+1

print(max(a_list))

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
friends_set=set()
for i in range(M):
    a,b=map(int,input().split())
    if a>b:
        a,b=b,a
    friends_set.add((a,b)) 
    
friends_list=[[] for _ in range(N+1)]

for f in friends_set:
    friends_list[f[0]].append(f[1])
    friends_list[f[1]].append(f[0])

max_len=0
for i in friends_list:
    max_len=max(max_len,len(i)+1)
    
print(max_len)

Submission status: Wrong Answer

Solution code:
import copy

n,m = map(int,input().split())
f = []

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

nf = []

for i in range(len(f)):
    cf = set()
    cf.add(f[i][0])
    cf.add(f[i][1])
    for j in range(i+1,len(f)):
        if f[i][0] in f[j]:
            cf.add(f[j][0])
            cf.add(f[j][1])
        elif f[i][1] in f[j]:
            cf.add(f[j][0])
            cf.add(f[j][1])
    nf.append(cf)

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

print(ans)








print(ans)

Submission status: Wrong Answer

Solution code:
def solve():
    n, m = map(int, input().split())
    group = []
    done = [-1]*n
    num = 0
    for i in range(m):
        a, b = map(lambda x:int(x)-1, input().split())
        if done[a] != -1:
            if done[b] == -1:
                group[done[a]].append(b)
                done[b] = done[a]
        else:
            if done[b] == -1:
                group.append([a,b])
                done[a], done[b] = num, num
                num += 1
            else:
                group[done[b]].append(a)
                done[a] = done[b]
    people = [0]+[len(i) for i in group]
    ans = max(people)
    amari = done.count(-1)
    if amari >= sum(people):
        print(ans-sum(people)+amari)
    else:
        print(ans)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys
from io import StringIO
import unittest

from collections import deque

# DFSで連結成分求める
def resolve():
    # s = input()
    # n = int(input())
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in range(m)]
    seen = set()

    graph = [[] for _ in range(n + 1)]

    # 線形
    for a, b in ab:
        if b not in set(graph[a]):
            graph[a] += [b]
        if a not in set(graph[b]):
            graph[b] += [a]

    que = deque()
    renketsu = []

    for ss in range(1, n + 1):
        if ss not in seen:
            tmp_renketsu = set()
            que.append(ss)
            while que:
                next_point = que.popleft()
                seen.add(next_point)
                # tmp_renketsu.add(next_point)
                # print(tmp_renketsu, seen)

                for point in set(graph[next_point]) - (set(graph[next_point]) & tmp_renketsu):
                # if graph[next_point]:
                #     for point in graph[next_point]:
                #        if point not in tmp_renketsu:
                    que.append(point)
                    tmp_renketsu.add(point)
            l = len(tmp_renketsu)
            renketsu.append(l)
            if l == m + 1:
                break

    print(max(renketsu))


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """5 3
1 2
3 4
5 1"""
        output = """3"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """4 10
1 2
2 1
1 2
2 1
1 2
1 3
1 4
2 3
2 4
3 4"""
        output = """4"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """10 4
3 1
4 1
5 9
2 6"""
        output = """3"""
        self.assertIO(input, output)


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
connect = []
ls = [0 for _ in range(N)]
flg = 1
count = [0 for _ in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    if ls[a-1] == 0 and ls[b-1] == 0:
        ls[a-1]=flg
        ls[b-1]=flg
        count[flg] +=2
        flg+=1
    elif ls[a-1] == 0:
        ls[a-1] = ls[b-1]
        count[ls[b-1]] +=1
    elif ls[b-1] == 0:
        ls[b-1] = ls[a-1]
        count[ls[a-1]] +=1
    else:
        check = [ls[a-1],ls[b-1]]
        connect.append(check)
connect.sort()
connect.reverse()
for j in connect:
    count[min(j)-1] += count[max(j)-1]
    count[max(j)-1] = 0
print(max(count))

Submission status: Wrong Answer

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

fri = []
chain = []

for i in range(M):
  fri.append( list(map(int, input().split())) )


for fr in fri:
  frag = False
  for i,ch in enumerate(chain):
    if fr[0] in ch and fr[1] not in ch:
      chain[i].append(fr[1])
      frag = True
      break
    elif fr[1] in ch and fr[0] not in ch:
      chain[i].append(fr[0])
      frag = True
      break
      
  if not(frag):
    chain.append(fr)

max = 0
for ch in chain:
  if len(ch)>max:
    max = len(ch)

print(max)

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 and people[b] != -1 and people[a] != people[b]:
        group[people[a]].update(group[people[b]])
        group[people[b]] = group[people[a]]
    elif 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:
# -*- coding: utf-8 -*-
def main():
    N,M  = [int(i) for i in input().split()]
    g = [[] for i in range(N)]
    #print(g)
    for i in range(M):
        a, b = [int(i) for i in input().split()]
        if a < b:
            if b-1 not in g[a-1]:
                g[a-1].append(b-1)
                if len(g[b-1]) != 0:
                     g[a-1].extend(g[b-1])
                     g[b-1] = []
        else:
            if a-1 not in g[b-1]:
                g[b-1].append(a-1)
                if len(g[a-1]) != 0:
                     g[b-1].extend(g[a-1])
                     g[a-1] = []
    print(max([len(v) for v in g])+1)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

cnt = [0] * n
for i in range(n):
    cnt[i] = len(l[i])

print(max(cnt))

Submission status: Wrong Answer

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


def bellman_ford(s):
    d = [float('inf')]*n # 各頂点への最小コスト
    d[s] = 0 # 自身への距離は0
    for i in range(n):
        update = False # 更新が行われたか
        for x, y, z in g:
            if d[y] > d[x] + z:
                d[y] = d[x] + z
                update = True
        if not update:
            break
        # 負閉路が存在
        if i == n - 1:
            return -1
    return d


# n, w = [int(x) for x in input().split()] # n:頂点数, w:辺の数
g = []
for a, b in AB:
    # x, y, z = [int(x) for x in input().split()] # 始点,終点,コスト
    g.append([a-1, b-1, 1])
    g.append([b-1, a-1, 1]) # 有向グラフでは削除
res = bellman_ford(0)
print(len([n for r in res if r != float('inf')]))