Problem:


Score : 400 points

Problem Statement

There are N persons called Person 1 through Person N.

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

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

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

At least how many groups does he need to make?

Constraints

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

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

1\leq A_i,B_i\leq N

A_i \neq B_i

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
\vdots
A_M B_M

Output

Print the answer.

Sample Input 1

5 3
1 2
3 4
5 1

Sample Output 1

3

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

Sample Input 2

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

Sample Output 2

4

Sample Input 3

10 4
3 1
4 1
5 9
2 6

Sample Output 3

3



Sample input:
5 3
1 2
3 4
5 1


Sample output:
3

Submission status: Wrong Answer

Solution code:
from 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)

Submission status: Wrong Answer

Solution code:

import collections
from functools import lru_cache
import bisect

INF = float("inf")
ZERO = 0
ONE = 1


class UnionFind:
    def __init__(self):
        self.parents = {}
        self.sizes = {}

    def findParent(self, x):
        if x not in self.parents:
            self.parents[x] = x
            self.sizes[x] = 1

            return x

        if self.parents[x] != x:
            self.parents[x] = self.findParent(self.parents[x])

        return self.parents[x]

    def union(self, x, y):
        rootX, rootY = self.findParent(x), self.findParent(y)

        if rootX == rootY:
            return

        if self.sizes[rootX] < self.sizes[rootY]:
            self.sizes[rootY] += self.sizes[rootX]
            self.parents[rootX] = rootY
        else:
            self.sizes[rootX] += self.sizes[rootY]
            self.parents[rootY] = rootX

    def numberOfComponents(self):
        return sum(1 for x, p in self.parents.items() if x == p)


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


def readInt():
    return int(input().strip())


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


def solve(N, M, arr):
    uf = UnionFind()

    for i in range(N):
        uf.findParent(i)

    for u, v in arr:
        uf.union(u, v)

    counts = collections.Counter()

    for x, parent in uf.parents.items():
        counts[parent] += 1

    return max(counts.values())


N, M = readList()
arr = set()

for _ in range(M):
    arr.add(tuple(sorted(readList())))

print(solve(N, M, arr))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
ins = lambda: input().rstrip()
ini = lambda: int(input().rstrip())
inm = lambda: map(int, input().rstrip().split())
inl = lambda: list(map(int, input().split()))
out = lambda x: print('\n'.join(map(str, x)))

def dfs(x):
    stack = [x]
    visited = 0
    checked[x] = 1
    while stack:
        visited += 1
        node = stack.pop()
        for i in graph[node]:
            if checked[i] == 0:
                stack.append(i)
                checked[i] = 1
    return visited
 
n, m = inm()
checked = [0] * (n+1)
graph = {}
for i in range(m):
    a, b = inm()
    if a not in graph:
        graph[a] = set()
    if b not in graph:
        graph[b] = set()
    graph[a].add(b)
    graph[b].add(a)
ans = 0
for i in graph:
    if checked[i] == 0:
        ans = max(ans, dfs(i))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
ins = lambda: input().rstrip()
ini = lambda: int(input().rstrip())
inm = lambda: map(int, input().split())
inl = lambda: list(map(int, input().split()))
out = lambda x: print('\n'.join(map(str, x)))

def dfs(x):
    stack = [x]
    visited = 0
    checked[x] = 1
    while stack:
        visited += 1
        node = stack.pop()
        for i in graph[node]:
            if checked[i] == 0:
                stack.append(i)
                checked[i] = 1
    return visited
 
n, m = inm()
checked = [0] * (n+1)
graph = {}
for i in range(m):
    a, b = inm()
    if a not in graph:
        graph[a] = set()
    if b not in graph:
        graph[b] = set()
    graph[a].add(b)
    graph[b].add(a)
ans = 0
for i in graph:
    if checked[i] == 0:
        ans = max(ans, dfs(i))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
