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 = map(int, input().split())
count = []
A = []
answer = []

for idx in range(m):
    a, b = map(int, input().split())
    if a < b:
        friends = [a, b]
    else:
        friends = [b, a]
    
    if friends not in A:
        A.append(friends)

A = sorted(A)
A_length = len(A)
sub_list = []
for idx in range(A_length):
    a, b = A[idx][0], A[idx][1]
    if idx == 0:
        sub_list += A[idx]
    elif idx == A_length - 1:
        if A[idx - 1][0] == A[idx][0]:
            sub_list += A[idx]
            sub_list = list(set(sub_list))
            answer.append(sub_list)
        else:
            answer.append(sub_list)
            sub_list = []
            sub_list += A[idx]
            answer.append(sub_list)
    else:
        if A[idx - 1][0] == A[idx][0]:
            sub_list += A[idx]
            sub_list = list(set(sub_list))
        else:
            answer.append(sub_list)
            sub_list = []
            sub_list += A[idx]

for ans in answer:
    count.append(len(ans))

print(max(max(count), n - sum(count)))

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
F=[1]*N
G=[0]*N
for i in range(M):
  A,B=map(int,input().split())
  if G[A-1]!=0 and G[B-1]==0:
    f=F[A-1]+F[B-1]
    F[A-1]=f
    F[B-1]=f
    G[B-1]=G[A-1]
    
  elif  G[A-1]==0 and G[B-1]!=0:
    f=F[A-1]+F[B-1]
    F[A-1]=f
    F[B-1]=f
    G[A-1]=G[B-1]
    
  elif G[A-1]!=G[B-1]:
    f=F[A-1]+F[B-1]
    F[A-1]=f
    F[B-1]=f
    a=G[A-1]
    b=G[B-1]
    for j in range(M):
      if G[j]==b:
        G[j]=a
    
  elif G[A-1]==0 and G[B-1]==0:
    f=F[A-1]+F[B-1]
    F[A-1]=f
    F[B-1]=f
    G[A-1]=i+1
    G[B-1]=i+1
    
  else:
print(max(F))

Submission status: Runtime Error

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

ans = 0

def DFS(n):
    global h, ans
    #print(h)
    if h[n] == 1:
        ans = max(ans, sum(h))
        return
    h[n] = 1
    for x in to[n]:
        DFS(x)

for i in range(N):
    h = [0] * N
    DFS(i)
    if ans >= N / 2:
        break

print(ans)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
a = [list(map(int,input().split())) for i in range(M)]
t = [[0]]*(2*10**5)
for i in range(len(a)):
    for j in range(len(a)):
        if (a[i][0] or a[i][1]) in a[j] and i != j:
            if a[j][0] not in t[i] and a[j][1] in t[i]:
                t[i].append(a[j][1])
            elif a[j][1] not in t[i] and a[j][0] in t[i]:
                t[i].append(a[j][0])
s = []
while i<=(len(t)-1):
    s.append(len(t[i]))
    i += 1
if max(s)<=N//2:
    if max(s)==1:
        print(N)
    else:
        print(N-max(s))
else:
    print(max(s))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
li = [0]*(n+1)
lii = []
flag = 1
for _ in range(m):
    a, b = map(int, input().split())
    if li[a] and li[b]:
        if li[a] != li[b]:
            lii.append(li[a],li[b])
    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
    for j in lii:
        a,b = j
        if li[i] == a or li[i] == b:
            li[i] = a+b
from collections import Counter
result = Counter(li)
print(result.most_common(1)[0][1])

Submission status: Runtime Error

Solution code:
n, m = [int(x) for x in input().split(" ")]
relations = set([tuple([int(x) for x in input().split(" ")]) for _ in range(m)])

table = {}
groups = []
for a, b in relations:
    if a in table:
        table[a].add(b)
        table[b] = table[a]
    elif b in table:
        table[b].add(a)
        table[a] = table[b]
    else:
        table[a] = {a, b}
        table[b] = table[a]
        groups.append(table[a])
print(max([len(g) for g in groups]))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a, b = [], []
for i in range(m):
    _a, _b = map(int, input().split())
    a.append(_a)
    b.append(_b)

group, lst = {}, {}
cnt = 1
for i in range(m):
    group_a, group_b = None, None
    if a[i] in lst:
        group_a = lst[a[i]]
    if b[i] in lst:
        group_b = lst[b[i]]
    if group_a is not None and group_b is not None and group_a != group_b:
        for _b in group[group_b]:
            lst[_b] = group_a
        group[group_a] += group[group_b]
        del group[group_b]
    elif group_a is not None and group_b is not None and group_a == group_b:
        continue
    elif group_a is not None and group_b is None:
        lst[b[i]] = group_a
        group[group_a].append(b[i])
    elif group_a is None and group_b is not None:
        lst[a[i]] = group_b
        group[group_b].append(a[i])
    else:
        group_name = f'g_{cnt}' 
        lst[a[i]], lst[b[i]] = group_name, group_name
        group[group_name] = [a[i], b[i]]
        cnt += 1
