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:
def resolve():
    N, M = map(int, input().split())

    person_group = [0] * (N+5)
    group_counter = 0
    menber_counter = [0]

    for _ in range(M):
        A, B = map(int, input().split())
        if person_group[A] == 0 and person_group[B] == 0:
            group_counter += 1
            person_group[A] = group_counter
            person_group[B] = group_counter
            menber_counter.append(2)
        elif person_group[A] != 0 and person_group[B] != 0:
            continue
        elif person_group[A] != 0 and person_group[B] == 0:
            person_group[B] = person_group[A]
            menber_counter[person_group[A]] += 1
        else:
            person_group[A] = person_group[B]
            menber_counter[person_group[B]] += 1
    print(max(menber_counter))

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
from collections import deque
input = sys.stdin.readline

G = defaultdict(set)
N, M = map(int, input().split())
AB = set()
for _ in range(M):
  A, B = map(int, input().split())
  if B > A:
    A, B = B, A
  G[A].add(B)
  G[B].add(A)
print(G)
color = [0 for i in range(N+1)]
color[1] = 1
que = deque([1])   # 始点を追加
bipartite = True

while len(que):
  p = que.popleft()
  for q in list(G[p]):
    if color[q] == 0:
      # 塗られていないならば別の色で塗る
      color[q] = color[p] + 1
      que.append(q)
    elif color[q] == color[p]:
      color[q] = color[p] + 1

result = list(set(color[1:]))
print(len(result))

Submission status: Wrong Answer

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


def root(a):
    if a == tree[a]:
        return a
    b = root(tree[a])
    tree[a] = b
    return tree[a]


def same(a, b):
    return root(a) == root(b)


def unite(a, b):
    if same(a, b):
        pass
    ra, rb = root(a), root(b)
    if ra > rb:
        ra, rb = rb, ra
    tree[rb] = ra


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

d = {}
for t in tree:
    if t not in d:
        d[t] = 1
    else:
        d[t] += 1

print(max(d.values()))

Submission status: Wrong Answer

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

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

for i in range(n):
    ans_list[i] = len(set(f_l[i]))

print(max(ans_list))

Submission status: Wrong Answer

Solution code:
N, M = [int(n) for n in input().split(" ")]
friends = []
for _ in range(M):
    a, b = [int(n) for n in input().split(" ")]
    friends.append([a - 1, b - 1])

X = [[0 for _ in range(N)] for _ in range(N)]

def show(m):
    for i in range(len(m)):
        print(m[i])

#show(X)

for f in friends:
    X[f[0]][f[1]] = 1
    X[f[1]][f[0]] = 1

#show(X)

groups = []

for n in range(N):
    already = False
    for g in groups:
        if n in g:
            already = True
            break
    if already:
        continue
    queue = [n]
    group = []
    while len(queue) > 0:
        nowNode = queue[0]
        del(queue[0])
        nextQueue = []
        for i in range(N):
            if X[nowNode][i] == 1 and i not in group:
                group.append(i)
                nextQueue.append(i)
        queue = nextQueue
        nextQueue = []
    groups.append(group)

#print(groups)

score = 0
for g in groups:
    #print(g)
    s = len(g)
    if score <= s:
        score = s
print(score)

Submission status: Wrong Answer

Solution code:
m,n=map(int,input().split())
a_list=[0 for i in range(m)]
m_list=[]
for i in range(n) :
  a,b = map(int, input().split())
  if a>b :
    m_list.append(str(a)+' '+str(b))
  else :
    m_list.append(str(b) +' '+ str(a))

m_list=list(set(m_list))

for s in m_list :
  a,b=s.split()
  a_list[int(a)-1]+=1
  a_list[int(b)-1]+=1




print(max(a_list)+1)

