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: Runtime Error

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

class QuickFind(object):
    id = []
    count = 0

    def __init__(self, n):
        self.count = n
        i = 0
        while i < n:
            self.id.append(i)
            i += 1

    def connected(self, p, q):
        return self.find(p) == self.find(q)

    def find(self, p):
        return self.id[p]

    def union(self, p, q):
        idp = self.find(p)
        if not self.connected(p, q):
            for i in range(len(self.id)):
                if self.id[i] == idp:  # 将p所在组内的所有节点的id都设为q的当前id
                    self.id[i] = self.id[q]
            self.count -= 1

qf = QuickFind(5000)
for k in abList:
    p = k[0]
    q = k[1]
    qf.union(p, q)

def most_frequent(List):
    counter = 0
    num = List[0]
    for i in List:
        curr_frequency = List.count(i)
        if (curr_frequency > counter):
            counter = curr_frequency
            num = i
    return counter

print(most_frequent(qf.id))

Submission status: Runtime Error

Solution code:
import numpy

N, M = map(int, input().split())
R = numpy.array([[int(r) for r in input().split()] for _ in range(M)]) - 1

size = [1] * N

groups = numpy.array([-1] * N)
gnum = 1
sameinfo = []

for p1, p2 in R:

    g1 = groups[p1]
    g2 = groups[p2]

    if g1 == -1 and g2 == -1:
        groups[p1] = gnum
        groups[p2] = gnum
        gnum += 1

    elif g1 != -1 and g2 == -1:
        groups[p2] = g1

    elif g1 == -1 and g2 != -1:
        groups[p1] = g2

    elif g1 != -1 and g2 != -1:
        sameinfo.append([min(g1, g2), max(g1, g2)])

for s1, s2 in sameinfo:
    groups[groups == s2] = s1


groups = groups[groups != -1]
maxgroup = numpy.argmax(numpy.bincount(groups))
print(numpy.count_nonzero(groups == maxgroup))

Submission status: Runtime Error

Solution code:
import numpy as np
n,m =map(int,input().split())
a = np.zeros((n,n))
for i in range(m):
  x,y = map(int,input().split())
  a[x-1][y-1] = 1
  a[y-1][x-1] = 1
used_list =[]
count =0
for j in range(n):
  if j in used_list:
    continue
  else:
    used_list.append(j)
  count +=1
  for k in range(j,n):
    if k in used_list:
      continue
    b = a[j] + a[k]
    if b[j]==1 or 2 in b:
      continue
    else:
      used_list.append(k)


print(count)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import numpy as np
import copy
N,M=map(int,input().split())
friend=defaultdict(list)
for _ in range(M):
    a,b=map(int,input().split())
    friend[a].append(b)
    friend[b].append(a)
friend2={i:list(set(j)) for i,j in friend.items()}
for i,j in friend.items():
    j=list(set(j))
    if len(j)<=1:
        continue
    for k in range(len(j)):
        for kk in range(k+1,len(j)):
            friend2[j[k]].append(j[kk])
            friend2[j[kk]].append(j[k])
friendcount={i:len(set(j)) for i,j in friend2.items()}
maxmax=np.max(list(friendcount.values()))+1
print(maxmax)

Submission status: Runtime Error

Solution code:
from collections import deque

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

edge = [[0]*n for i in range(n)]

for i in range(m):
  edge[a[i]-1][b[i]-1] = 1
  edge[b[i]-1][a[i]-1] = 1
  
maxcon = 0
con = 0

yet = [-1 for i in range(n)]

for i in range(n):
  con = 0
  if yet[i] == -1:
    yet[i] = 1
    con = 1
    d = deque([i])
    while d:
      now = d.popleft()
      for j in range(n):
        if edge[now][j] == 1 and yet[j] == -1:
          d.append(j)
          yet[j] = 1
          con += 1
  if con > maxcon:
    maxcon = con

print(maxcon)

Submission status: Runtime Error

Solution code:
import numpy as np