print(max([len(s[1]) for s in group.items()]))

Submission status: Runtime Error

Solution code:
# Python3 program to print DFS traversal
# from a given given graph
from collections import defaultdict

# This class represents a directed graph using
# adjacency list representation


class Graph:

    # Constructor
    def __init__(self):
        self.zrr=[]

        # default dictionary to store graph
        self.graph = defaultdict(list)

    # function to add an edge to graph
    def addEdge(self, u, v):
        self.graph[u].append(v)

    # A function used by DFS
    def DFSUtil(self, v, visited):
        zrr=self.zrr

        # Mark the current node as visited
        # and print it
        visited[v] = True
        # print(v, end=' ')
        if v!=None:
            zrr.append(v) 
            # print(v)

        # Recur for all the vertices
        # adjacent to this vertex
        for i in self.graph[v]:
            if visited[i] == False:
                self.DFSUtil(i, visited)

    # The function to do DFS traversal. It uses
    # recursive DFSUtil()
    def DFS(self, v):

        # Mark all the vertices as not visited
        visited = [False] * (max(self.graph)+1)

        # Call the recursive helper function
        # to print DFS traversal
        self.DFSUtil(v, visited)

# Driver code


# Create a graph given
# in the above diagram
g = Graph()


# This code is contributed by Neelam Yadav
n, m = map(int, input().split())


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

# maxi = -1
# for i in range(n):
#     if maxi < (len((g.DFS(i)))):
#         maxi = len(g.DFS(i))
# print(maxi+1)

# print(g.zrr)
maxi=-1
for i in range(n):
    g.DFS(i)
    # print(g.zrr)
    if len(g.zrr)>maxi:
        maxi=len(g.zrr)
    g.zrr=[]
print(maxi+1)

Submission status: Runtime Error

Solution code:
n,m = map(int, input().split())
if m == 0:
  print(1)
  exit()
g = [[] for i in range(n)]
for i in range(m):
  a, b = map(int, input().split())
  g[a-1].append(b-1)
  g[b-1].append(a-1)
v = [-1 for i in range(n)]
ans = [0]*n
def dfs(x,y):
  for i in g[x]:
    if v[i] == -1:
      v[i]=1
      ans[y]+=1
      dfs(i,y)
for i in range(n):
  if v[i]!=-1:
    continue
  v[i]=0
  dfs(i,i)
