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,Q = 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
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x]==rank[y]:rank[x]+=1

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

from collections import*
C=Counter(par)
A=max(C.values())
B=sum(v==1 for v in C.values())-1
print(max(A,B))

Submission status: Wrong Answer

Solution code:
import collections
n,m = map(int,input().split())
if m==0:
  print(1)
  exit()
g = [-1]*n
for i in range(m):
  a,b = map(int,input().split())
  if g[a-1]!=-1:
    g[b-1] = g[a-1]
  elif g[b-1]!=-1:
    g[a-1] = g[b-1]
  else:
    g[a-1] = i
    g[b-1] = i
c = collections.Counter(g)
cnt = c.most_common()
if cnt[0][0]==-1:
  print (cnt[1][1])
else:
  print (cnt[0][1])

Submission status: Wrong Answer

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

g = [0]*N
n = [0]*N

num = 1

for i in range(len(c)):
    
    if g[c[i][0]-1] != 0 and g[c[i][1]-1] != 0:
        pass
    elif g[c[i][0]-1] != 0:
        g[c[i][1]-1] = g[c[i][0]-1]
        n[g[c[i][0]-1]-1] += 1
    elif g[c[i][1]-1] != 0:
        g[c[i][0]-1] = g[c[i][1]-1]
        n[g[c[i][1]-1]-1] += 1
    else:
        g[c[i][0]-1] = num
        g[c[i][1]-1] = num
        n[num-1] += 2
        num += 1

print(max(n))

Submission status: Wrong Answer

Solution code:
import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque, defaultdict
from fractions import gcd
from functools import reduce
from itertools import groupby, combinations
from heapq import heapify, heappush, heappop

# sys.setrecursionlimit(5000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return list(map(lambda x: x + d, A))
def ldec(A, d=1): return list(map(lambda x: x - d, A))

N, M = nn()
T = nm(M)

d = defaultdict(list)

#memo = array2(N+1, N+1)
memo = defaultdict(dict)

for i in range(M):
    a, b = T[i]
    if b in memo[a]:
        continue
    else:
        d[a].append(b); memo[a][b] = 1
        d[b].append(a); memo[b][a] = 1

ans = 0
for k, v in d.items():
    #print(k, v, len(v))
    tmp = len(v)
    if tmp > ans:
        ans = tmp