N, M = map(int,input().split())
Adj=np.identity(N)
for i in range(M):
    A, B=  map(int,input().split())
    Adj[A-1,B-1]=1
    Adj[B-1,A-1]=1

AD=Adj**2
count=0
for i in range(N):
    if np.count_nonzero(AD[i, :])>count:
        count=np.count_nonzero(AD[i, :])
print(count)

Submission status: Runtime Error

Solution code:
N, M = (int(x) for x in input().split())
import collections
Parent = [i for i in range(N)]
for _ in range(M):
    a, b = (int(x) for x in input().split())
    Parent[max(a,b)-1] = min(a,b)-1

def fp(i):
    global Parent
    if Parent[i] == i:
        return i
    else:
        Parent[i] == fp(Parent[i])
        return Parent[i]


Groupsize = collections.defaultdict(lambda:0)
for i in range(N):
    i = fp(i)
    Groupsize[i] +=1
ans = max(gs for gs in Groupsize.values())
print(ans)

Submission status: Runtime Error

Solution code:
def abc177d():
    n, m = map(int, input().split())
    check = [-1] * n
    group_no = 0
    group = {}
    for i in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        if check[a] == check[b] != -1: continue
        if check[a] == check[b] == -1:
            group[group_no] = {a, b}
            check[a] = check[b] = group_no
            group_no += 1
        elif check[a] == -1 or check[b] == -1:
            max_g = max(check[a],check[b])
            group[max_g] |= {a,b}
            check[b] = check[a] = max_g
        else:
            re = min(check[a], check[b])
            de = max(check[a], check[b])
            for v in group[de]:
                check[v] = re
            group[re] |= group[de]
            del group[de]
    max_val = max(map(len, group.values()))
    print(max(1,max_val))


abc177d()

Submission status: Runtime Error

Solution code:
group = [1]*N
ngroup = [[0 for i in range(N)] for i in range(N)]
for i in range(M):
    group[AB[i][0]-1] += 1
    group[AB[i][1]-1] += 1
print(max(group))

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = list(range(n)) #親
        self.rank = [0] * n #根の深さ

    # xの属する根を求める
    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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            # if they have the same parent, no need to union
            return
        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

    # xとyが同じ集合に属するかを判定（同じ根に属するか）
    def same(self, x, y):
        return self.find(x) == self.find(y)


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

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

cnt = [0] *n
for i in range(N):
    cnt[uf.par[i]] += 1
print(max(cnt))

Submission status: Runtime Error

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

A_set = set()
B_set = set()
A = []
B = []
for i in range(M):
    a, b = map(int, input().split())
    if (a < b):
        A_set.add(a)
        A.append(a)
        B_set.add(b)
        B.append(b)
    else:
        A_set.add(b)
        A.append(b)
        B_set.add(a)
        B.append(a)


count = 0
group = [set()]
member = []
for a in A_set:
    group[count].add(a)
    for i in range(M):
        if (A[i] == a):
            group[count].add(B[i])    
    member.append(len(group[count]))
    group.append(set())
    count = count + 1

print(max(member))

Submission status: Runtime Error

Solution code:
from collections import defaultdict

def dfs(target):
    if target in visited:
        return 0
    visited.add(target)
    node_count = 1
    for neighbor in adj_list[target]:
        #if neighbor != parent:
        node_count += dfs(neighbor)
    return node_count

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

A, B = [], []

adj_list = defaultdict(set)

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

visited = set([])
count = 1

for node in range(1, N+1):
    count = max(dfs(node), count)
print(count)

Submission status: Runtime Error

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

sums = 0
for i in range(n):
    sums += a[i]

sums *= sums;
ans = sums;

for i in range(n):
    ans -= a[i]*a[i]
ans /= 2

ans %= 1000000007
print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter

class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * 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 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
            

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

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

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
x = [list(map(int, input().split()))]
for i in range(1, m):
    ab = list(map(int, input().split()))
    cnt = 0
    for j in range(len(x)):
        if ab[0] in x[j] or ab[1] in x[j]:
            x[j].extend(ab)
            x[j] = list(set(x[j]))
        else:
            cnt += 1
            if cnt == len(x):
                x.append(ab)