print(max(ans)+1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

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

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([])
def dfs(target):
    if target not in adj_list:
        return 0
    elif target in visited:
        return 0
    visited.add(target)
    node_count = 1

    for neighbor in adj_list[target]:
        node_count += dfs(neighbor)
    return node_count
count = 1

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

Submission status: Runtime Error

Solution code:
def solve():
    n, m = map(int, input().split())
    arr = [[0 for _ in range(5)] for _ in range(5)]
    for _ in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        arr[a][b] = 1
        arr[b][a] = 1

    ans = max([arr[i].count(1)+1 for i in range(n)])
    print(ans)


def main():
    t = 1
    while t > 0:
        solve()
        t -= 1


main()

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
l=[]
for i in range(n):
    l.append(-1)
for j in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    if l[a]!=-1 and l[b]!=-1:
        e=l[b]
        for o in range(l.count(e)):
            l[l.index(e)]=l[a]
    elif l[a]==-1 and l[b]==-1:
        l[a]=1+max(l)
        l[b]=max(l)
    elif l[a]!=-1:
        l[b]=l[a]
    elif l[b]!=-1:
        l[a]=l[b]
c=[]
for k in range(1+max(l)):
    c.append(l.count(k))
print(max(c))

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

readline = sys.stdin.readline
read = sys.stdin.read
n, m = map(int, readline().split())
if m == 0:
    print(1)
    sys.exit()
d = np.zeros(n+1,dtype=np.int64)
for i in range(m):
    a, b = map(int, readline().split())
    if d[a] == 0:
        if d[b] == 0:
            d[b] == a
        else:
            x = d[b]
            d[a] = x
            d = np.where(d==a,x,d)
    else:
        if d[b] == 0:
            x = d[a]
            d[b] = x
            d = np.where(d==b,x,d)
        else:
            x = d[a]
            y = d[b]
            d[x] = y
            d = np.where(d==x,y,d)
u, c = np.unique(d, return_counts=True)
ans = np.max(c[1::]) + 1
print(ans)

Submission status: Runtime Error

Solution code:
def solve():
    n, m = map(int, input().split())
    group = []
    done = [-1]*n
    num = 0
    for i in range(m):
        a, b = map(lambda x:int(x)-1, input().split())
        if done[a] != -1:
            if done[b] == -1:
                group[done[a]].append(b)
                done[b] = done[a]
        else:
            if done[b] == -1:
                group.append([a,b])
                done[a], done[b] = num, num
                num += 1
            else:
                group[done[b]].append(a)
                done[a] = done[b]
    people = [0]+[len(i) for i in group]
    ans = max(people)
    amari = done.count(-1)
    if amari >= sum(people):
        print(ans+(sum(people-amari)))
    else:
        print(ans)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
# [] = list(map(int, input().split()))

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

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

countMax = {}
for x in qf.id:
    if x in countMax:
        countMax[x] += 1
    else:
        countMax[x] = 0


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:
n,m=map(int,input().split())
# Union-Find
a=list(range(n))
def find(x):
  if a[x]==x:
    return x
  a[x] = find(a[x])
  return a[x]

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

for _ in range(m):
  x,y=map(lambda x:int(x)-1,input().split())
  union(x, y)

count=[0]*n
for i in range(n):
  count[find(i)] += 1
print(max(count))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

#bisect.bisect_left(list,key)はlistのなかでkey未満の数字がいくつあるかを返す
#つまりlist[i] < x となる i の個数
#bisect.bisect_right(list, key)はlistのなかでkey以下の数字がいくつあるかを返す
#つまりlist[i] <= x となる i の個数
#これを応用することで
#len(list) - bisect.bisect_left(list,key)はlistのなかでkey以上の数字がいくつあるかを返す
#len(list) - bisect.bisect_right(list,key)はlistのなかでkeyより大きい数字がいくつあるかを返す
#これらを使うときはあらかじめlistをソートしておくこと！
n,m = MI()
li = [0 for _ in range(n+1)]
k = 0
for j in range(m):
    a,b = MI()
    if li[a] == 0 and li[b] == 0:
        k += 1
        li[a] = k
        li[b] = k
    elif li[a] == 0 and li[b] != 0:
        li[a] = li[b]
    elif li[b] == 0 and li[a] != 0:
        li[b] = li[a]
    else:
        continue
c = Counter(li)
del c[0]
print(max(c.values()))

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)])
    
    elif g1 == g2:
        continue

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 sys
input = sys.stdin.readline

N, M = map(int, input().split())
nums = [0] * N
friends = []
for _ in range(N):
    friends.append(set())

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

gnum = 0
groupn = 0
nmax = 0

def find_route(i):
    global gnum
    global nums
    global friends
    global groupn
    global nmax
    if len(friends[i]) == 0:
        return
    if nums[i] == 0:
        gnum += 1
        if groupn > nmax:
            nmax = groupn
        groupn = 1
        nums[i] = gnum
    for f in friends[i]:
        if nums[f] == 0:
            nums[f] = gnum
            groupn += 1
            find_route(f)

for i in range(N):
    find_route(i)

print(max(nmax, 1))

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

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

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([])
def dfs(target):
    if target in visited:
        return 0
    visited.add(target)
    node_count = 1
    for neighbor in adj_list[target]:
        node_count += dfs(neighbor)
    return node_count
count = 1

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

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
group = [1]*N
for i in range(M):
    if AB[i][0] > AB[i][1]:
        tmp = AB[i][0]
        AB[i][0] = AB[i][1]
        AB[i][1] = tmp
AB.sort()
before0 = AB[0][0]
before1 = AB[0][1]
for i in range(M):
    if i != 0:
        if before0 == AB[i][0] and before1 == AB[i][1]:
            continue
        group[AB[i][0]-1] += 1
        group[AB[i][1]-1] += 1
print(max(group))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
F = []
for _ in range(M):
    A, B = map(int, input().split())
    if len(F) == 0:
        F.append([A, B])
    isExist = False
    for f in F:
        if A in f or B in f:
            f.append(A)
            f.append(B)
            isExist = True
    if not isExist:
        F.append([A, B])
if len(F) == 0:
    print(1)
else:
    ans = 1
    for f in F:
    ans = max(ans, len(list(set(f))))
    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)

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

Submission status: Runtime Error

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

friends = [0]*n
group = [-1]*n

