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())
lis = []
ans = 0
for _ in range(m):
  a, b = map(int, input().split())
  if len(lis) > 0:
    c = 0
    for i in range(len(lis)):
      if a in lis[i] or b in lis[i]:
        lis[i].append(a)
        lis[i].append(b)
        c += 1
        break
    if c == 0:
      lis.append([a, b])
  else:
    lis.append([a, b])

for x in lis:
  ans = max(ans, len(set(x)))
            
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

n, m = map(int, input().split())
if m == 0:
  print("0")
else:
  ab = [map(int, input().split()) for _ in range(m)]
  a, b = [list(i) for i in zip(*ab)]

  a.extend(b)
  c = Counter(a)
  most = c.most_common(1)[0][0]

  temp = []
  for i in range(m):
    if a[i] == most or b[i] == most:
      if a[i] == b[i]:
        continue
      temp.append(a[i])
      temp.append(b[i])
  temp = list(set(temp))
  print(len(temp))

Submission status: Wrong Answer

Solution code:
import collections

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

A = []
B = []
for _ in range(m):
    a, b = map(int, input().split())
    x = min(a, b)
    y = max(a, b)
    A.append(x)
    B.append(y)

if m == 0:
    print(1)
else:
    C = zip(A, B)
    C = sorted(C)
    A, B = zip(*C)
    groups = [0] * n
    index = 1
    for i, j in zip(A, B):
        i -= 1
        j -= 1
        if groups[i] == 0 and groups[j] == 0:
            groups[i] = groups[j] = index
            index += 1
        elif groups[i] == 0 and groups[j] != 0:
            groups[i] = groups[j]
        elif groups[j] == 0 and groups[i] != 0:
            groups[j] = groups[i]
    g = collections.Counter(groups)
    zero_ = g[0]
    max_ = 0
    for i, j in zip(g.keys(), g.values()):
        if i != 0:
            max_ = max(max_, j)
    print(max_)

Submission status: Wrong Answer

Solution code:
import collections

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

A = []
B = []
for _ in range(m):
    a, b = map(int, input().split())
    x = min(a, b)
    y = max(a, b)
    A.append(x)
    B.append(y)

if m == 0:
    print(1)
else:
    C = zip(A, B)
    C = sorted(C)
    A, B = zip(*C)
    groups = [0] * n
    index = 1
    for i, j in zip(A, B):
        i -= 1
        j -= 1
        if groups[i] == 0 and groups[j] == 0:
            groups[i] = groups[j] = index
            index += 1
        elif groups[i] == 0 and groups[j] != 0:
            groups[i] = groups[j]
        elif groups[j] == 0 and groups[i] != 0:
            groups[j] = groups[i]
    g = collections.Counter(groups)
    zero_ = g[0]
    max_ = 0
    for i, j in zip(g.keys(), g.values()):
        if i != 0:
            max_ = max(max_, j)
    print(max(zero_, max_))

Submission status: Wrong Answer

Solution code:
N, M = (int(d) for d in input().split())

C = [set() for i in range(N+1)]
for i in range(M):
    A, B = (int(d) for d in input().split())
    C[A].update([B])
    C[B].update([A])

# BFS
seen = set()
G = []

for i in range(1, N+1):
    if i in seen:
        continue

    # create new group
    G.append(set())
    G[-1].update([i])

    # create queue
    Q = list(C[i])
    G[-1].update(C[i])
    seen.update(C[i])

    while len(Q) > 0:
        # queue is not empty

        I = Q.pop(0)

        if I in seen:
            continue
        
        J = C[I].difference(seen)
        Q += list(J)
        G[-1].update(J)

        seen.update(J)


print(max([len(g) for g in G]))

Submission status: Wrong Answer

Solution code:
import networkx as nx
import sys

G = nx.Graph()

n, m = map(int, input().split())
if m == 0:
    print(1)
    sys.exit()
for i in range(m):
    a, b = map(int, input().split())
    G.add_edge(a, b)

largest_cc = max(nx.connected_components(G), key=len)
print(largest_cc)
print(len(largest_cc))

Submission status: Wrong Answer

Solution code:

def main():
    n, m = map(int, input().split())
    fs = [set([i]) for i in range(n+1)]

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

    print(len(max(fs, key=lambda x: len(x))))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import collections

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
  par[x]=find(par[x])
  return par[x]

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