print(ans+1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n, m = map(int, input().split())
mydic = defaultdict(set)
for i in range(m):
    ai, bi = map(int, input().split())
    temp = mydic[ai] | mydic[bi]
    tt = {ai, bi}
    mydic[ai] = temp | tt
    mydic[bi] = temp | tt
ans = 0
for i, v in mydic.items():
    # print(i, v)
    ans = max(ans, len(v))
print(ans)

Submission status: Wrong Answer

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

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

f.sort(key=lambda x: len(x), reverse=True)

print(len(f[0])+1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
from collections import deque
from collections import defaultdict
from collections import Counter
import heapq
import collections
import itertools
import bisect
import copy
sys.setrecursionlimit(10**6)

# lis_of_lis = [[] for _ in range(N)]


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


def z(): return int(sys.stdin.readline())


def S(): return sys.stdin.readline()[:-1]


def C(line): return [sys.stdin.readline() for _ in range(line)]


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 = zz()
A = [0]*M
B = [0] * M
tree = UnionFind(N)
# friends = [[0]*N for i in range(N)]
# print(friends)
for i in range(M):
    a, b = zz()
    a -= 1
    b -= 1
    # A[i], B[i] = a, b
    tree.union(a, b)
used = [0]*N
group = UnionFind(N)

for i in range(N):
    if (used[i] == 1):
        # すでに振り分け済み
        continue
    for j in range(i + 1, N):
        if (used[j] == 1):
            # すでに振り分け済み
            continue
        if (tree.same(i, j)):
            # 友達
            continue
        else:
            used[i] = 1
            used[j] = 1
            group.union(i, j)

    # # 全員と友達
    # if (used[i] == 0):
# print(used)
print(group.group_count())


# 最大でNグループにわければいける
# 素朴にやる

Submission status: Wrong Answer

Solution code:
N, M = list(map(int, input().split(" ")))
group = set()
groups = [group]

for _ in range(M):
  a, b = list(map(int, input().split(" ")))
  for group in groups:
    if a in group or b in group:
      group.add(a)
      group.add(b)
    else:
      s = {a, b}
      groups.append(s)

print(max([len(group) for group in groups]))

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


#S=[[0] * 3 for _ in range(2)] 2行3列の場合
S = [[]for i in range(N+1)]

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

tmp=0
for i in range(1,N+1):
    tmp2=len(set(S[i]))
    if tmp2>tmp:
        tmp=tmp2

print(tmp+1)

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[A - 1].union(person[B - 1])
        
        person[B - 1].add(A - 1)
        person[B - 1].union(person[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

if __name__ == '__main__':
    N, M = list(map(lambda x: int(x), sys.stdin.readline().split()))
    matrix = [0 for i in range(N)]
    s = set()
    for _ in range(M):
        a, b = list(map(lambda x: int(x), sys.stdin.readline().split()))
        if (a,b) in s:
            continue
        s.add((a,b))
        s.add((b,a))
        matrix[a-1] += 1
        matrix[b-1] += 1

    # つながっている最大のグラフを求めればいい
    print(max([matrix[i] for i in range(N)])+1)

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
    if info_count == 0:
        return 1
    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]
        new_id += 1
        if id_a == -1 == id_b:
            frieds_circle_ids[a] = new_id
            frieds_circle_ids[b] = new_id
        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.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
        
        # 根のparentsはそのグループの要素数 * (-1) がはいる
        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 _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    uf.union(a, b)
    ans = max(ans, uf.size(a))

print(ans)

Submission status: Wrong Answer

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

l = []  # 同値類のリスト
d = {}  # 各人がいるlのindex
tmp = 0

for i in range(M):
    A, B = map(int, input().split())
    if (d.get(A) == None) and (d.get(B) == None):
        d[A] = tmp
        d[B] = tmp
        tmp += 1
        l.append([A, B])
    elif (d.get(A) != None) and (d.get(B) == None):
        d[B] = d[A]
        l[d[A]].append(B)
    elif (d.get(A) == None) and (d.get(B) != None):
        d[A] = d[B]
        l[d[B]].append(A)
    else:
        continue

if M == 0:
    ans = 1
else:
    ans = 1
    for i in range(len(l)):
        ans = max(len(l[i]), ans)

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

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

checker = []

for _ in range(N):
    checker.append(set())


for AB in ABs:
    checker[AB[0] - 1].add(AB[1])
    checker[AB[1] - 1].add(AB[0])

#print(checker)

ans = 1

for anscheck in checker:
    ans = max(ans, len(anscheck)+1)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
N, M = map(int, input().split())
tree = [[] for _ in range(N)]
happend = set()
for _ in range(M):
    a, b = map(lambda x: int(x)-1, input().split())
    if (a, b) not in happend and (b, a) not in happend:
        tree[a].append(b)
        tree[b].append(a)
        happend.add((a, b))
        happend.add((b, a))
visited = [False]*N
visited[0] = True
q = deque()
ans = 0
for i in range(N):
    if visited[i]:
        continue
    q.append(i)
    tmp = 1
    while len(q):
        v = q.popleft()
        for e in tree[v]:
            # print("v , e", v, e)
            if visited[e]:
                continue
            visited[e] += 1
            tmp += 1
            q.append(e)
            # print("tmp : ", tmp)
    ans = max(tmp, ans)
# print(tree)
print(ans)

Submission status: Wrong Answer

Solution code:
import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")
al = "abcdefghijklmnopqrstuvwxyz"

n, m=I()
people = [[] for i in range(n)]

for i in range(m):
    A,B=I()
    people[A-1].append(B-1)
    people[A-1] = list(set(people[A-1]))

befo = []

for i in people:
    if i not in befo:
        befo.append(i)
    if i == []:
        ans += 1

if ans == 1:
    print(len(befo))
else:
    print(len(befo)-1)

Submission status: Wrong Answer

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

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


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

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:
def resolve():
    '''
    code here
    '''
    N, M = [int(item) for item in input().split()]

    edges = [[int(item) for item in input().split()] for _ in range(M)]
    links = [set() for _ in range(N+1)]

    for a, b in edges:
        links[a].add(b)
        links[b].add(a)

    max_num = 0
    for item in links:
        max_num = max(max_num, len(item))

    print(max_num +1)



if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

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

relations = []
for i in range(M):
    relations.append([int(i) for i in input().split()])
    
def search(node,stock):
    go_list = set()
    ng_list = []
    
    for s in stock:
        go = False
        for n in node:
            if n in s:
                go = True
                break
        if go:
            go_list = go_list | set(s)
        else:
            ng_list.append(s)
    node = set(node) | go_list    
    
        
    while(len(go_list)>0):
        go_list_ = set()
        ng_list_ = []
        for ng in ng_list:
            go = False
            if len(set(ng)& go_list)>0:
                go = True
                break
            if go:
                go_list_ = go_list_ | set(ng)
            else:
                ng_list_.append(ng)
        go_list = go_list_
        ng_list = ng_list_        
        node = node | go_list 
            
    return len(node),ng_list

    
MaxMember = 0    
while(len(relations)>1):
    l_member,relations = search(relations[0],relations[1:])
    MaxMember = max(MaxMember,l_member)

print(MaxMember)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
M=set(tuple(map(int,input().split())) for _ in range(m))
d={i:set() for i in range(1,n+1)}

for a,b in M:
    d[min(a,b)].add(max(a,b))

MAX = 0
for i in d.values():
    MAX=  max(MAX,len(i))
print(MAX+1)

Submission status: Wrong Answer

Solution code:
n,m = (int(x) for x in input().split())
friendlist = [0]*n
classes = 1
for i in range(m):
    a,b = (int(x)-1 for x in input().split())
    if friendlist[a]!=0:
        friendlist[b] = friendlist[a]
    elif friendlist[b]!=0:
        friendlist[a] = friendlist[b]
    else:
        friendlist[a] = classes
        friendlist[b] = classes
        classes += 1

count = [0]*(classes+1)
for i in range(n):
    count[friendlist[i]] += 1

print(max(count[1:]))

Submission status: Wrong Answer

Solution code:
from collections import *
n,m=map(int,input().split())
if(m==0):
    print(1)
else:
    f={}
    d=[]
    for i in range(m):
        l=list(map(int,input().split()))
        q=sorted(l)
        r=tuple(q)
        if(r not in f):
            f[r]=1
            d.append(q)
    dd=defaultdict(int)
    for i in d:
        dd[i[0]]+=1
        dd[i[1]]+=1
    k=max(dd.values())
    print(k+1)

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
        if parent[a] < parent[b]:
            parent[b] = parent[a]
        else:
            parent[a] = parent[b]

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

    print(max(cnt))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: UTF-8 -*-

class UnionFind:
    def __init__(self, size):
        self.rank=[0]*size
        self.par =[int(i) for i in range(size)]
        self.grp =size

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

        self.par[x]=self.find(self.par[x])
        return self.par[x]

    def same(self, x, y): #2つの頂点が同じグループであるかを判定する
        return self.find(x)==self.find(y)

    def unite(self, x, y): #辺で接続されている2つの頂点を投げて統合する
        x,y=self.find(x),self.find(y)
        if x==y:
            return

        self.grp-=1
        if self.rank[x]<self.rank[y]:
            self.par[x]=y
        else:
            self.par[y]=x
            if self.rank[x]==self.rank[y]:
                self.rank[x]+=1

    def group_num(self):
        return self.grp


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)
b=[1]*n
ans=0
for i in range(n):
    t=set([])
    if b[i]:
        t.add(i)
        b[i]=0
        for j in range(i+1,n):
            f=1
            for k in t:
                if uf.same(k,j):
                    f=0
            if f:
                t.add(j)
                b[j]=0
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
allsets = []
n,t = list(map(int,input().split()))
for _ in range(t):
    a,b = list(map(int,input().split()))
    if a < b and [a,b] not in allsets:
        allsets.append([a,b])
    elif b < a and [b,a] not in allsets:
        allsets.append([b,a])
# print(allsets)
hmap = {}
visitedNode = {}
for a,b in allsets:
    if a in visitedNode:
        if b not in hmap[visitedNode[a]]:
            hmap[visitedNode[a]].append(b)
        continue
    if a in hmap:
        hmap[a].append(b)
        visitedNode[b] = a
    else:
        hmap[a] = [b]
        visitedNode[b] = a
# print(hmap)
res = 0
for k,v in hmap.items():
    res = max(res,len(v)+1)
print(res)

Submission status: Wrong Answer

Solution code:
class Graph:
    def __init__(self,v):
        from collections import defaultdict
        self.v = v
        self.graph = defaultdict(set) 
        self.count = 0
        self.mx = 0

    def addEdge(self,a,b):
        if b in self.graph[a]:
            return
        if a in self.graph[b]:
            return
        self.graph[a].add(b)
        self.graph[b].add(a)

    def dfs(self,node,visited):
        if visited[node]:
            return self.count
        else:
            visited[node] = True
            self.count += 1
        
        for nbr in self.graph[node]:
            if not visited[nbr]:
                visited[nbr] = True
                self.count += 1
                self.dfs(node,visited)

    def solve(self):
        visited = [False]*(self.v+1)

        for i in range(1,self.v+1):
            if not visited[i]:
                self.dfs(i,visited)

            self.mx = max(self.mx, self.count)
            self.count = 0
        return self.mx

if __name__ == "__main__":
    n,m = map(int, input().split())
    if m != 0:        
        g = Graph(n)
        for i in range(m):
            a,b = map(int, input().split())
            g.addEdge(a,b)
        print( g.solve() )
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
AB = []
G = {n:set() for n in range(N)}
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    for a_ in G[a]:
        if a != a_:
            G[a_].add(a)
            G[a_].add(b)
            G[b].add(a_)
    for b_ in G[b]:
        if b != b_:
            G[b_].add(a)
            G[b_].add(b)
            G[a].add(b_)
    G[a].add(b)
    G[b].add(a)
ans = -1
for n in range(N):
    if n in G[n]:
        G[n].remove(n)
    ans = max(ans, len(G[n])+1)
print(ans)

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

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

friend = list()
for a, b in AB:
  a_set = -1
  b_set = -1
  a_f = False
  b_f = False
  for i, f in enumerate(friend):
    if a in f:
      a_set = i
      a_f = True
      if b_f:
        break
    elif b in f:
      b_set = i
      b_f = True
      if a_f:
        break
  if a_set == b_set == -1:
    friend.append({a, b})
  elif a_set == -1:
    friend[b_set].add(a)
  elif b_set == -1:
    friend[a_set].add(b)
  else:
    friend[a_set] = friend[a_set] | friend[b_set]
    friend.pop(b_set)

ans = 0
for f in friend:
  ans = max(len(f), ans)
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
ans = [[set(),0]]
count = 0
for i in range(M):
    A_i, B_i = map(int, input().split())
    for i in range(len(ans)):
        if A_i in ans[i][0] or B_i in ans[i][0]:
            if A_i not in ans[i][0]:
                ans[i][1] += 1
            if B_i not in ans[i][0]:
                ans[i][1] += 1
            ans[i][0].add(A_i)
            ans[i][0].add(B_i)
            count = max(count, ans[i][1])
            break
        if i == len(ans) - 1:
            ans.append([{A_i, B_i}, 2])
            count = max(count, ans[-1][1])
            break
print(count)

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
g = [0 for _ in range(len(groups))]
for i in groups:
  g[i] += 1
print(max(g))

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

    tmp = list(friend[A-1])
    if len(tmp) > 0:
        for i in range(len(tmp)):
            var = tmp[i]
            if var != B-1:
                friend[var].add(B-1)
                friend[B-1].add(var)
    friend[A-1].add(B-1)

    tmp = list(friend[B-1])
    if len(tmp) > 0:
        for i in range(len(tmp)):
            var = tmp[i]
            if var != A-1:
                friend[var].add(A-1)
                friend[A-1].add(var)
    friend[B-1].add(A-1)

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())
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] and (B[i] not in l[A[i]]):
        l[A[i]].append(B[i])
    elif B[i] < A[i] and (A[i] not in l[B[i]]):
        l[B[i]].append(A[i])

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