ans = 0
for k in range(len(x)):
    ans = max(ans, len(x[k]))
print(ans)

Submission status: Runtime Error

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

friend_list = [set()]
input_list = []

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

sorted(input_list)

for inp in input_list:
    found = False
    for friend_set in friend_list:
        if inp[0] in friend_set:
            friend_set.add(b)
            found = True
            break
        # elif b in friend_set:
        #     friend_set.add(a)
        #     found = True
        #     break
    if not found:
        friend_set = set()
        friend_set.add(a)
        friend_set.add(b)
        friend_list.append(friend_set)

ans = 0
for friend_set in friend_list:
    ans = max(len(friend_set), ans)

print(ans)

Submission status: Runtime Error

Solution code:

def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

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


s = set()
J = {}
for i in range(m):
    t1,t2 = map(int,input().split())
    if t1 < t2:
        if t1 in J:
            if t2 not in J[t1]:
                J[t1].append(t2)
        else:
            J[t1] = [t2]
    else:
        if t2 in J:
            if t1 not in J[t2]:
                J[t2].append(t1)
        else:
            J[t2] = [t1]
        
#print(J)

def check(key, checkL, setL):
    if key in setL:
        for i in setL[key]:
            if i not in checkL:
                checkL.add(i)
                checkL = check(i, checkL, setL)
            
    return checkL

checkL = set()
ans  = 0
s = set()

for i in J.keys():
    checkL.clear()
    if i not in s:
        checkL.add(i)
        checkL = check(i, checkL, J)
        if ans < len(checkL):
            ans = len(checkL)
        s = s | checkL
        #print(checkL,s)

print(ans)

Submission status: Runtime Error

Solution code:
from __future__ import print_function
range = xrange
input = raw_input
import sys,bisect

from sys  import stdin,stdout

from bisect import bisect_left,bisect_right,bisect,insort,insort_left,insort_right

from math import gcd,ceil,floor,sqrt

from collections import Counter,defaultdict,deque,OrderedDict

dx=[-1,1,0,0]
dy=[0,0,1,-1]


sys.setrecursionlimit(10**6)
INF = float('inf')
MOD = 998244353
mod = 10**9+7

def isPrime(n):
    if (n <= 1) :return False
    if (n <= 3) :return True
    if (n%2 == 0 or n%3 == 0):return False
    for i in range(5,ceil(sqrt(n))+1,6):
        if (n%i==0 or n%(i+2)==0):
            return False
    return True

def st():
    return list(stdin.readline().strip())

def inp():
    return int(stdin.readline())

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

def mp():
    return map(int,stdin.readline().split())

def pr(n):
    stdout.write(str(n)+"\n")

def CC(d,v,i,l):
    v[i]=True
    stack=[i]
    c=1
    while stack:
        a=stack.pop()
        for i in d[a]:
            if not v[i]:
                stack.append(i)
                v[i]=True
                c+=1
    l.append(c)
    
def solve():
    n,m=mp()
    d={i:[] for i in range(1,n+1)}
    for i in range(m):
        a,b=mp()
        d[a].append(b)
        d[b].append(a)

    v=[False for i in range(n+1)]
    x=[]
    for i in range(1,n+1):
        if not v[i]:
            CC(d,v,i,x)


    x.sort()
    cd=0
    while sum(x)!=0:
        for i in range(len(x)):
            if x[i]>0:
                x[i]-=1
        cd+=1
    pr(cd)
        
        
    