for i in range(m):
  a,b=map(int,input().split())
  union(a,b)
c=collections.Counter(par)
li=sorted(c.values(),reverse=True)
print(li[0])

Submission status: Wrong Answer

Solution code:
import collections

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
  par[x]=find(par[x])
  return par[x]

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

for i in range(m):
  a,b=map(int,input().split())
  union(a,b)
dic=collections.Counter(par)
li=sorted(dic.values(),reverse=True)
print(li[0])

Submission status: Wrong Answer

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

class UnionFindPathCompression():
    def __init__(self, n):
        self.parents = list(range(n))
        self.rank = [1]*n
        self.size = [1]*n
        

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

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

        if px == py:
            return
        else:
            if self.rank[px] < self.rank[py]:
                self.parents[px] = py
                self.size[py] += self.size[px]
            else:
                self.parents[py] = px
                self.size[px] += self.size[py]
                #ランクの更新
                if self.rank[px] == self.rank[py]:
                    self.rank[px] += 1


n,m = map(int,input().split())
ufpc = UnionFindPathCompression(n)
for _ in range(m):
    a,b = map(int,input().split())
    a,b=a-1,b-1
    ufpc.union(a,b)
counter = {}
for v in ufpc.parents:
    if v in counter:
        counter[v] += 1
    else:
        counter[v] = 1

for i in range(n):
    ufpc.find(i)

ans = 0
for key,val in counter.items():
    ans = max(ans, val)
print(ans)

Submission status: Wrong Answer

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

class UnionFindPathCompression():
    def __init__(self, n):
        self.parents = list(range(n))
        self.rank = [1]*n
        self.size = [1]*n
        

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

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

        if px == py:
            return
        else:
            if self.rank[px] < self.rank[py]:
                self.parents[px] = py
                self.size[py] += self.size[px]
            else:
                self.parents[py] = px
                self.size[px] += self.size[py]
                #ランクの更新
                if self.rank[px] == self.rank[py]:
                    self.rank[px] += 1


n,m = map(int,input().split())
ufpc = UnionFindPathCompression(n)
for _ in range(m):
    a,b = map(int,input().split())
    a,b=a-1,b-1
    ufpc.union(a,b)
counter = {}
for v in ufpc.parents:
    if v in counter:
        counter[v] += 1
    else:
        counter[v] = 1

ans = 0
for key,val in counter.items():
    ans = max(ans, val)
print(ans)

Submission status: Wrong Answer

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

ans = [i for i in range(1,n+1,1)]
#now = [1]*n
now_num = 1
link = [[] * 1 for i in range(n)]

for i in ab:
    if i[1] not in link[i[0]-1]:
        link[i[0]-1].append(i[1])
    if i[0] not in link[i[1]-1]:
        link[i[1]-1].append(i[0])
    a = max(len(link[i[0]-1]),len(link[i[1]-1]))
    if now_num < a:
        now_num = a
    
print(now_num+1)

Submission status: Wrong Answer

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

ans = [i for i in range(1,n+1,1)]
#now = [1]*n
now_num = 1
link = [[] * 1 for i in range(n)]

for i in ab:
    if i[1] in link[i[0]-1]:
        link[i[0]-1].append(i[1])
    if i[0] in link[i[1]-1]:
        link[i[1]-1].append(i[0])
    a = max(len(link[i[0]-1]),len(link[i[1]-1]))
    if now_num < a:
        now_num = a
    
print(now_num+1)

Submission status: Wrong Answer

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

ans = [i for i in range(1,n+1,1)]
#now = [1]*n
now_num = 1
link = [[] * 1 for i in range(n)]

for i in ab:
    link[i[0]-1].append(i[1])
    link[i[1]-1].append(i[0])
    a = max(len(link[i[0]-1]),len(link[i[1]-1]))
    if now_num < a:
        now_num = a
    
        
print(now_num+1)

Submission status: Wrong Answer

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

used = [-1]*N
for i in range(N):
    if used[i] >= 0:
        continue
    q = deque()
    q.append(i)
    while q:
        temp = q.popleft()
        for e in E[temp]:
            if used[e] == i:
                continue
            used[e] = i
            q.append(e)

ans = [0]*N
for c in used:
    ans[c] += 1
print(max(ans))

Submission status: Wrong Answer

Solution code:
import collections