if ans == 0:
    print(0)
else:
    print(ans+1)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
e = list(set([tuple(sorted(map(int, input().split()))) for _ in range(m)]))
e.sort()
g = {k: k for k in range(1, n+1)}
p = {k: 1 for k in range(1, n+1)}

for a, b in e:
  l = min([g[a], g[b]])
  r = max([g[a], g[b]])
  if l != r:
    g[a] = g[b] = l
    p[l] += p[r]
    p[r] = 0
  
print(max(p.values()))

Submission status: Wrong Answer

Solution code:
from collections import deque

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

friendsetlist = [set([]) for _ in range(n)]

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

    friendsetlist[a].add(b)
    friendsetlist[b].add(a)

stack = deque([])

checked = [0 for _ in range(n)]

checked[0] = 1

ans = 0

for i in range(n):
    if checked[i] == 0:
        stack.append(i)
        tmpans = 1
        while len(stack) != 0:
            now = stack.popleft()
            for nxt in friendsetlist[now]:
                if checked[nxt] == 0:
                    tmpans += 1
                    stack.append(nxt)
                    checked[nxt] = 1
        if ans < tmpans:
            ans = tmpans

print(ans)

Submission status: Wrong Answer

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


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


def readint():
    return int(input())


def readnums():
    return map(int, input().split())