Submission status: Wrong Answer

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

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

        for i in range(len(lis1)):
            if len(lis1[i]) == 0:
                lis1[i].append(a)
                lis1[i].append(b)
                break
            elif a not in lis1[i] and b in lis1[i]:
                lis1[i].append(a)
                break
            elif a in lis1[i] and b not in lis1[i]:
                lis1[i].append(b)
                break
    ans = 0
    for j in range(len(lis1)):
        tmp = len(lis1[j])
        if ans < tmp:
            ans = tmp

    print(ans)
        

    

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N, M = map(int, input().split())
    person = [set() for i in range(N)]

    for i in range(M):
        A, B = map(int, input().split())

        person[A - 1].add(B - 1)
        person[B - 1].add(A - 1)

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

    print(ans + 1)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

N,M= (int(x) for x in input().rstrip('\n').split())
res = 1
aed = []
f = []
for _ in range(M):
  A,B = (int(x) for x in input().rstrip('\n').split())
  if A not in aed:
    if B not in aed:
      f.append([A,B])
      aed.append(A)
      aed.append(B)
    else:
      for x in f:
        if B in x:
          x.append(A)
          aed.append(A)
          break
  elif B not in aed:
    for x in f:
      if A in x:
        x.append(B)
        aed.append(B)
        break
if len(f)>0:
  l = [len(x) for x in f]
  print(max(l))
else:
  print(1)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