ins = lambda: input().rstrip()
ini = lambda: int(input().rstrip())
inm = lambda: map(int, input().split())
inl = lambda: list(map(int, input().split()))
out = lambda x: print('\n'.join(map(str, x)))

n, m = inm()
checked = [0] * (n+1)
graph = {}
for i in range(m):
    a, b = inm()
    if a not in graph:
        graph[a] = set()
    if b not in graph:
        graph[b] = set()
    graph[a].add(b)
    graph[b].add(a)


def dfs(x):
    stack = [x]
    visited = 0
    checked[x] = 1
    while stack:
        visited += 1
        node = stack.pop()
        for i in graph[node]:
            if checked[i] == 0:
                stack.append(i)
                checked[i] = 1
    return visited
 

ans = 0
for i in graph:
    ans = max(ans, dfs(i))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
ins = lambda: input().rstrip()
ini = lambda: int(input().rstrip())
inm = lambda: map(int, input().split())
inl = lambda: list(map(int, input().split()))
out = lambda x: print('\n'.join(map(str, x)))

def dfs(x):
    stack = [x]
    visited = 0
    checked[x] = 1
    while stack:
        visited += 1
        node = stack.pop()
        for i in graph[node]:
            if checked[i] == 0:
                stack.append(i)
                checked[i] = 1
    return visited
 
n, m = inm()
checked = [0] * (n+1)
graph = {}
for i in range(m):
    a, b = inm()
    if a not in graph:
        graph[a] = set()
    if b not in graph:
        graph[b] = set()
    graph[a].add(b)
    graph[b].add(a)
ans = 0
for i in graph:
    ans = max(ans, dfs(i))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
ins = lambda: input().rstrip()
ini = lambda: int(input().rstrip())
inm = lambda: map(int, input().split())
inl = lambda: list(map(int, input().split()))
out = lambda x: print('\n'.join(map(str, x)))

def dfs(x):
    stack = [x]
    visited = 0
    checked[x] = 1
    while stack:
        visited += 1
        node = stack.pop()
        for i in graph[node]:
            if checked[i] == 0:
                stack.append(i)
                checked[i] = 1
    return visited
 
n, m = inm()
checked = [0] * (n+1)
graph = {}
for i in range(m):
    a, b = inm()
    if a not in graph:
        graph[a] = []
    if b not in graph:
        graph[b] = []
    graph[a].append(b)
    graph[b].append(a)
ans = 0
for i in graph:
    ans = max(ans, dfs(i))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter, deque

n, m = map(int, input().split())
par = list(range(n + 1))


def find(x):
    q = deque()
    q.append(x)
    while len(q) > 0:
        v = q.pop()
        if v == par[v]:
            return v
        q.append(par[v])


def union(x, y):
    px, py = find(x), find(y)
    if px == py:
        return
    par[py] = px


qr = set()
for _ in range(m):
    a, b = map(int, input().split())
    if a > b:
        a, b = b, a
    qr.add((a, b))
for v in qr:
    union(v[0], v[1])

parc = Counter(par)
print(parc.most_common(1)[0][1])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
ins = lambda: input().rstrip()
ini = lambda: int(input().rstrip())
inm = lambda: map(int, input().split())
inl = lambda: list(map(int, input().split()))
out = lambda x: print('\n'.join(map(str, x)))

def dfs(x):
    stack = [x]
    visited = 0
    checked[x] = 1
    while stack:
        visited += 1
        node = stack.pop()
        for i in graph[node]:
            if checked[i] == 0:
                stack.append(i)
                checked[i] = 1
    return visited

n, m = inm()
checked = [0] * (n+1)
graph = {}
for i in range(m):
    a, b = inm()
    if a not in graph:
        graph[a] = []
    if b not in graph:
        graph[b] = []
    graph[a].append(b)
    graph[b].append(a)
ans = 0
for i in graph:
    if checked[i] == 0:
        ans = max(ans, dfs(i))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter, deque