def readstrs():
    return input().split()


def main():
    N, M = readnums()
    ab = [tuple(readnums()) for _ in range(M)]
    al = {i: set() for i in range(1, N + 1)}
    for a, b in ab:
        if not al:
            al[a].add(b)
            al[b].add(a)
        else:
            if b not in al[a]:
                al[a].add(b)
            if a not in al[b]:
                al[b].add(a)

    ans = max(list(map(lambda x: len(x), al.values())))
    print(ans + 1)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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


friends=[]
num=0
people=[-1]*n
ans=0

for f in F:

    if people[f[0]-1]==-1 and people[f[1]-1]==-1:
        friends.append({f[0]-1,f[1]-1})
        people[f[0]-1]=num
        people[f[1]-1]=num
        num+=1

    elif people[f[0]-1]!=-1 and people[f[1]-1]!=-1:
        friends[people[f[0]-1]] = friends[people[f[0]-1]].union(friends[people[f[1]-1]])
        for i in friends[people[f[1]-1]]:
            people[i]=people[f[0]-1]

    elif people[f[0]-1]!=-1:
        friends[people[f[0]-1]].add(f[1]-1)
        people[f[1]-1]=people[f[0]-1]

    elif people[f[1]-1]!=-1:
        friends[people[f[1]-1]].add(f[0]-1)
        people[f[0]-1]=people[f[1]-1]

