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:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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


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

uf = UnionFind(N)
check = set()

for i in range(M):
    a, b = map(int, input().split())
    uf.union(a-1, b-1)
    check.add(a-1)

all_group_members = uf.all_group_members()
ans = 0
for i in check:
    ans = max(ans, uf.size(i))

print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
fri_dic = {}
for _ in range(m):
  a, b = map(int, input().split())
  if a not in fri_dic:
    fri_dic[a] = set()
  if b not in fri_dic[a]:
    fri_dic[a].add(b)
  if b not in fri_dic:
    fri_dic[b] = set()
  if a not in fri_dic[b]:
    fri_dic[b].add(a)
fri_set = set([1])
count = 0
for i in range(1, n + 1):
  if i not in fri_set:
    continue
  count += 1
  queue = [i]
  visited = set()
  while queue:
    p = queue.pop(0)
    if p not in fri_dic or p in visited:
      continue
    for j in fri_dic[p]:
      fri_set.add(j)
      visited.add(j)
      queue.append(j)
print(count)

Submission status: Wrong Answer

Solution code:
N,M=map(int, input().split())
d=dict()
for _ in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    if d.get(a):
        d[a].add(b)
    else:
        d[a]={b,}
    if d.get(b):
        d[b].add(a)
    else:
        d[b]={a,}
l=[True for _ in range(N)]
ans=-1
for i in range(N):
    if l[i]:
        l[i]=False
        if d.get(i):
            s=set(d[i])
            for x in d[i]:
                l[x]=False
                s=s|d[x]
            ans=max(ans,len(s))
if ans==-1:
    print(1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N,M = map(int,input().split())
fr = [[0]*2 for _ in range(M)]
for i in range(M):
    fr[i][:] = list(map(int,input().split()))
    fr[i][0] -= 1
    fr[i][1] -= 1

already = [False]*N
d = defaultdict(int)
group = [-1]*N
cnt = 0

for i in range(M):
    a,b = map(int,fr[i])
    if already[a] == False and already[b] == False:
        d[cnt] += 2
        group[a] = cnt
        group[b] = cnt
        cnt += 1
        already[a] = True
        already[b] = True
    elif (already[a] == True and already[b] == False):
        d[group[a]] += 1
        group[b] = group[a]
        already[b] = True
    elif (already[b] == True and already[a] == False):
        d[group[b]] += 1
        group[a] = group[b]
        already[a] = True

MAX = 0
for k in d.keys():
    MAX = max(MAX,d[k])
print(MAX)

Submission status: Wrong Answer

Solution code:
n,m=map(int, input().split())
l=[0]*(n+1)
c=set()
for i in range(m):
  a,b=map(int, input().split())
  a,b=min(a,b),max(a,b)
  d={(a,b)}
  if not d <= c:
    c.add((a,b))
    l[a]+=1
    l[b]+=1

ans=-1
for i in range(1,n+1):
  ans=max(ans, l[i])
  
print(ans+1)

Submission status: Wrong Answer

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

S = [set([i]) for i in range(N)]

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

res = 0
tmp = set()
for s in S:
    res = max(res, len(s))

print(res)

Submission status: Wrong Answer

Solution code:
import collections

n,m=map(int,input().split())
grouplist=[i for i in range(n)]
for i in range(m):
    f=list(map(int,input().split()))
    f[0]-=1
    f[1]-=1
    grouplist[max(f)]=grouplist[min(f)]
grouplist.sort()
ans=1
tmp=1
for i in range(1,n):
    if grouplist[i-1]!=grouplist[i]:
        ans=max(ans,tmp)
        tmp=1
    else:
        tmp+=1
print(max(ans,tmp))

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_)

l = [[]*N for _ in range(N)]
for i in range(M):
    if A[i] < B[i]:
        l[A[i]-1].append(B[i]-1)

ans = 1
for i in range(N):
    if len(l[i]) != 0:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
Friend = list(range(N))
for i in range(M):
    A, B = map(int, input().split())
    a = A-1
    b = B-1
    if(B < A):
        a = B-1
        b = A-1
    Friend[b] = Friend[a]
sF = sorted(Friend)
now = 0
count = 0
cmax = 0
for j in sF:
    if(j == now):
        count += 1
    else:
        now = j
        if(count > cmax):
            cmax = count
        count = 0
if(count > cmax):
    cmax = count
print(cmax)

Submission status: Wrong Answer

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

n, m = map(int, input().split())
uf = UnionFind(n)
ans = 0
for i in range(m):
    a, b = map(int, input().split())
    uf.union(a-1, b-1)
    ans = max(ans, uf.size(a-1))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

x = 0
color = {}
group = defaultdict(set)