n, m = map(int, input().split())
par = list(range(n + 1))
rank = [0] * (n + 1)


def find(x):
    q = deque()
    q.append(x)
    while len(q) > 0:
        v = q.pop()
        if v == par[v]:
            return v
        q.append(par[v])


def union(x, y):
    px, py = find(x), find(y)
    if px == py:
        return
    if rank[px] < rank[py]:
        par[px] = py
        return
    elif rank[px] == rank[py]:
        rank[px] += 1
    par[py] = px


qr = set()
for _ in range(m):
    a, b = map(int, input().split())
    if a > b:
        a, b = b, a
    qr.add((a, b))
for v in qr:
    union(v[0], v[1])

parc = Counter(par)
print(parc.most_common(1)[0][1])

Submission status: Wrong Answer

Solution code:
from collections import Counter, deque

n, m = map(int, input().split())
par = list(range(n + 1))
rank = [0] * (n + 1)


def find(x):
    q = deque()
    q.append(x)
    while len(q) > 0:
        v = q.pop()
        if v == par[v]:
            return v
        q.append(par[v])


def union(x, y):
    px, py = find(x), find(y)
    if px == py:
        return
    if rank[px] < rank[py]:
        par[px] = py
        return
    elif rank[px] == rank[py]:
        rank[px] += 1
    par[py] = px


qr = set()
for _ in range(m):
    a, b = map(int, input().split())
    if a > b:
        a, b = b, a
        qr.add((a, b))
for v in qr:
    union(v[0], v[1])

parc = Counter(par)
print(parc.most_common(1)[0][1])

Submission status: Wrong Answer

Solution code:
from collections import Counter, deque

n, m = map(int, input().split())
par = list(range(n + 1))
rank = [0] * (n + 1)


def find(x):
    q = deque()
    q.append(x)
    while len(q) > 0:
        v = q.pop()
        if v == par[v]:
            return v
        q.append(par[v])


def union(x, y):
    px, py = find(x), find(y)
    if px == py:
        return
    if rank[px] < rank[py]:
        par[px] = py
        return
    elif rank[px] == rank[py]:
        rank[px] += 1
    par[py] = px


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


parc = Counter(par)
print(parc.most_common(1)[0][1])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
ins = lambda: input().rstrip()
ini = lambda: int(input().rstrip())
inm = lambda: map(int, input().split())
inl = lambda: list(map(int, input().split()))
out = lambda x: print('\n'.join(map(str, x)))

def dfs(x):
    stack = [x]
    visited = []
    if checked[x] == 1:
        return 0
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.append(node)
            checked[node] = 1
            for i in graph[node]:
                stack.append(i)
                checked[i] = 1
    return len(visited)

n, m = inm()
checked = [0] * (n+1)
graph = {}
for i in range(m):
    a, b = inm()
    if a not in graph:
        graph[a] = []
    if b not in graph:
        graph[b] = []
    graph[a].append(b)
    graph[b].append(a)