for _ in range(1):
    solve()

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
frl = [] #friend list
number = [0]*n #personal number
lnum = 1
for i in range(m):
	a,b = map(int,input().split())
	if number[a-1] == 0 and number[b-1] == 0:
		number[a-1] = lnum
		number[b-1] = lnum
		frl.append([a,b])
		lnum += 1
	elif number[a-1] != 0 and number[b-1] != 0:
		if number[a-1] != number[b-1]:
			frl[number[a-1]-1].extend(frl[number[b-1]-1])
			frl[number[b-1]-1] = frl[number[a-1]-1]
	elif number[a-1] != 0:
		frl[number[a-1]-1].append(b)
		number[b-1] = number[a-1]
	elif number[b-1] != 0:
		frl[number[b-1]-1].append(a)
		number[a-1] = number[b-1]
leng = []
for i in range(len(frl)):
	leng.append(len(frl[i]))
print(max(leng))

Submission status: Runtime Error

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

def main():
    n , m = map( int, input().split() )
    Sets = []

    Dicto = [ -1 for i in range(n + 1)]

    for i in range( m ):
        a , b = map( int , input().split() )
        if Dicto[a] == -1 and Dicto[b] == -1:
            Sets.append( set( [a,b] ) )
            x_i = len(Sets)
            Dicto[ a ] = x_i - 1
            Dicto[ b ] = x_i - 1
        elif Dicto[ a ] != -1 and Dicto[ b ] == -1:
            Sets[ Dicto[a] ].add( b )
            Dicto[ b ] = Dicto[a]
        elif Dicto[ b ] != -1 and Dicto[ a ] == -1:
            Sets[ Dicto[b] ].add( a )
            Dicto[ a ] = Dicto[b]
        elif Dicto[ b ] != -1 and Dicto[ a ] != -1:
            if Dicto[ b ] > Dicto[ a ]:
                set_x = Sets.pop( Dicto[b] )
                Sets[ Dicto[a] ] |= ( set_x )
                l_set_x = list( set_x )
                for j in l_set_x:
                    Dicto[j] = Dicto[a]

            else:
                set_x = Sets.pop( Dicto[a] )
                Sets[ Dicto[b] ] |= ( set_x )
                Dicto[a] = Dicto[b]

    #print(Sets)
    #print(Dicto)

    max_len = 1

    for i in range( len(Sets) ):
        if max_len < len( Sets[i] ):
            max_len = len( Sets[i] )

    print(max_len)


main()

Submission status: Runtime Error

Solution code:
from collections import deque

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

edge = [[0]*n for i in range(n)]

for i in range(m):
  edge[a[i]-1][b[i]-1] = 1
  edge[b[i]-1][a[i]-1] = 1
  
maxcon = 0
con = 0

yet = [-1 for i in range(n)]


for i in range(n):
  con = 0
  if yet[i] == -1:
    yet[i] = 1
    con = 1
    d = deque([i])
    while d:
      now = d.popleft()
      for j in range(n):
        if edge[now][j] == 1 and yet[j] == -1:
          d.append(j)
          yet[j] = 1
          con += 1
    if con > maxcon:
      maxcon = con

print(maxcon)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from collections import Counter
N, M = map(int, input().split())
groups = [0] * (N + 1)
group_num_list = [[0]]
group_num = 1
for _ in range(M):
    A, B = map(int, input().split())
    if groups[A] != 0 and groups[B] != 0:
        if groups[A] != groups[B]:
            lower = min(groups[A], groups[B])
            higher = max(groups[A], groups[B])
            for i in group_num_list[higher]:
                groups[i] = lower
            tmp = group_num_list[higher]
            group_num_list[lower].extend(tmp)
            # del group_num_list[higher]
    elif groups[A] != 0:
        groups[B] = groups[A]
        group_num_list[groups[A]].append(B)
    elif groups[B] != 0:
        groups[A] = groups[B]
        group_num_list[groups[B]].append(A)
    else:
        groups[A] = group_num
        groups[B] = group_num
        #group_num_list.append([A, B])
        group_num += 1
counter = Counter(groups)
# print(collection)
# print(group_num_list)
if counter.most_common()[0][0] != 0:
    print(counter.most_common()[0][1])
else:
    print(counter.most_common()[1][1])

Submission status: Runtime Error