for a, b in ab:
    if a > b:
        a, b = b, a
    a -= 1
    b -= 1
    if group[a] == -1 and group[b] == -1:
        group[a] = a
        group[b] = b
        friends[a] += 2
    elif group[a] != -1 and group[b] != -1:
        group[b] = group[a]
        friends[group[a]] += friends[group[b]]
    elif group[a] == -1:
        group[a] = group[b]
        friends[group[b]] += 1
    elif group[b] == -1:
        group[b] = group[a]
        friends[group[a]] += 1

print(max(friends))

Submission status: Runtime Error

Solution code:
n,m=map(int, input().split())
l=[set()]*(n+1)
c=set()
e=[]
for i in range(m):
  
  a,b=map(int, input().split())
  a,b=min(a,b),max(a,b)
  d={(a,b)}
  if not d <= c:#チェック機能
    c.add((a,b))
    e.append({a,b})

l[0]=l[0]|e[0]
for i in range(len(e)):
  ok=True
  j=0
  while ok:
    if e[i] & l[j] != set():
      l[j]=l[j]|e[i]
      ok=False
    elif l[j]==set():
      l[j]=e[i]
      ok=False
    j+=1

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

Submission status: Runtime Error

Solution code:
import itertools
import collections
n,m = map(int,input().split())
ab = [sorted(list(map(int,input().split()))) for i in range(m)]
ab = list(map(list, set(map(tuple, ab))))
friend = []
# print(ab)
flat = list(itertools.chain.from_iterable(ab))
# print(flat)
c = collections.Counter(flat)
print(c.most_common()[0][1]+1)

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix
import numpy as np
n, m = map(int,input().split())
A=[]
B=[]
conne = [[0]*n for _ in range(n)]
visited = [0]*n

for i in range(m):
    a,b=map(int,input().split())
    A.append(a)
    B.append(b)
    conne[a-1][b-1]=1
    conne[b-1][a-1]=1

n, labels = connected_components(conne)
ans=0
for i in range(n):
    
    an = np.sum(labels==i)
    ans = max(ans,an)

print(ans)

Submission status: Runtime Error

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

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

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


def dfs(x:int, marked:set):
    a = 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
marked = set()
for i in range(1,N+1):
    if i not in marked:
        a, addmark = dfs(i, set())
        marked = marked.union(addmark)
        #print(a,marked)
        if (length:=len(a) > res):
            res = length
print(res)

Submission status: Runtime Error

Solution code:
from collections import Counter
n,m=map(int, input().split())
ans=1
l=[]
x=[-1]*n
for i in range(m):
    a,b=map(int, input().split())
    a-=1
    b-=1
    if x[a]+x[b]==-2:
        l.append(2)
        x[a]=len(l)-1
        x[b]=len(l)-1
    elif x[a]==x[b]:
        continue
    elif x[a]!=-1:
        l[x[b]]+=1
        x[a]=x[b]
    elif x[b]!=-1:
        l[x[a]]+=1
        x[b]=x[a]
    else:
        l[x[a]]+=l[x[b]]
        l[x[b]]=0
        for i in range(n):
            if x[i]==x[b]:
                x[i]=x[a]
print(max(l))

Submission status: Runtime Error

Solution code:
N, M = [int(a) for a in input().split()]
lol = []
for i in range(M):
  a, b = [int(a) for a in input().split()]
  found_a = -10
  found_b = -10
  for j in range(len(lol)):
    if a in lol[j]:
      found_a = j
    if b in lol[j]:
      found_b = j
    if found_a >= 0 and found_b >= 0:
      break
  
  if found_a < 0 and found_b < 0:
    lol.append([a,b])
  elif found_a >= 0 and found_b < 0:
    lol[found_a].append(b)
  elif found_b >= 0 and found_a < 0:
    lol[found_b].append(a)
    
ans = max([len(z) for z in lol])

print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
if M == 0:
    print(1)
else:
    D = {}
    count = 0
    friends = []
    while count < M:
        A, B = map(int,input().split())
        if A not in D and B not in D:
            friends += [[A,B]]
            D[A] = len(friends) -1
            D[B] = len(friends) - 1
        elif A in D and B not in D:
            friends[D[A]] += [B]
            D[B] = D[A]
        elif B in D and A not in D:
            friends[D[B]] += [A]
            D[A] = D[B]
        count += 1

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

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(int(B))
    elif groups[B] != 0:
        groups[A] = groups[B]
        group_num_list[groups[B]].append(int(A))
    else:
        groups[A] = group_num
        groups[B] = group_num
        group_num_list.append([int(A), int(B)])
        group_num += 1