n, m = map(int, input().split())
f=[0]*(n+1)
s = 1
aa = [0]
for i in range(m):
    a, b = map(int, input().split())
    if f[a] == 0 and f[b] == 0:
        f[a] = f[b] = s
        aa.append(2)
        s+=1
    elif f[a]*f[b] == 0:
        f[a] = f[b] = f[a]+f[b]
        aa[f[a]] += 1
print(max(aa))

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)
maxn = 0
for i in range(m):
    a, b = map(int, input().split())
    uf.union(a-1,b-1)
    maxn = max(maxn, uf.size(a-1))
    maxn = max(maxn, uf.size(b-1))
print(maxn)

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)
maxn = 0
for i in range(m):
    a, b = map(int, input().split())
    uf.union(a-1,b-1)
    maxn = max(maxn, uf.size(a-1))
    maxn = max(maxn, b-1)
print(maxn)

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)
maxn = 0
for i in range(m):
    a, b = map(int, input().split())
    uf.union(a-1,b-1)
    maxn = max(maxn, uf.size(a-1))
print(maxn)

Submission status: Wrong Answer

Solution code:
n, m = list(map(int, input().split()))
relations = {}
for _ in range(m):
  a, b = list(map(int, input().split()))
  a -= 1
  b -= 1
  if relations.get(a):
     relations[a].append(b)
  else:
    relations[a] = [b]
  if relations.get(b):
    relations[b].append(a)
  else: 
    relations[b] = [a]

from collections import deque
visited = [False for i in range(n)]

groups = 0
def bfs(n, visited):
  global groups
  queue = deque([n])
  group_len = 0
  while queue:
    current = queue.popleft()
    if not visited[current]:
      visited[current] = True
      if relations.get(current):
        for neighbor in relations[current]:
          queue.append(neighbor)
        group_len += 1

  groups = max(groups, group_len)
    

for i in range(n):
  if not visited[i]:
    bfs(i, visited)

print(groups)

Submission status: Wrong Answer

Solution code:
from __future__ import print_function

from functools import reduce
from operator import mul
from collections import Counter
from collections import deque
from itertools import accumulate
from queue import Queue
from queue import PriorityQueue as pq
from heapq import heapreplace
from heapq import heapify
from heapq import heappushpop
from heapq import heappop
from heapq import heappush
import heapq
import time
import random
import bisect
import itertools
import collections
from fractions import Fraction
import fractions
import string
import math
import operator
import functools
import copy
import array
import re
import sys
sys.setrecursionlimit(500000)


input = sys.stdin.readline


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return

# from fractions import gcd
# from math import gcd

# def lcm(n, m):
#     return int(n * m / gcd(n, m))


# def coprimize(p, q):
#     common = gcd(p, q)
#     return (p // common, q // common)


# def find_gcd(list_l):
#     x = reduce(gcd, list_l)
#     return x


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


mod = 1000000007


def combinations_count_mod(n, r):
    r = min(r, n - r)
    numer = reduce(lambda x, y: x * y % mod, range(n, n - r, -1), 1)
    denom = pow(reduce(lambda x, y: x * y % mod, range(1, r + 1), 1), mod - 2, mod)
    return numer * denom % mod


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 solve():
    pass


def main():
    n, m = map(int, input().strip().split())

    uf = UnionFind(n)

    ans = 0
    if m==0:
        print(n)
        return
        
    for i in range(m):
        a, b = map(lambda x: int(x)-1, input().strip().split())
        if a > b:
            c = a
            a = b
            b = c
        uf.union(a,b)
        ans = max(ans,uf.size(a))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from __future__ import print_function

from functools import reduce
from operator import mul
from collections import Counter
from collections import deque
from itertools import accumulate
from queue import Queue
from queue import PriorityQueue as pq
from heapq import heapreplace
from heapq import heapify
from heapq import heappushpop
from heapq import heappop
from heapq import heappush
import heapq
import time
import random
import bisect
import itertools
import collections
from fractions import Fraction
import fractions
import string
import math
import operator
import functools
import copy
import array
import re
import sys
sys.setrecursionlimit(500000)


input = sys.stdin.readline


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return

# from fractions import gcd
# from math import gcd

# def lcm(n, m):
#     return int(n * m / gcd(n, m))


# def coprimize(p, q):
#     common = gcd(p, q)
#     return (p // common, q // common)