for i in range(m):
    a, b = map(int, input().split())
    if a in color and b in color:
        ca = color[a]
        cb = color[b]
        if ca == cb:
            continue

        group[ca] |= group[cb]
        for p in group[cb]:
            color[p] = ca
        del group[cb]
    elif a not in color and b not in color:
        color[a] = x
        group[x].add(a)
        color[b] = x
        group[x].add(b)
        x += 1
    elif a in color and b not in color:
        color[b] = color[a]
        group[color[a]].add(b)
    elif a not in color and b in color:
        color[a] = color[b]
        group[color[b]].add(a)
ans = 0
for g, ms in group.items():
    ans = max(ans, len(ms))
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

print(temp)

Submission status: Wrong Answer

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

friend = [set() for _ in range(N)]

for _ in range(M):
    A, B = map(int, input().split())
    friend[A-1].add(B-1)
    friend[B-1].add(A-1)

for i in range(N):
    tmp = len(friend[i])
    for j in range(tmp):
        for k in range(j, tmp):
            friend[j].add(k)
            friend[k].add(j)

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

Submission status: Wrong Answer

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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


N,M = map(int, input().split())
uf = UnionFind(N)
for i in range(M):
    N,M = map(int, input().split())
    uf.union(N-1,M-1)
ans = 0
for i in range(N):
    ans = max(ans,uf.size(i))

print(ans)

Submission status: Wrong Answer

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

S = [set([i]) for i in range(N)]

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

res = 0
tmp = set()
for s in S:
    # s_frozen = frozenset(s)
    # tmp.add()
    res = max(res, len(s))

print(res)

Submission status: Wrong Answer

Solution code:
from collections import deque
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

li = []
seen = [False]*n
for i in range(n):
    if seen[i]:
        continue
    q = deque([i])
    seen[i] = True
    cnt = 1
    while q:
        node = q.popleft()
        for i in graph[node]:
            if seen[i]:
                continue
            seen[i] = True
            cnt += 1
    li.append(cnt)
print(max(li))

Submission status: Wrong Answer

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

members = [-1] * N

group_count = 0
groups = [0] * N
for m in range(M):
    A, B = map(int, input().split())
    A = A - 1
    B = B - 1
    if members[A]==-1 and members[B]==-1:
        members[A] = members[B] = group_count
        groups[group_count] = 2
        group_count += 1
    
    elif members[A]!=-1 and members[B]==-1:
        members[B] = members[A]
        groups[members[A]] += 1
    
    elif members[B]!=-1 and members[A]==-1:
        members[A] = members[B]
        groups[members[B]] += 1

print(max(groups))

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]:
                lB = lister[fMap[b]]
                lA = lister[fMap[a]]
                for e in lB:
                    lA.append(e)
                    fMap[e] = fMap[a]
        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 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)

st = deque([1])
check = [0]*(N+1)
check[1] = 1
mark = [0]*(N+1)
ans = 0
while st:
  cnt = 0
  s = st.popleft()
  for t in l[s]:
    if check[t] == 0:
      mark[t] = s
      check[t] = 1
      st.append(t)
      cnt += 1
  ans = max(ans,cnt)
print(ans+1)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
numbers=[set() for _ in range(N)]
for _ in range(M):
    a,b=map(int,input().split())
    A=sorted([a,b])
    numbers[A[0]-1].add(A[1]-1)
ans=1
suuji=0
for number in numbers:
    suuji=max(suuji,len(number))
print(ans+suuji)

Submission status: Wrong Answer

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

friend = [[]]*N

for i in range(M):
    A,B = list(map(int,input().split()))
    A -= 1
    B -= 1
    friend[A].append(B)
    friend[A] = friend[A]+friend[B]
    friend[B] = friend[A]
ans = 0  
for i in range(N):
    ans2 = len(set(friend[i]))
    ans = max([ans,ans2])
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0: return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y: return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
#======================================================#

def main():
    n, m = MII()
    group = [MIIZ() for _ in range(m)]
    uf = UnionFind(n)
    for a, b in group:
        uf.union(a, b)

    # g = uf.all_group_members().values()
    # maxv = max([len(gi) for gi in g])
    # print(maxv)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

node = [i for i in range(1, n+1)]
for _ in range(m):
   a, b = map(int, input().split())
   x = min(a, b)
   node[a-1] = min(node[a-1], x)
   node[b-1] = min(node[b-1], x)

cnt = Counter(node)
print(cnt.most_common()[0][1])

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.readline
import time
from heapq import heappush, heappop, heapify
import math
import itertools as it
from collections import deque 


def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
start_time = time.perf_counter()
# ------------------------------

N, M = inpl()
graph = [set() for i in range(N)]
for i in range(M):
    A, B = inpl()
    A, B = A - 1, B - 1 
    graph[A].add(B)
    graph[B].add(A)

ans = 0
for ls in graph:
    ans = max(ans, len(ls))