counter = Counter(groups)
# print(collection)
# print(group_num_list)
if len(groups) == 1:
    print(1)
elif int(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 functools

N = int(input())
A = [int(_) for _ in input().split()]
p = set([])

y = functools.reduce(math.gcd, A)
pairwise = True

for a in A:
    if a == 1:
        continue
    if pairwise is False:
        break
    for k in range(2, int(math.sqrt(a)) + 2):
        if a % k == 0:
            if k in p:
                pairwise = False
                break
            p.add(k)
            while a % k == 0:
                a //= k
    if pairwise and a > 1:
        p.add(a)

if pairwise:
    print("pairwise coprime")
elif y == 1:
    print("setwize coprime")
else:
    print("not coprime")

Submission status: Runtime Error

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

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

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

print(max_gr_len)

Submission status: Runtime Error

Solution code:
from collections import Counter
def resolve():
    N, connections = map(int, input().split())
    
    connection_set = set([tuple(map(int, input().split())) for _ in range(connections)])
    group_list = [0]*N
    group_num = 1
    for connection in connection_set:
        x0 = connection[0]-1
        x1 = connection[1]-1
        if group_list[x0] != 0:
            if group_list[x1] == 0:
                group_list[x1] = group_list[x0]
        else:
            if group_list[x1] == 0:
                group_list[x0] = group_num
                group_list[x1] = group_num
                group_num += 1
            else:
                group_list[x0] = group_list[x1]

    c = Counter(group_list)
    d = c.most_common()

    if d[0][0] == 0:
        print(d[1][1])
    else:
        print(d[0][1]) 
resolve()

Submission status: Runtime Error

Solution code:
N, M = list(map(int, input().split()))
G = [[0] * N for i in range(N)]

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

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

    G[a - 1][b - 1] = 1
    G[b - 1][a - 1] = 1


friend_chain = []
checked = [False]*N

for i in range(N):

    if (checked[i] == True):
        for a, chain_i in enumerate(friend_chain):

            for b, friend in enumerate(chain_i):

                if (i == friend):
                    for k in range(N):
                        if (G[i][k] == 1 and checked[k] == False):
                            friend_chain[a].append(k)
                            checked[k] = True

    else:
        checked[i] = True
        friend_chain_i = [i]

        for j in range(N):
            if (G[i][j] == 1 and checked[j] == False):
                friend_chain_i.append(j)
                checked[j] = True

        friend_chain.append(friend_chain_i)

    if (False not in checked):
        break


max_num = 0
for i in range(len(friend_chain)):
    if (len(friend_chain[i]) > max_num):
        max_num = len(friend_chain[i])

print(max_num)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
f = [set() for _ in range(N)]
v = [False for _ in range(N)]
ans = 1

for _ in range(M):
  a, b = map(int, input().split())
  a, b = a - 1, b - 1
  f[a].add(b)
  f[b].add(a)
  
  
def dfs(fi):
  if v[fi]: return 0
  
  v[fi] = True
  cnt = 1
  
  for fr in f[fi]:
    cnt += dfs(fr)
    
  return cnt

for i in range(N):
  cnt = dfs(i)
  ans = max(ans, cnt)
  
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int,input().split())
communities = [0 for i in range(N)]
same = []
num = 1
for i in range(M):
  A, B = map(int,input().split())
  if communities[A-1] == 0 and communities[B-1] == 0:
    communities[A-1] = num
    communities[B-1] = num
    num += 1
  elif communities[A-1] == 0:
    communities[A-1] = communities[B-1]
  elif communities[B-1] == 0:
    communities[B-1] = communities[A-1]
  elif communities[A-1] != communities[B-1]:
    same.append(min(communities[A-1],communities[B-1]))
    same.append(max(communities[A-1],communities[B-1]))
  else:
    continue

communities.sort()
members = [0 for i in range(communities[-1])]
for i in range(N):
  if communities[i] == 0:
    continue
  else:
    members[communities[i]-1] += 1
for i in range(len(same)//2):
  members[same[2*i]-1] += members[same[2*i+1]-1]
print(max(members))

Submission status: Runtime Error

Solution code:
#D
N,M = map(int, input().split())
L = []
for i in range(N):
    L.append([])
maxim = 0
for i in range(M):
    A,B = map(int, input().split())
    for j in L[:maxim+1]:
        #print(L[:maxim+1])
        if A in j and B in j:
            break
        elif A in j:
            j.append(B)
            break
        elif B in j:
            j.append(A)
            break
        else:
            L[maxim] += [A, B]
            maxim += 1
            break
    #print(L)
result = 0
for j in L:
    if len(j)>result:
        result = len(j)
print(result)

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)


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