# def find_gcd(list_l):
#     x = reduce(gcd, list_l)
#     return x


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


mod = 1000000007


def combinations_count_mod(n, r):
    r = min(r, n - r)
    numer = reduce(lambda x, y: x * y % mod, range(n, n - r, -1), 1)
    denom = pow(reduce(lambda x, y: x * y % mod, range(1, r + 1), 1), mod - 2, mod)
    return numer * denom % mod


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 solve():
    pass


def main():
    n, m = map(int, input().strip().split())

    uf = UnionFind(n)

    ans = 0
    for i in range(m):
        a, b = map(lambda x: int(x)-1, input().strip().split())
        if a > b:
            c = a
            a = b
            b = c
        uf.union(a,b)
        ans = max(ans,uf.size(a))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import queue
N, M = map(int, input().split())
l = [[] for i in range(N)]
for i in range(M):
        a, b = map(int, input().split())
        l[a - 1].append(b - 1)
        l[b - 1].append(a - 1)
c = [0] * N 
ans = 0 
q = queue.Queue()
for j in range(N):
        q.put(l[j])
        u = 0 
        while not q.empty():
                temp = q.get()
                for k in temp:
                        if c[k]:
                                continue
                        c[k] = 1 
                        u += 1
                        q.put(l[k])
        ans = max(ans, u)
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
c=[[] for i in range(n+1)]
for _ in range(m):
    a,b=map(int,input().split())
    if a not in c[b] and b not in c[a]:
        c[a].append(b)
        c[b].append(a)
        for j in range(len(c[a])):
            if c[a][j] not in c[b]:
                c[b].append(c[a][j])
        for k in range(len(c[b])):
            if c[b][k] not in c[a]:
                c[a].append(c[b][k])
d=[]
for l in range(n+1):
    d.append(len(c[l]))
print(max(d))

Submission status: Wrong Answer

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

P=[[0,0]]
for i in range(1,N+1):
    P.append([i,i])

R=[]
for i in range(M):
    a,b=map(int,input().split())
    c=max(a,b)
    a=min(a,b)
    b=c
    R.append((a,b))

R=sorted(list(set(R)))

for i in range(len(R)):
    #親の番号
    x=0
    #子番号
    y=0
    #新たに増えるグループの人数
    cnt=0
    a=R[i][0]
    b=R[i][1]
    #親idの親idを抽出
    u=P[P[a][1]][1]
    v=P[P[b][1]][1]
    #親idの親idが変化した時のために親idを更新
    P[a][1]=u
    P[b][1]=v
    if u==v:#既に同グループに所属済み
        continue
    else:#別グループに属している場合
        x=min(u,v)
        y=max(u,v)
    
    #子idが乗っ取られるか確認
    if u!=x:
        P[u][1]=x
    if v!=x:
        P[v][1]=x
    
    P[a][1]=x
    P[b][1]=x

for i in range(1,N+1):
    if P[i][0]==P[i][1]:
        continue
    else:
        P[i][1]=P[P[i][1]][1]


for i in range(1,N+1):
    x=P[i][1]

S=[]
for i in range(1,N+1):
    S.append((P[i][1],P[i][0]))
S=sorted(S)

Q=[]
for i in range(1,N+1):
    if P[i][0]==P[i][1]:
        Q.append(P[i][1])

l=len(Q)
T=[[0] for i in range(l)]

last=S[0][0]
cnt=0
for i in range(N):
    if S[i][0]!=last:
        cnt+=1
        last=S[i][0]
    T[cnt].append(S[i][1])

for i in range(l):
    T[i].pop(0)

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

print(ans)

Submission status: Wrong Answer

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

P=[[0,0,0]]
for i in range(1,N+1):
    P.append([i,i,1])

R=[]
for i in range(M):
    a,b=map(int,input().split())
    c=max(a,b)
    a=min(a,b)
    b=c
    R.append((a,b))

R=sorted(list(set(R)))