array = [-1] * n
for i in range(m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  
  if a > b:
    a,b = b,a
    
  if array[a] == -1:
    array[b] = a
    
  else:
    array[b] = array[a]

ans_array = [0] * n

for i in range(n):
  if array[i] != -1:
    ans_array[array[i]] += 1
    
print(max(ans_array)+1)

Submission status: Wrong Answer

Solution code:
from collections import deque
N,M = map(int,input().split())
l = [[] for _ in range(N+1)]

for _ in range(M):
  a,b = map(int,input().split())
  l[a].append(b)
  l[b].append(a)
ans = 0
check = [0]*(N+1)
for i in range(1,N+1):
  st = deque(l[i])
  cnt = 0
  while st:
    s = st.popleft()
    for t in l[s]:
      if check[t] == 0:
        check[t] = 1
        st.append(t)
        cnt += 1
  ans = max(ans,cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
def input(): return sys.stdin.readline().rstrip()


def main():
    n, m = map(int, input().split())
    li = {}
    if m == 0:
        print(n)
        return

    for _ in range(m):
        a, b = sorted(map(int, input().split()))
        if a not in li:
            li[a] = {b}
        else:
            li[a].add(b)
    i = max(li, key=lambda k: len(li[k]))
    print(len(li[i]) + 1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
(n,m),*e=[[*map(int,i.split())]for i in open(0)]
d=[[]for i in range(n+1)]
dd=[[]for i in range(n+1)]
for i,j in e:
    d[i]+=[j]
    d[j]+=[i]
a=[]
for i in range(n+1):
    dd[i]=list(set(d[i]))
    if len(a)<len(dd[i]):a=dd[i]
b=[]
for i in a:
    b+=dd[i]
print(len(set(a+b)))

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
from decimal import *
import heapq
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

def dfs(human):
    res = [human]
    for n_human in r[human]:
        res.extend(dfs(n_human))
    res = set(res)
    return res

n, m = MAP()
r = [set([]) for _ in range(n)]
for _ in range(m):
    a, b = MAP()
    a -= 1
    b -= 1
    if b < a:
        a, b = b, a
    r[a].add(b)
#print(r)
ans = 1
ans_set = set([])
for i in range(n):
    if i in ans_set:
        continue
    tmp = dfs(i)
    ans = max(ans, len(tmp))
    #print(i, tmp)
    for j in tmp:
        ans_set.add(j)
print(ans)

Submission status: Wrong Answer

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


def root(a):
    if a == tree[a]:
        return a
    b = root(tree[a])
    tree[a] = b
    return tree[a]


def same(a, b):
    return root(a) == root(b)


def unite(a, b):
    if same(a, b):
        pass
    if a > b:
        a, b = b, a
    ra, rb = root(a), root(b)
    tree[rb] = tree[ra]


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

d = {}
for t in tree:
    if t not in d:
        d[t] = 1
    else:
        d[t] += 1

print(max(d.values()))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
ex = [0 for i in range(n)]
fri = {}

for i in range(m):
    a, b = map(int, input().split())
    if ex[a-1] == 0 and ex[b-1] == 0:
        if a > b:
            a, b = b,a
        ex[a-1] = a
        ex[b-1] = a
        fri[a] = [a, b]
    elif ex[a-1] == 0:
        ex[a-1] = ex[b-1]
        fri[ex[b-1]].append(a)
    elif ex[b-1] == 0:
        ex[b-1] = ex[a-1]
        fri[ex[a-1]].append(b)
    elif ex[a-1] == ex[b-1]:
        continue
    else:
        shozoku = min(ex[a-1], ex[b-1])
        mu = max(ex[a-1], ex[b-1])
        for j in range(len(fri[mu])):
            ex[fri[mu][j]-1] = shozoku
        fri[shozoku].extend(fri.pop(mu))

ans = 0
for key in fri:
    ans = max(ans, len(fri[key]))
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = [list(map(int, input().split())) for i in range(m)]
b=[]
c=[]
for i in a:
    if((i[0] not in b) and (i[1] not in b)):
        c.append(i)
        b.append(i[0])
        b.append(i[1])
    else:
        for j in c:
            if((i[0] in j) or (i[1] in j)):
                c.append(list(set(j)|set(i)))
                c.remove(j)
p=0

for k in c:
    if(len(k)>p):
        p=len(k)
print(p)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n: int) -> None:
        self.forest = [-1] * n

    def union(self, x: int, y: int) -> None:
        x = self.findRoot(x)
        y = self.findRoot(y)
        if x == y:
            return
        if self.forest[x] > self.forest[y]:
            x,y = y,x
        self.forest[x] += self.forest[y]
        self.forest[y] = x
        return

    def findRoot(self, x: int) -> int:
        if self.forest[x] < 0:
            return x
        else:
            self.forest[x] = self.findRoot(self.forest[x])
            return self.forest[x]

    def issame(self, x: int, y: int) -> bool:
        return self.findRoot(x) == self.findRoot(y)

    def size(self,x: int) -> int:
        return -self.forest[self.findRoot(x)]


n,m = map(int,input().split())
ab = [tuple(map(int,input().split())) for i in range(m)]
uf = UnionFind(n)
for ai,bi in ab:
    uf.union(ai-1,bi-1)

f = [False]*n
ans = 0
for i in range(n):
    for j in range(n):
        if not (uf.issame(i,j) or f[j]):
            f[i] = True
            f[j] = True
            ans += 1
            n -= 2
print(ans+n)

Submission status: Wrong Answer

Solution code:
n,m = [int(i) for i in input().split()]
d = []
for i in range(m):
  d.append(sorted([int(i) for i in input().split()]))
#print(sorted(d))

groups = list(range(n))
for t1,t2 in d:
  groups[t2-1] = groups[t1-1]
groups.sort()

pre = groups[0]
c = 0
t = 1
#print(groups)
for i in range(0,len(groups)):
  """
  if groups[i] == pre:
    t += 1
  else:
    t = 1
  pre = groups[i]
  """
  count = len([x for x in groups if x == groups[i]])
  c = max(c, count)
print(c)

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] == -1:
			group[M - 1] = m - 1
		else:
			group[M - 1] = group[m - 1]
	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:
# union find, bfs

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


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

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

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

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
li = [[] for i in range(N+1)]
for i in range(M):
  a, b = map(int, input().split())
  li[a].append(b)
  li[b].append(a)
  
ans = 0
for i in range(1, N+1):
  l = list(set(li[i]))
  for x in li[i]:
    for y in li[x]:
      if y == i:
        pass
      elif y in li[i]:
        pass
      else:
        l.append(y)
  ans = max(ans, len(set(l))+1)
print(ans)

Submission status: Wrong Answer

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

f_list = []
total_set = set()
for i in range(M):
    A = list(map(int, input().split()))
#    A = set(A)
    if A[0] in total_set or A[1] in total_set:
        for j in range(len(f_list)):
            if A[0] in f_list[j] or A[1] in f_list[j] :
                f_list[j] = f_list[j] | set(A)
                break
    else:
        f_list.append(set(A))
                     
    total_set = total_set | set(A)

best = 0
for i in range(len(f_list)):
    if len(f_list[i]) > best:
        best = len(f_list[i])
        
print(best)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline

N, M = map(int, input().split())
friend = [list(map(int, input().split())) for _ in range(M)]
d = {}
ans = 0
for i, e in enumerate(friend):
    if e[0] > e[1]:
        friend[i] = [e[1], e[0]]
friend.sort()
for e in friend:
    if e[0] not in d.keys():
        d[e[0]] = [e[1]]
    else:
        d[e[0]].append(e[1])



for e in d.values():
    e = set(e)
    ans = max(len(e)+1, ans)
print(ans)

Submission status: Wrong Answer

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

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

#print(numlist)

max = 0
for item in numlist:
    length = len(list(set(item)))
    if length>max:
        max = length
print(max+1)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
F = [[] for _ in range(M)]
for _ in range(M):
    A, B = map(int, input().split())
    for f in F:
        if len(f) == 0:
            f.append(A)
            f.append(B)
            break
        elif A in f:
            f.append(B)
            break
        elif B in f:
            f.append(A)
            break
ans = 0
for f in F:
    ans = max(ans, len(list(set(f))))
print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
x = [[]]
for a,b in ab:
    if x == [[]]:
        x[0] += [a,b]
    else:
        flag = False
        for i in range(len(x)):
            if a in x[i] or b in x[i]:
                if a not in x[i]: x[i].append(a)
                elif b not in x[i]: x[i].append(b)
                flag = True
        if not flag: x.append([a,b])
ans = 0
for i in x:
    ans = max(ans, len(i))
print(ans)

Submission status: Wrong Answer

Solution code:
nm = input('').split()
n = int(nm[0])
m = int(nm[1])

friends={}
for i in range(m):
    ab=input('').split()
    a = ab[0]
    b = ab[1]
    if a not in friends.keys():
        friends[a]=set()
    if b not in friends.keys():
        friends[b]=set()
    friends[a].add(b)
    friends[b].add(a)

mx=0
for k,v in friends.items():
#    print(v)
    len_v=len(v)
    if len_v>mx:
        mx=len_v
print(mx+1)

Submission status: Wrong Answer

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

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

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

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

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

    first = True
    next_gid = 0

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

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

        gids[a] = cur_gid
        for b in bs:
            gids[b] = cur_gid

        fa = a


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


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

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

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

main(pairs, n, m)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
k=[1]*(n+1)
for i in range(m):
    a,b=map(int,input().split())
    k[a]+=1;k[b]+=1
if max(k)>n:
    print(n)
else:
    print(max(k))

Submission status: Wrong Answer

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

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

s = 0
for j in range(n):
    s = max(s,len(l[j]))

print(s+1)

Submission status: Wrong Answer

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

friends = [[] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    friends[min(a,b)].append(max(a,b))

ans = -1
for i in range(N):
    ans = max(len(set(friends[i])), ans)

print(ans+1)

Submission status: Wrong Answer

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

fMap = {}
count = 0
lister = []

for i in range(m):
    a, b = map(int, input().split())
    if a in fMap:
        if not b in fMap:
            lister[fMap[a]].append(b)
        else:
            if fMap[a] != fMap[b]:
                de = fMap[b]
                lB = lister[fMap[b]]
                for e in lB:
                    lister[fMap[a]].append(e)
                    fMap[e] = fMap[a]
                lister[de] = []
        fMap[b] = fMap[a]
    elif b in fMap:
        if not a in fMap:
            lister[fMap[b]].append(a)
        fMap[a] = fMap[b]
    else:
        fMap[a] = count
        fMap[b] = count
        count+=1
        lister.append([a, b])

maxL = 0
for l in lister:
    if len(l) > maxL:
        maxL = len(l)
print(maxL)

Submission status: Wrong Answer

Solution code:
from collections import Counter


def main():
    people_count, info_count = [int(x) for x in input().split()]
    frieds_circle_ids = [-1] * people_count
    new_id = 0
    for _ in range(info_count):
        a, b = [int(x) - 1 for x in input().split()]
        id_a = frieds_circle_ids[a]
        id_b = frieds_circle_ids[b]
        if id_a == -1 == id_b:
            frieds_circle_ids[a] = new_id
            frieds_circle_ids[b] = new_id
            new_id += 1
        elif id_a == -1:
            frieds_circle_ids[a] = id_b
        elif id_b == -1:
            frieds_circle_ids[b] = id_a
    return Counter(frieds_circle_ids).most_common()[0][1]


if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
class UnionFind:
  def __init__(self, n):
    self.parent = [i for i in range(n)]
    self.height = [0 for i in range(n)]
        
  def get_root(self, i):
    if self.parent[i] == i:
      return i
    else:
      self.parent[i] = self.get_root(self.parent[i])
      return self.parent[i]
            
  def unite(self, i, j):
    root_i = self.get_root(i)
    root_j = self.get_root(j)
    if root_i != root_j:
      if self.height[root_i] < self.height[root_j]:
        self.parent[root_i] = root_j
      else:
        self.parent[root_j] = root_i
        if self.height[root_i] == self.height[root_j]:
          self.height[root_i] += 1
                
  def is_in_group(self, i, j):
    if self.get_root(i) == self.get_root(j):
      return True
    else:
      return False
          
N, M = map(int, input().split())
uf = UnionFind(N)
for i in range(M):
  a, b = map(int, input().split())
  uf.unite(a-1, b-1)
X = [0]*N
for i in range(N):
  X[uf.parent[i]] += 1
print(max(X)+1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python

def main():
    n, m = map(int, input().split())
    ab_arr = []
    for _ in range(m):
        ab = list(map(int, input().split()))
        ab.sort()
        ab_arr.append(ab)

    ab_arr.sort(key=lambda ab: ab[0])
    parent = [i for i in range(n+1)]
    cnt = [0 for i in range(n+1)]

    for ab in ab_arr:
        a, b = ab
        parent[b] = parent[a]

    for p in parent:
        cnt[p] += 1

    print(max(cnt))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

for i in range(M):
    tmp = list(map(int, input().split()))
    tmp.sort()
    if tmp[0] in friends:
        friends[tmp[0]].append(tmp[1])
    else:
        friends[tmp[0]] = [tmp[0], tmp[1]]

ans = 0
for i in friends.values():
    i = set(i)
    ans = max(ans, len(i))
print(ans)

Submission status: Wrong Answer

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

s=set()
for i in range(m):
  a,b=map(int,input().split())
  if (a,b) in s or (b,a) in s:
    continue
  else:
    s.add((a,b))
d=[1]*n
for i in s:
  d[i[0]-1]+=1
  d[i[1]-1]+=1
print(max(d))

Submission status: Wrong Answer

Solution code:
from collections import deque

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

flag = [True for i in range(n)]
max_grupe = 0
for i in range(n):
  if(flag[i] == False):
    break
  num = 0
  queue = deque([i])
  flag[i] = False
  while queue:
    now = queue.popleft()
    num += 1
    for j in friend[now]:
      if(flag[j]):
        queue.append(j)
        flag[j] = False
        
  max_grupe = max(max_grupe, num)
  
print(max_grupe)

Submission status: Wrong Answer

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

tmplist = [[] for i in range(N)]
friendlist = [0 for i in range(N)]


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

result = 0

for i in tmplist:
    setlist = set(i)
    tmp = len(setlist)
    
    if result < tmp:
        result = tmp
    

print(result + 1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
def main():
    from collections import deque

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

    seen = set()
    friends_group = []
    for i in range(N):
        if i in seen:
            continue
        q = deque([i])
        tmp_group = [i]
        while q:
            now = q.popleft()
            if i in seen:
                continue
            seen.add(now)
            for j in friends_input[now]:
                if j not in seen:
                    q.append(j)
                    tmp_group.append(j)
        friends_group.append(tmp_group)
    ans = 0
    for i in friends_group:
        ans = max(ans, len(i))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
li = []
flag = 0
ans = 0
for _ in range(m):
    a, b = map(int, input().split())
    if li:
        for i in li:
            if flag == 0:
                if a in i:
                    if not b in i:
                        i.append(b)
                        ans = max(ans, len(i))
                    flag = 1
                elif b in i:
                    if not a in i:
                        i.append(a)
                        ans = max(ans, len(i))
                    flag = 1
        if flag == 0:
            li.append([a, b])
        flag = 0
    else:
        li.append([a, b])
        ans = 2
print(ans)

Submission status: Wrong Answer

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

G = []
m = {}
for _ in range(M):
    a, b = map(int, input().split())
    if a in m:
        gid = m[a]
        m[b] = gid
        G[gid].add(b)
    elif b in m:
        gid = m[b]
        m[a] = gid
        G[gid].add(a)
    else:
        G.append({a, b})
        m[a] = len(G) - 1
        m[b] = len(G) - 1

if M == 0:
    print(1)
else:
    print(max(len(g) for g in G))

Submission status: Wrong Answer

Solution code:
from collections import Counter

class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]
        
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
            

N, M = map(int, input().split())
UF = UnionFind(N)
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    big = max(a, b)
    small = min(a, b)
    UF.par[big] = small
    
for i in range(N):
    _ = UF.find(i)

c = Counter(UF.par)
print(max(c.values()))

Submission status: Wrong Answer

Solution code:
n,m=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
    elif rank[x]<rank[y]:
        par[x]=y
    else:
        par[y]=x
        if rank[x]==rank[y]:
            rank[x]+=1                 
for i in range(m):
    a,b=map(int,input().split()) 
    if a>b:
        a,b=b,a
    unite(a,b)
from collections import Counter
C=dict(Counter(par))
#print(par)
#print(C)
print(max(C.values()))

Submission status: Wrong Answer

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

par = [i for i in range(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:
    par[x] = y
  else:
    par[y] = x
  
for i in range(M):
  a, b = map(int, input().split())
  unite(a - 1, b - 1)
  
ans = [0] * N
Max = 0
for i in par:
  ans[i] += 1
for i in ans:
  if i > Max:
    Max = i
  
print(Max)

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])
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())
A,B=[],[]

l=[-1]*N

d={}
def getID(l,idx):
  if idx==-1:
    return -1
  while True:
    if idx==l[idx]:break
    idx=l[idx]
  return idx

for i in range(M):
  s=list(map(int,input().split()))
  s[0]-=1
  s[1]-=1
  if l[s[0]]==-1 and l[s[1]]==-1:
    l[s[0]]=s[0]
    l[s[1]]=s[0]
  elif l[s[0]]==-1 or l[s[1]]==-1:
    for j in range(2):
      if l[s[j]]==-1:
        l[s[j]]=l[s[(j+1)%2]]
  else:
    r1=getID(l,s[0])
    r2=getID(l,s[1])
    if getID(l,s[0])==getID(l,s[1]):continue
    l[r1]=r2

#d={}
#for i in range(N):
#  x=getID(l,i)
#  d.setdefault(x,0)
#  d[x]+=1
#ans=0
#for i in d:
#  ans=max(ans,d[i])
#print(ans)