Solution code:
import math
import collections
import itertools

def resolve():
    #N=int(input())
    N,M=map(int,input().split())
    Gr = [[] for y in range(N)]
    GrNum=1

    A0,B0=map(int,input().split())
    Gr[0].append(A0)
    Gr[0].append(B0)
    Max=2
    for i in range(M-1):
        A,B=map(int,input().split())
        found=False
        for j in range(GrNum):
            if(A in Gr[j]):
                if(B not in Gr[j]):
                    Gr[j].append(B)
                found=True
            if(B in Gr[j]):
                if(A not in Gr[j]):
                    Gr[j].append(A)
                found=True
            tmp=len(Gr[j])
            Max=max(Max,len(Gr[j]))
        if(found!=True):
            Gr[GrNum].append(A)
            Gr[GrNum].append(B)
            GrNum+=1                

    ans=Max

    print(ans)

resolve()

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
li = [0]*(n+1)
flag = 1
for _ in range(m):
    a, b = map(int, input().split())
    if li[a] and li[b]:
        if li[a]!=li[b]:
            x = li[b]
            for i in len(li):
                if li[i]==x:
                    li[i] = li[a]
    elif li[a] or li[b]:
        s = max(li[a],li[b])
        li[a] = s
        li[b] = s
    else:
        li[a] = flag
        li[b] = flag
        flag += 1
for i in range(len(li)):
    if li[i] == 0:
        li[i] = -i
from collections import Counter
result = Counter(li)
print(result.most_common(1)[0][1])

Submission status: Runtime Error

Solution code:
from collections import defaultdict

def dfs(node):
    if node in visited:
        return 0
    visited.add(node)
    node_count = 1
    for neighbor in adj_list[node]:
        #if neighbor != parent:
        node_count += dfs(neighbor)
    return node_count

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

A, B = [], []

adj_list = defaultdict(set)
visited = set([])

count = 1

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

for node in range(1, N+1):
    count = max(dfs(node), count)
print(count)

Submission status: Runtime Error

Solution code:
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 5)


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