for i in range(len(R)):
    #親の番号
    x=0
    #子番号
    y=0
    #新たに増えるグループの人数
    cnt=0
    a=R[i][0]
    b=R[i][1]
    #親idを抽出
    u=P[P[a][1]][1]
    v=P[P[b][1]][1]
    #親idが変化していれば子の親idも変化
    P[a][1]=u
    P[b][1]=v
    if P[a][1]==P[b][1]:#既に同グループに所属済み
        continue
    else:#別グループに属している場合
        x=min(P[a][1],P[b][1])
        y=max(P[a][1],P[b][1])
    
    #子idが乗っ取られるか確認
    if u!=x:
        P[u][1]=x
    if v!=x:
        P[v][1]=x

    cnt=P[y][2]
    P[a][1]=x
    P[b][1]=x
    P[x][2]+=cnt


ans=0
for i in range(1,N+1):
    x=P[i][1]
    P[i][2]=P[x][2]

for i in range(1,N+1):
    ans=max(ans,P[i][2])


print(ans)

Submission status: Wrong Answer

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

P=[[0,0,0]]
for i in range(1,N+1):
    P.append([i,i,1])

R=[]
for i in range(M):
    a,b=map(int,input().split())
    c=max(a,b)
    a=min(a,b)
    b=c
    R.append((a,b))

R=sorted(list(set(R)))

for i in range(len(R)):
    #親の番号
    x=0
    #子番号
    y=0
    #新たに増えるグループの人数
    cnt=0
    a=R[i][0]
    b=R[i][1]
    #親idを抽出
    u=P[P[a][1]][1]
    v=P[P[b][1]][1]
    #親idが変化していれば子の親idも変化
    P[a][1]=u
    P[b][1]=v
    if P[a][1]==P[b][1]:#既に同グループに所属済み
        continue
    else:#別グループに属している場合
        x=min(P[a][1],P[b][1])
        y=max(P[a][1],P[b][1])
    
    #子idが乗っ取られるか確認
    if u!=x:
        P[u][1]=x
    if v!=x:
        P[v][1]=x

    cnt=P[y][2]
    P[a][1]=x
    P[b][1]=x
    P[x][2]+=cnt


ans=0
for i in range(1,N+1):
    x=P[i][1]
    P[i][2]=P[x][2]

for i in range(1,N+1):
    ans=max(ans,P[i][2])

print(R)
print(P)
print(ans)

Submission status: Wrong Answer

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

P=[[0,0,0]]
for i in range(1,N+1):
    P.append([i,i,1])

R=[]
for i in range(M):
    a,b=map(int,input().split())
    c=max(a,b)
    a=min(a,b)
    b=c
    R.append((a,b))

R=sorted(list(set(R)))

for i in range(len(R)):
    #親の番号
    x=0
    #子番号
    y=0
    #新たに増えるグループの人数
    cnt=0
    a=R[i][0]
    b=R[i][1]
    #親idを抽出
    u=P[P[a][1]][1]
    v=P[P[b][1]][1]
    #親idが変化していれば子の親idも変化
    P[a][1]=u
    P[b][1]=v
    if P[a][1]==P[b][1]:#既に同グループに所属済み
        continue
    else:#別グループに属している場合
        x=min(P[a][1],P[b][1])
        y=max(P[a][1],P[b][1])
    
    #子idが乗っ取られるか確認
    if u!=x:
        P[u][1]=x
    if v!=x:
        P[v][1]=x

    cnt=P[y][2]
    P[a][1]=x
    P[b][1]=x
    P[x][2]+=cnt


ans=0
for i in range(N):
    x=P[i][1]
    P[i][2]=P[x][2]

for i in range(N):
    ans=max(ans,P[i][2])

print(ans)

Submission status: Wrong Answer

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

P=[[0,0,0]]
for i in range(1,N+1):
    P.append([i,0,1])

R=[]
for i in range(M):
    a,b=map(int,input().split())
    c=max(a,b)
    a=min(a,b)
    b=c
    R.append((a,b))

R=sorted(list(set(R)))

for i in range(len(R)):
    #親の番号
    x=0
    #子番号
    y=0
    #新たに増えるグループの人数
    cnt=0
    a=R[i][0]
    b=R[i][1]
    if P[a][1]==0 and P[b][1]==0:
       x=min(a,b)
       y=max(a,b)
       cnt=P[y][2]
    elif P[a][1]!=0 and P[b][1]!=0:
        if P[a][1]==P[b][1]:
            continue
        else:
            P[a][1]=P[P[a][1]][1]
            P[b][1]=P[P[b][1]][1]
            x=min(P[a][1],P[b][1])
            y=max(P[a][1],P[b][1])
            cnt+=P[y][2]
    else:
        if P[a][1]!=0:
            P[a][1]=P[P[a][1]][1]
            x=P[a][1]
            y=b
        else:
            P[b][1]=P[P[b][1]][1]
            x=P[b][1]
            y=b
        cnt=P[y][2]

    P[a][1]=x
    P[b][1]=x
    P[x][2]+=cnt