print(ans + 1)


# -----------------------------
end_time = time.perf_counter()
print('time:', end_time-start_time, file=sys.stderr)

Submission status: Wrong Answer

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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


N,M = map(int, input().split())
uf = UnionFind(N)
for i in range(M):
    N,M = map(int, input().split())
    uf.union(N-1,M-1)
ans = 1
for i in range(N):
    ans = max(ans,uf.size(i))

print(ans)

Submission status: Wrong Answer

Solution code:
#ここまでテンプレ
from sys import stdin
from sys import setrecursionlimit
setrecursionlimit(10 ** 7)

n,m = map(int,stdin.readline().rstrip().split())

#Union Find
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size = [1] * 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]
    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)
    # すべての頂点に対して親を検索する
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)

f = UnionFind(n)

for _ in range(m):
    a,b = map(int,stdin.readline().rstrip().split())
    a -= 1
    b -= 1
    f.union(a,b)

from itertools import groupby

li = f.par

li.sort()

lin = []
for key, value in groupby(li):
    lin.append(len(list(value)))

print(max(lin))

Submission status: Wrong Answer

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

ab = [[int(_)-1 for _ in input().split()]for i in range(m)]

for i in range(m):
    if ab[i][0] > ab[i][1]:
        ab[i][0], ab[i][1] = ab[i][1], ab[i][0]

ab.sort(key=lambda x: x[0])

t = [-1 for i in range(n)]
ans = [0 for i in range(n)]
for i in range(m):
    a, b = ab[i]
    if t[b] == -1:
        if t[a] == -1:
            t[b] = a
        else:
            t[b] = t[a]
        ans[t[b]] += 1

print(max(ans)+1)
# print(t)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
connect = []
for i in range(m):
    connect.append(sorted(list(map(int, input().split()))))
con = {}
for i in range(m):
    try:
        con[connect[i][0]].append(connect[i][1])
        con[connect[i][0]] = list(set(con[connect[i][0]]))
    except KeyError:
        con[connect[i][0]] = [connect[i][1]]
a = 0
if(con == {}):
    print(1)
else:
    for i in con:
        a = max(a, len(con[i])+1)
    print(a)

Submission status: Wrong Answer

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

def union(a,b):
	x=find(a)
	global con
	y=find(b)
	if x!=y:
		p[y]=p[x]=min(x,y);con-=1
		r[min(x,y)]+=r[max(x,y)];con=max(con,r[min(x,y)])
n,m=map(int,input().split())
p=[i for i in range(n+1)]
con=1
r=[1]*(n+1)
for i in range(m):
  u,v=map(int,input().split())
  union(u,v)
print(con)

Submission status: Wrong Answer

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

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

ret = 0
for k, v in d.items():
    ret = max(len(v)+1, ret)
print(ret)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N, M = map(int, input().split())
friends = defaultdict(set)

for _ in range(M):
    a, b = map(lambda x: int(x)-1, input().split())
    friends[a].add(b)
    friends[b].add(a)
ans = 0
for k, v in friends.items():
    ans = max(ans, len(v)+1)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

N, M = MAP()
nodes = [set() for i in range(N)]
for i in range(M):
    a, b = MAP()
    a -= 1; b -= 1
    nodes[a].add(b)
    nodes[b].add(a)

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

Submission status: Wrong Answer

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

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

n,m = mp()
cnt = [0]*(n+1)
used = set()
for i in range(m):
    a,b = mp()
    if (a,b) not in used:
        cnt[a] += 1
        cnt[b] += 1
        used.add((a,b))
        used.add((b,a))
print(max(cnt)+1)

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]
c = 0
for i in range(n):
  c = max(c, groups.count(i))
print(c)

Submission status: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit
input = stdin.buffer.readline
setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi, radians, sin, cos

MOD = 10 ** 9 + 7
INF = 10 ** 18

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]

root = [i for i in range(N + 1)]
size = [1] * (N + 1)
 
def find(x):
  y = root[x]
  if x == y:
    return x
  else:
    z = find(y)
    root[x] = z
    return z

def union(x, y):
  rx = find(x)
  ry = find(y)
  sx = size[rx]
  sy = size[ry]
  if rx == ry:
    return 0
  else:
    if sx >= sy:
      root[ry] = rx
      size[rx] = sx + sy
    else:
      root[rx] = ry
      size[ry] = sx + sy
    return sx * sy

cnt = [0] * (N + 1)

for a, b in AB:
    union(a, b)
for r in root[1:]:
    cnt[r] += 1

if max(cnt):
    print(max(cnt))
else:
    print(1)

Submission status: Wrong Answer