def union(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    parent[x] = y


def find(x):
    if parent[x] == -1:
        return x
    res = parent[x] = find(parent[x])
    return res

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


count = Counter(find(i) for i in range(N))
print(count.most_common(1)[0][1])

Submission status: Runtime Error

Solution code:
from collections import Counter
N, M = map(int, input().split())
groups = [0] * (N + 1)
group_num_list = [[0]]
group_num = 1
for _ in range(M):
    A, B = map(int, input().split())
    if groups[A] != 0 and groups[B] != 0:
        if groups[A] != groups[B]:
            lower = min(groups[A], groups[B])
            higher = max(groups[A], groups[B])
            for i in group_num_list[higher]:
                groups[i] = lower
            tmp = group_num_list[higher]
            group_num_list[lower].extend(tmp)
            # del group_num_list[higher]
    elif groups[A] != 0:
        groups[B] = groups[A]
        group_num_list[groups[A]].append(B)
    elif groups[B] != 0:
        groups[A] = groups[B]
        group_num_list[groups[B]].append(A)
    else:
        groups[A] = group_num
        groups[B] = group_num
        group_num_list.append([A, B])
        group_num += 1
counter = Counter(groups)
# print(collection)
# print(group_num_list)
if counter.most_common()[0][0] != 0:
    print(counter.most_common()[0][1])
else:
    print(counter.most_common()[1][1])

Submission status: Runtime Error

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

# from typing import Optional
# from typing import List
# from typing import Dict
# from typing import Tuple
# from typing import Sequence


def main():
    args = input().split()
    N = int(args[0])
    M = int(args[1])

    groupList = set()
    for i in range(M):
        args = list(map(lambda x: int(x), input().split()))

        isHit = False
        for group in groupList:
            if args[0] in group:
                groupList.remove(group)
                newGroup = set(group)
                newGroup.add(args[1])
                groupList.add(frozenset(newGroup))
                isHit = True
            elif args[1] in group:
                groupList.remove(group)
                newGroup = set(group)
                newGroup.add(args[0])
                groupList.add(frozenset(newGroup))
                isHit = True

        if not isHit:
            groupList.add(frozenset({args[0], args[1]}))

    maxNum = 0
    for group in groupList:
        maxNum = max(maxNum, len(group))

    print(maxNum)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# from collections import deque

n, m = map(int, input().split())
# # arr = [tuple(map(int, input().split())) for _ in range(m)]

# f = {a: set() for a in range(1, n+1)}
# for _ in range(m):
#     x, y = map(int, input().split())
#     f[x].add(y)
#     f[y].add(x)

# res = 0
# visited = set()
# stack = deque()
# for i in range(1, n+1):
#     if i in visited:
#         continue
#     visited = {i}
#     stack = deque([i])
#     while stack:
#         c = stack.pop()
#         for v in f[c]:
#             if v not in visited:
#                 visited.add(v)
#                 stack.append(v)
#     res = max(res, len(visited))

# print(res)

f = []
for _ in range(m):
    x, y = map(int, input().split())
    for f_ in f:
        if x in f_ or y in f_:
            f_.update((x, y))
            break
    else:
        f.append({x, y})

print(max([len(f_) for f_ in f]))

Submission status: Runtime Error

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

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

marks = [False for i in range(N)]

def dfs(n):
    global E_list
    global marks
    global N,M

    marks[n] = True

    steps = 1

    for nx in E_list[n]:
        if not marks[nx]:
            marks[nx] = True
            steps += dfs(nx)
    
    return steps



for i in range(M):
    e1,e2 = map(int, input().split())
   
    E_list[e1-1].append(e2-1)
    E_list[e2-1].append(e1-1)

m = 1



for i in range(N):
    if not marks[i]:
        st = dfs(i)

    m = max(m,st)

print(m)

Submission status: Runtime Error

Solution code:
from math import gcd
from collections import defaultdict
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return [a[0] for a in arr]

N = int(input())
A = sorted([int(i) for i in input().split()])
dict_A = defaultdict(int)
dep_flag = False
for a in A:
  dict_A[a] += 1
  if a != 1 and dict_A[a] >= 2:
    dep_flag=True
if dep_flag == False:  
  all_flag = True
  devisors = set()
  for n in range(N-1):
      if n == 0:
          g = gcd(A[n],A[n+1])
      else:
          g = gcd(A[n+1],g)
      temp = factorization(A[n])
      for t in temp:
          if t in devisors:
              all_flag=False
          else:
              devisors.add(t)
  if all_flag and g == 1:
      print('pairwise coprime')
  elif g==1:
      print('setwise coprime')
  else:
      print('not coprime')
else:
    print('not coprime')

Submission status: Runtime Error

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

dic = dict((i, set()) for i in range(1,N+1))
#print(dic)

for _ in range(M):
    a,b = map(int, input().split()) 
    dic[a].add(b)
    dic[b].add(a)

#print(dic)

def dfs(x:int, marked:set):
    a = set()
    a = a.union(dic[x])
    marked.add(x)
    for i in dic[x]:
        if i not in marked:
            b, marked = dfs(i, marked)
            a = a.union(b)

    return a, marked



res = 0
for i in range(1,N+1):
    a, marked = dfs(i, set())
    #print(a,marked)
    if len(a) > res:
        res = len(a)

print(res)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
count = 0
people = set()
friends = []
while count < M:
    A, B = map(int,input().split())
    if A in people and B not in people:
        for f in friends:
            if A in f:
                f += [B]
    elif B in people and A not in people:
        for f in friends:
            if B in f:
                f += [A]
    elif A not in people and B not in people:
        friends += [[A,B]]
    people = people.union({A,B})
    count += 1

print(max(len(f) for f in friends))

Submission status: Runtime Error

Solution code:
from collections import defaultdict

def dfs(node):
    if node in visited:
        return 0
    visited.add(node)
    count = 1
    for neighbor in adj_list[node]:
        #if neighbor != parent:
        count += dfs(neighbor)
    return count

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

A, B = [], []

adj_list = defaultdict(set)
visited = set([])

count = 1

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

count = 0
for node in range(1, N+1):
    count = max(dfs(node), count)
print(count)

Submission status: Runtime Error

Solution code:
from collections import defaultdict as dc
x, y = map(int, input().split())
graph = [[] for n in range(x+1)]

st = dc(lambda: 0)

for n in range(y):
    a, b = map(int, input().split())

    if a > b:
        a, b = b, a
    graph[a].append(b)
    graph[b].append(a)


res = 0
vis = dc(lambda: 0)


def dfs(node):
    global res
    vis[node] = 1
    res += 1
    for n in graph[node]:
        if vis[n] == 0:
            dfs(n)


mx = 0
for n in range(1, x+1):
    res = 0
    if vis[n] == 0:
        dfs(n)
        mx = max(mx, res)

print(mx)

Submission status: Runtime Error

Solution code:
import random
import sys

sys.setrecursionlimit(100000)

n, m = map(int, input().split())
# n, m = 200000, 200000
group = {i: 0 for i in range(1, n+1)}
edge = {}
g_mem = {}
g_num = 0
g_con = set()

for i in range(m):
    a, b = map(int, input().split())
    # a, b = random.sample(range(1,n+1), 2)
    if group[a]==0 and group[b] == 0:
        g_num += 1
        group[a] = g_num
        group[b] = g_num
        g_mem[g_num] = 2
    elif group[a] == 0:
        group[a] = group[b]
        g_mem[group[b]] += 1
    elif group[b] == 0:
        group[b] = group[a]
        g_mem[group[a]] += 1
    elif group[a] != group[b]:
        if edge.get(group[a]):
            edge[group[a]].add(group[b])
        else:
            edge[group[a]] = {group[b]}
        if edge.get(group[b]):
            edge[group[b]].add(group[a])
        else:
            edge[group[b]] = {group[a]}

# print(g_mem)
# print(sum(g_mem.values()))
# print(edge)

g_reached = {i: 0 for i in range(1, g_num+1)}

def dps(g_mem, edge, now):
    count = g_mem[now]
    if edge.get(now):
        for e in edge[now]:
            edge[e].remove(now)
            if g_reached[e] == 0:
                g_reached[e] = 1
                count += g_mem[e]
                for ee in edge[e]:
                    edge[ee].remove(e)
                    if g_reached[ee] == 0:
                        g_reached[ee] = 1
                        count += dps(g_mem, edge, ee)
    return count


ans = []
for now in range(1, g_num+1):
    if g_reached[now] == 0:
        g_reached[now] = 1
        ans.append(dps(g_mem, edge, now))

# print(ans)
print(max(ans))

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque

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

D = defaultdict(deque)
R = [0] * (N+1)
for _ in range(M):
  a, b = map(int, input().split())
  if R[a] != 0:
    if R[b] != 0:
      aa, bb = R[a], R[b] 
      if aa == bb:
        pass
      else:
        if len(D[aa]) < len(D[bb]):
          aa, bb = bb, aa
        for x in D[bb]:
          R[x] = aa
        D[aa].extend(D[bb])
        del D[bb]
    else:
      R[b] = R[a]
      D[R[a]].append(b)
  else:
    if R[b] != 0:
      R[a] = R[b]
      D[R[b]].append(a)
    else:
      R[a] = a
      R[b] = a
      D[a].append(a)
      D[a].append(b)

print(max(len(x) for x in D.values()))

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

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

if M==0:
    print(1)
    sys.exit()

    
    
friends_map = np.zeros(shape=(N, N))

for _ in range(M):
    A_i, B_i = map(int, input().split())
    friends_map[A_i-1][B_i-1] = 1
    friends_map[B_i-1][A_i-1] = 1

ans = 0
for row in friends_map:
    ans = max(ans, sum(row))
    
print(int(ans+1))