ans = 0
for i in graph:
    ans = max(ans, dfs(i))
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
eg = [set() for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    eg[a].add(b)
    eg[b].add(a)

ans = 0
for v in eg:
    ans = max(ans, len(v) + 1)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
ins = lambda: input().rstrip()
ini = lambda: int(input().rstrip())
inm = lambda: map(int, input().split())
inl = lambda: list(map(int, input().split()))
out = lambda x: print('\n'.join(map(str, x)))

def dfs(x):
    stack = [x]
    visited = []
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.append(node)
            stack += graph[node]
    return len(visited)

n, m = inm()
graph = {}
for i in range(m):
    a, b = inm()
    if a not in graph:
        graph[a] = []
    if b not in graph:
        graph[b] = []
    graph[a].append(b)
    graph[b].append(a)
ans = 0
for i in graph:
    ans = max(ans, dfs(i))
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = list(map(int, input().split()))
am = []
bm = []
for _ in range(m):
    a, b = list(map(int, input().split()))
    ab_min = min([a, b])
    ab_max = max([a, b])
    am.append(ab_min)
    bm.append(ab_max)
am.sort()
bm.sort()

groups = []
for ai, bi in zip(am, bm):
    ag = None
    bg = None
    for g, group in enumerate(groups):
        if ai in group:
            ag = g
        if bi in group:
            bg = g
    if ag is None:
        if bg is None:
            groups.append({ai, bi})
        else:
            groups[bg].add(ai)
    else:
        if bg is None:
            groups[ag].add(bi)
        else:
            if ag != bg:
                groups[ag] = groups[ag].union(groups[bg])
                del groups[bg]

# max_gr_len = 1
# for group in groups:
#     if max_gr_len < len(group):
#         max_gr_len = len(group)
max_gr_len = max([len(group) for group in groups] + [1])

print(max_gr_len)

Submission status: Wrong Answer

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

par = [i + 1 for i in range(n)]
rank = [1] * n
size = [1] * n

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

def union(x, y):
    x = find(x)
    y = find(y)
    if rank[x - 1] < rank[y - 1]:
        par[x - 1] = y
        size[y - 1] += size[x - 1]
    else:
        par[y - 1] = x
        size[x - 1] += size[y - 1]
        if rank[x - 1] == rank[y - 1]:
            rank[x - 1] += 1

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

print(max(size))

Submission status: Wrong Answer

Solution code:
info_str = input()

human_num, info_num = info_str.split()

rel_list = []

for i in range(int(info_num)):
    rel_list.append(input().split())

friends_group = []

for x, y in rel_list:
    found = False
    for group in friends_group:
        found = False
        if y in group:
            group.add(x)
            group.add(y)
            found = True
            break
    if not found:
        friends_group.append(set([x, y]))

max_member_num = 0

for group in friends_group:
    member_num = len(group)
    if max_member_num < member_num:
        max_member_num = member_num




print(max_member_num)

Submission status: Wrong Answer

Solution code:
from collections import deque

n, m = list(map(int, input().split()))
edges = [list(map(int, input().split())) for _ in range(m)]

neighbor = [[] for _ in range(n)]
for edge in edges:
    neighbor[edge[0] - 1].append(edge[1] - 1)  # 1- → 0-index
    neighbor[edge[1] - 1].append(edge[0] - 1)

print(neighbor)
visited = [-1] * n
ans = 1
for idx in range(n):
    if visited[idx] == -1:
        queue = deque()
        queue.append(idx)
        group_population = 1
        visited[idx] = 0
        while len(queue) > 0:
            vertex = queue.popleft()
            for nei in neighbor[vertex]:
                if visited[nei] == -1:
                    visited[nei] = 0
                    queue.append(nei)
                    group_population += 1

    ans = max(ans, group_population)

print(ans)

Submission status: Wrong Answer

Solution code:
#Union-Find木の実装
from collections import Counter
N,M=map(int,input().split())

#初期化
par=[i for i in range(N)]#親の要素(par[x]=xのときxは木の根)
rank=[0]*N#木の深さ

#木の根を求める
def find(x):
  if par[x] == x:
    return x
  else:
    par[x] = find(par[x])
    return par[x]

#xとyの属する集合を併合
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

#xとyが同じ集合に属するか否か
def same(x,y):
  return find(x)==find(y)

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

c=Counter(par)
c=c.most_common()[0][1]
print(c)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
friends = {i: set([]) for i in range(N)}
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    friends[a].add(a)
    friends[a].add(b)
    friends[b].add(a)
    friends[b].add(b)
# print(friends)
from collections import deque

reached = [-1] * N
ans = 1
for i in range(N):
    if reached[i] == -1:
        queue = deque()
        queue.append(i)
        t = 1
        reached[i] = 0
        while queue:
            v = queue.popleft()
            for n in friends.get(i):
                if reached[n] == -1:
                    reached[n] = 0
                    queue.append(n)
                    t += 1
    ans = max(ans, t)
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
friends = {i: 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)
#print(friends)
from collections import deque
reached = [-1] * N
ans = 1
for i in range(N):
    if reached[i] == -1:
        queue = deque()
        queue.append(i)
        t = 1
        reached[i] = 0
        while queue:
            v = queue.popleft()
            for n in friends.get(i):
                if reached[n] == -1:
                    reached[n] = 0
                    queue.append(n)
                    t += 1
    ans = max(ans,t)
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import collections
import fractions
import itertools
import functools
import operator
import bisect

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[a] != done[b]:
                    group[done[a]] += group[done[b]]
                    group[done[b]] = [0]
        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 = [1]+[len(i) for i in group]
    print(max(people))
    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
def uf_find(x):
  while x != p[x]:
    x = p[x]
    print(x)
  return(x)

def uf_unite(x,y):
  x = uf_find(x)
  y = uf_find(y)
  if x == y:
    pass
  else:
    p[x] = y

N, M = map(int, input().split())
p = list(range(N))

for i in range(M):
  A, B = [int(i)-1 for i in input().split()]
  uf_unite(A,B)
  #print(p)

for i in range(N):
  p[i] = uf_find(i)
print(p)

q = [0]*N
for i in range(N):
  q[i] = p.count(i)
  
print(max(q))

Submission status: Wrong Answer

Solution code:
def find(e):
  if parent[e] == e:
    return e
  return find(parent[e])
n, m = map(int,input().split())
l = []
parent = [i for i in range(n)]
for _ in range(m):
  p, q = map(int,input().split())
  p -= 1
  q -= 1
  x = find(p)
  y = find(q)
  if parent[x] > parent[y]:
      x, y = y, x
  parent[y] = x
mx = 0
for i in set(parent):
    mx = max(mx,parent.count(i))
print(mx)

Submission status: Wrong Answer

Solution code:
def uf_find(x):
  if p[x] == -1:
    return x
  else:
    for i in range(5):
      x = p[x]
      if x == -1:
        return x
    return x

def uf_unite(x,y):
  x = uf_find(x)
  y = uf_find(y)
  if x == y and x != -1:
    pass
  else:
    p[x] = y

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

for i in range(M):
  A, B = [int(i)-1 for i in input().split()]
  uf_unite(A,B)
  #print(p)

for i in range(N):
  p[i] = uf_find(i)
print(p)

q = [0]*N
for i in range(N):
  q[i] = p.count(i)
  
print(max(q))

Submission status: Wrong Answer

Solution code:
'''
Created on 2020/08/30

@author: harurun
'''
def main():
  import collections
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write

  N,M=map(int,pin().split())
  c=[0]*N
  i=1
  for _ in [0]*M:
    A,B=map(int,pin().split())
    if c[A-1]==0 and c[B-1]==0:
      c[A-1]=i
      c[B-1]=i
      i+=1
    elif c[A-1]!=0 and c[B-1]==0:
      c[B-1]=c[A-1]
    elif c[B-1]!=0 and c[A-1]==0:
      c[A-1]=c[B-1]
  d=collections.Counter(c)
  print(d.most_common()[0][1])
  return
main()

Submission status: Wrong Answer

Solution code:
def find(e):
  if parent[e] == e:
    return e
  return find(parent[e])
n, m = map(int,input().split())
l = []
parent = [i for i in range(n)]
for _ in range(m):
  p, q = map(int,input().split())
  p -= 1
  q -= 1
  x = find(p)
  y = find(q)
  if x > y:
      x, y = y, x
  parent[y] = x
mx = 0
for i in set(parent):
    mx = max(mx,parent.count(i))
print(mx)

Submission status: Wrong Answer

Solution code:
import math
import collections
import fractions
import itertools
import functools
import operator
import bisect

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

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
def find(e):
  if parent[e] == e:
    return e
  return find(parent[e])
n, m = map(int,input().split())
l = []
for _ in range(m):
  p, q = map(int,input().split())
  p -= 1
  q -= 1
  l.append((p,q))
parent = [i for i in range(n)]
for i,j in l:
  x = find(i)
  y = find(j)
  if x > y:
      x, y = y, x
  parent[y] = x
mx = 0
for i in set(parent):
    mx = max(mx,parent.count(i))
print(mx)

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import deque
from collections import defaultdict as dd
import collections as col
import sys
sys.setrecursionlimit(10**8)

def DFS():
    temp=q.pop()

    for i in range(len(d[temp])):
        if chk[d[temp][i]-1]==0:
            chk[d[temp][i]-1]=1
            q.append(d[temp][i])
        else:break

        if d[temp][i] not in d[temp]:
            d[temp].append(d[temp][i])

    if len(q)>0:
        DFS()
    else:
        f=0
        for i in range(N):
            if chk[i]==0:
                f=1
                chk[i]=1
                q.append(i+1)
                break

        if f==0:
            ans()
        else:
            DFS()
    return

def ans():
    ans=0
    for i in d:
        if len(d[i])>0:
            ans=max(ans,len(col.Counter(d[i]))+1)
    print(ans)
    exit(0)

    return


q=[]
d=dd(list)
N,M=map(int, input().split())
chk=np.zeros(N,dtype=np.int)

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

q.append(1)
chk[0]=1

DFS()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd
from collections import deque
import collections as col
d=dd(list)
q=deque([])

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

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

ans=0
for i in  range(N):
    if len(d[i])>0:
        ans=max(ans,len(col.Counter(d[i]))+1)
print(ans)

Submission status: Wrong Answer

Solution code:
def uf_find(x):
  if p[x] == -1:
    return x
  else:
    i = 0
    while p[x] != -1:
      x = p[x]
      i+=1
      if i == 5:
        break
    return x

def uf_unite(x,y):
  x = uf_find(x)
  y = uf_find(y)
  if x == y and x != -1:
    pass
  else:
    p[x] = y

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

for i in range(M):
  A, B = [int(i)-1 for i in input().split()]
  uf_unite(A,B)
  #print(p)

for i in range(N):
  p[i] = uf_find(i)
#print(p)

q = [0]*N
for i in range(N):
  q[i] = p.count(i)
  
print(max(q))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd
from collections import deque
import collections as col
d=dd(list)
q=deque([])

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

ans=0
for i in  range(N):
    if len(d[i])>0:
        ans=max(ans,len(col.Counter(d[i]))+1)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd
from collections import deque
import collections as col
d=dd(list)
q=deque([])

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



print(d)
ans=0
for i in  range(N):
    if len(d[i])>0:
        ans=max(ans,len(col.Counter(d[i]))+1)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

class UnionFindBasic():
    """via https://note.nkmk.me/python-union-find/#_3
    """
    def __init__(self, n):
        self.parents = list(range(n))

    def find(self, x: int) -> int:
        if self.parents[x] == x: return x
        return self.find(self.parents[x])

    def union(self, x: int, y: int):
        x = self.find(x)
        y = self.find(y)
        if x == y: return
        if x > y: x,y = y,x
        self.parents[y] = x

def main():
    N, M = map(int, input().split())

    if M == 0:
        print(1)
        return

    uf = UnionFindBasic(N)

    for _ in range(M):
        a,b = list(map(lambda x: int(x)-1, input().split()))
        uf.union(a,b)

    print(Counter(uf.parents).most_common()[0][1])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

checked = []

for a, b in zip(A, B):
    first = min(a, b)
    second = max(a, b)
    checked.append((first, second))

visited = [0]*N
for c, d in set(checked):
    visited[c] += 1

max_ = max(visited)
print(int(min(N, max_ + max_*(max_-1)/2)))