Solution code:
n,q=map(int,input().split())
d={}
for i in range(q):
    j,k=map(int,input().split())
    j,k=min(j,k),max(j,k)
    if j in d:
        d[j][k]=1
    else:
        flag=False
        for g in d:
            if j in d[g]:
                d[g][k]=1
                flag=True
        if not flag:
            d[j]={k:1}
ans=0
for i in d:
    ans=max(ans,1+len(d[i]))
print(ans)

Submission status: Wrong Answer

Solution code:
def resolve():
    from collections import defaultdict, deque
    N, M = [int(i) for i in input().split()]
    AABB = [[int(i) - 1 for i in input().split()] for _ in range(M)]
    dic = defaultdict(deque)
    for a, b in AABB:
        dic[a].append(b)
        dic[b].append(a)
    groups = [[] for _ in range(N)]
    cnt = 0
    for i in range(N):
        for j in range(N):
            if i not in groups[j] and all(a not in groups[j] for a in dic[i]):
                if len(groups[j]) == 0:
                    cnt += 1
                groups[j].extend(dic[i])
                break
    print(cnt)

resolve()

Submission status: Wrong Answer

Solution code:
import collections as cc
I=lambda:list(map(int,input().split()))
mod=10**9+7
n,m=I()
g=[set() for i in range(n+1)]
ds=[i for i in range(n+1)]
def find(a):
    while ds[a]!=a:
        a=ds[a]
    return a
def join(a,b):
    x=find(a)
    y=find(b)
    if x!=y:
        ds[x]=ds[y]=min(x,y)
for i in range(m):
    x,y=I()
    g[x].add(y)
    g[y].add(x)
    join(x,y)
temp=cc.Counter(ds[1:])
print(max(temp.values()))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, Counter
from itertools import product, permutations, combinations, accumulate
from bisect import bisect_left, bisect
from heapq import heappop, heappush
from fractions import gcd
from math import ceil, floor


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


def input_int():
    return int(input())


N, M = input_list()
d = {}
for _ in range(M):
    a, b = input_list()
    if a in d:
        d[a].add(b)
    else:
        d[a] = set([b])
    if b in d:
        d[b].add(a)
    else:
        d[b] = set([a])
ans = 0
for k in d:
    ans = max(ans, len(d[k]))
print(ans + 1)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys

sys.setrecursionlimit(20000)


def _ia(): return map(int, sys.stdin.readline().strip().split())


class UnionFind:
    def __init__(self, n: int) -> None:
        self._par = [i for i in range(n)]
        self._rank = [0] * n

    def root(self, n: int) -> int:
        return self._par[n]

    def same(self, n: int, m: int) -> bool:
        return self.root(n) == self.root(m)

    def unite(self, n: int, m: int) -> None:
        pn = self.root(n)
        pm = self.root(m)
        if pn == pm:
            return
        self._par[pm] = pn


def main():
    n, m = _ia()
    uf = UnionFind(n)
    for _ in range(m):
        a, b = map(lambda x: x-1, _ia())
        uf.unite(a, b)
    c = Counter([uf.root(i) for i in range(n)])
    return max(c.values())


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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
##https://tjkendev.github.io/procon-library/python/union_find/union_find.html
from collections import Counter
N = 2*10**5

*p, = range(N)
rank = [1]*N
def root(x):
    if x == p[x]:
        return x
    p[x] = y = root(p[x])
    return y
def unite(x, y):
    px = root(x); py = root(y)
    if px == py:
        return 0
    rx = rank[px]; ry = rank[py]
    if ry < rx:
        p[py] = px
    elif rx < ry:
        p[px] = py
    else:
        p[py] = px
        rank[px] += 1
    return 1

def main():

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

    for _ in range(M):
        a,b = map(int,input().split())
        a,b = a-1,b-1
        unite(a,b)
    
    tmp = Counter(p[:n])
    print(max(tmp.values()))
    


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

direction = [-1]+[False]*n
d = defaultdict(list)

for i in range(m):
    a,b = map(int,input().split())
    if direction[a] == False and direction[b] == False:
        direction[a] = a
        direction[b] = a
        d[a] += [a,b]
    elif direction[a] == False:
        direction[a] = direction[b]
        d[direction[b]].append(a)
    elif direction[b] == False:
        direction[b] = direction[a]
        d[direction[a]].append(b)
maxi = 0
for alist in d.values():
    maxi = max(maxi,len(alist))
print(maxi)

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

group = []
for i in range(m):
    a,b = friend_list[i]

    new_group = set()
    if group == []:
        new_group.add(a)
        new_group.add(b)

    for g in range(len(group)):
        if a in group[g] or b in group[g]:
            group[g].add(a)
            group[g].add(b)
        else:
            new_group.add(a)
            new_group.add(b)
    if new_group != set():
        group.append(new_group)

max_group = -1
for g in group:
    max_group = max(len(g),max_group)

print(max_group)