ans=0
for i in range(1,N+1):
    x=P[i][1]
    if x!=0:
        P[i][2]=P[x][2]

for i in range(1,N+1):
    ans=max(ans,P[i][2])

print(ans)

Submission status: Wrong Answer

Solution code:
N,M=list(map(int,input().split()))
X=[]
for i in range(M):
    X.append(list(map(int,input().split())))
dic={i:[i] for i in range(1,N+1)}
for i in range(M):
    if X[i][1] not in dic[X[i][0]]:
        dic[X[i][0]].append(X[i][1])
    if X[i][0] not in dic[X[i][1]]:
        dic[X[i][1]].append(X[i][0])
c=1
for i in range(1,N+1):
    c=max(c,len(dic[i]))
print(c)

Submission status: Wrong Answer

Solution code:
N,M=list(map(int,input().split()))
X=[]
for i in range(M):
    X.append(list(map(int,input().split())))
dic={i:[i] for i in range(1,N+1)}
for i in range(M):
    if X[i][1] not in dic[X[i][0]]:
        dic[X[i][0]].append(X[i][1])
    if X[i][0] not in dic[X[i][1]]:
        dic[X[i][1]].append(X[i][0])
c=1
for i in range(1,N+1):
    c=max(c,len(dic[i]))
print(c)
print(dic)

Submission status: Wrong Answer

Solution code:
N,M=list(map(int,input().split()))
X=[]
for i in range(M):
    X.append(list(map(int,input().split())))
dic={i:[] for i in range(1,N+1)}
for i in range(M):
    if X[i][1] not in dic[X[i][0]]:
        dic[X[i][0]].append(X[i][1])
    if X[i][0] not in dic[X[i][1]]:
        dic[X[i][1]].append(X[i][0])
c=0
for i in range(1,N+1):
    c=max(c,len(dic[i]))
print(c+1)

Submission status: Wrong Answer

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

P=[[0,0,0]]
for i in range(1,N+1):
    P.append([i,0,0])

R=[]
for i in range(M):
    a,b=map(int,input().split())
    c=max(a,b)
    a=min(a,b)
    b=c
    R.append((a,b))

R=sorted(list(set(R)))

for i in range(len(R)):
    #親の番号
    x=0
    #新たに増えるグループの人数
    cnt=0
    a=R[i][0]
    b=R[i][1]
    if P[a][1]==0 and P[b][1]==0:
       x=min(a,b)
       cnt=2
    elif P[a][1]!=0 and P[b][1]!=0:
        x=min(P[a][1],P[b][1])
        cnt=1
    else:
        if P[a][1]!=0:
            x=P[a][1]
        else:
            x=P[b][1]
        cnt=1
    P[a][1]=x
    P[b][1]=x
    P[x][2]+=cnt
ans=0
for i in range(1,N+1):
    if P[i][0]==P[i][1]:
        ans=max(ans,P[i][2])
print(ans)

Submission status: Wrong Answer

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

P=[[0,0,0]]
for i in range(1,N+1):
    P.append([i,0,0])

R=[]
for i in range(M):
    a,b=map(int,input().split())
    c=max(a,b)
    a=min(a,b)
    b=c
    R.append((a,b))

R=sorted(list(set(R)))

for i in range(len(R)):
    #親の番号
    x=0
    #新たに増えるグループの人数
    cnt=0
    a=R[i][0]
    b=R[i][1]
    if P[a][1]==0 and P[b][1]==0:
       x=min(a,b)
       cnt=2
    elif P[a][1]!=0 and P[b][1]!=0:
        x=min(P[a][1],P[b][1])
        cnt=1
    else:
        if P[a][1]!=0:
            x=P[a][1]
        else:
            x=P[b][1]
        cnt=1
    P[a][1]=x
    P[b][1]=x
    P[a][2]+=cnt
    P[b][2]=P[a][2]
ans=0
for i in range(1,N+1):
    ans=max(ans,P[i][2])

print(ans)