for i in friends:
    if len(i)>ans:
        ans=len(i)
print(ans)

Submission status: Wrong Answer

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

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

print(max(friends) + 1)

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)
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:
from collections import defaultdict

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_dict = defaultdict(lambda : None)
group_counter = 0
group_member = [0]*(n+1)

update_dict = defaultdict(lambda : None)

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

    a_group = group_dict[a]
    b_group = group_dict[b]
    target_group = -1
    if a_group != None:
        target_group = a_group
    if b_group != None:
        target_group = b_group

    if target_group == -1:
        target_group = group_counter
        group_counter+=1

    if a_group != None and b_group != None:
        target_group = max(a_group,b_group)
        update_dict[min(a_group,b_group)] = max(a_group,b_group)
    
    group_dict[a] = target_group
    group_dict[b] = target_group


for k in group_dict:
    new_k = None
    if update_dict[group_dict[k]] != None:
        new_k = update_dict[group_dict[k]]
    if new_k != None:
        change = new_k
    else:
        change = group_dict[k]
    group_member[change] += 1

print(max(group_member))

Submission status: Wrong Answer

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


#S=[[0] * 3 for _ in range(2)] 2行3列の場合
S = [[]for i in range(N+1)]

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

tmp=0
for i in range(1,N+1):
    if len(S[i])>tmp:
        tmp=len(set(S[i]))

print(tmp+1)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
dic=dict()
for i in range(1,N+1):
  dic[i]=[0]
  
for i in range(M):
  A,B=map(int,input().split())
  if B not in dic[A]:
    dic[A].append(B)
  if A not in dic[B]:
    dic[B].append(A)

ans=sorted(dic.items(),key=lambda x:len(x[1]))
print(len(ans[-1][1]))