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())
a = [] * m
b = [] * m
for i in range(m):
    aa, bb = input().split()
    a.append(aa)
    b.append(bb)
ans = n
f1 = []
f1.append(a[0])
for i in range(m):
    if a[i] in f1:
        f1.append(b[i])
    elif b[i] in f1:
        f1.append(a[i])
rans = len(f1)
if rans < ans:
    ans = rans
j = 1
while j < m:
    f2 = []
    if a[j] in f1 or b[j] in f1:
        j += 1
        continue
    print(j,m)
    if j < m:
      f2.append(a[j])
      f1.append(a[j])
      for k in range(j, m):
        if a[k] in f2:
          f2.append(b[k])
          f1.append(b[k])
        elif b[k] in f2:
          f2.append(a[k])
          f1.append(a[k])
      rans = len(f2)
      if rans > ans:
        ans = rans
    j += 1
print (ans)

Submission status: Runtime Error

Solution code:
import numpy as np

class union_find:
    def __init__(self,N):
        self.r = np.ones(N)*-1
    
    def root(self,x):
        if self.r[x]<0:
            return int(x)
        else:
            self.r[x] = self.root(int(self.r[x]))
            return int(self.r[x])
        
    def unite(self,x,y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        else:
            self.r[x] += self.r[y]
            self.r[y] = int(x)
            return True
        
    def size(self,x):
        return -self.r[self.root(x)]


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

Union = union_find(N)
for i in range(M):
    x,y = [int(i) for i in input().split()]
    Union.unite(x-1,y-1)

Y = 0
for i in range(N):
    Y = max(Y,Union.size(i))
print(int(Y))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
friends_set_list = [set(i) for i in range(N+1)]
ans = 1
for i in range(M):
    A, B = map(int, input().split())
    friends_set_list[B].add(A)
    friends_set_list[A] |= friends_set_list[B]
    friends_set_list[B] = friends_set_list[A]
    num = len(friends_set_list[A])
    if ans < num:
        ans = num

print(ans)

Submission status: Runtime Error

Solution code:
def search(x, num):
    nodes.remove(x)
    search_list = []
    for y in list(edge[x]):
        if y in nodes:
            edge[y].discard(x)
            num = search(y, num)
    return num + 1


(n,m),*d  = [list(map(int, s.split())) for s in open(0)]

edge = [set() for _ in range(n+1)]
for x in d:
    edge[x[0]].add(x[1])
    edge[x[1]].add(x[0])

nodes = set(range(1,n+1))
ans = 1
for x in list(nodes):
    if x not in nodes:
        continue
    tmp = search(x, 0)
    ans = max(tmp, ans)
print(ans)

Submission status: Runtime Error

Solution code:
def search(x, num):
    nodes.remove(x)
    search_list = []
    for y in list(edge[x]):
        edge[y].discard(x)
        if y in nodes:
            num = search(y, num)
    return num + 1


(n,m),*d  = [list(map(int, s.split())) for s in open(0)]

edge = [set() for _ in range(n+1)]
for x in d:
    edge[x[0]].add(x[1])
    edge[x[1]].add(x[0])

nodes = set(range(1,n+1))
ans = 1
for x in list(nodes):
    if x not in nodes:
        continue
    tmp = search(x, 0)
    ans = max(tmp, ans)
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
count = 0
def dfs_main(adj,visited,src):
    visited[src] = True
    global count
    count+=1
    for negh in adj[src]:
        if not visited[negh]:
            dfs_main(adj,visited,negh)
def dfs(n,adj):
    visited = defaultdict(lambda: False)
    global count
    mx = -1
    for src in adj:
        if not visited[src]:
            dfs_main(adj,visited,src)
            mx = max(mx,count)
        count = 0
    return(mx)
n,e = map(int,input().split())
adj = defaultdict(list)
for _ in range(e):
    u,v = map(int,input().split())
    adj[u].append(v)
    adj[v].append(u)
print(dfs(n,adj))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
friends_set_list = [set() for i in range(N+1)]
ans = 1
for i in range(M):
    A, B = map(int, input().split())
    friends_set_list[B].add([A,B])
    friends_set_list[A] |= friends_set_list[B]
    friends_set_list[B] = friends_set_list[A]
    num = len(friends_set_list[A])
    if ans < num:
        ans = num

print(ans)

Submission status: Runtime Error

Solution code:
def search(x, num):
    nodes.remove(x)
    search_list = []
    for y in list(edge[x]):
        edge[y].remove(x)
        if y in nodes:
            num = search(y, num)
    return num + 1


(n,m),*d  = [list(map(int, s.split())) for s in open(0)]

edge = [set() for _ in range(n+1)]
for x in d:
    edge[x[0]].add(x[1])
    edge[x[1]].add(x[0])

nodes = set(range(1,n+1))
ans = 1
for x in list(nodes):
    if x not in nodes:
        continue
    tmp = search(x, 0)
    ans = max(tmp, ans)
print(ans)

Submission status: Runtime Error

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

root = [-1]*n

def r(x):
    if root[x] < 0 :
        return x
    else:
        root[x] = r(root[x])
        return root[x]

def unite(x, y):
    x = r(x)
    y = r(y)
    if x == y:
        return
    root[x] += root[y]
    root[y] = x

def size(x):
    x = r(x)
    return - root[x]

for i in range(m):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    unite(x,y)

max_size = max(map(size,range(n)))

print(max_size)

Submission status: Runtime Error

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

pg = {n: -1 for n in range(1, N + 1)}  # person's group
gpc = []  # group person count
gc = 0  # group count

for _ in range(M):
	Ai, Bj = map(int, input().strip().split())

	if pg[Ai] < 0 and pg[Bj] < 0:
		pg[Ai] = gc
		pg[Bj] = gc
		gpc.append(2)
		gc += 1

	if pg[Ai] < 0:
		pg[Ai] = pg[Bj]
		gpc[pg[Ai]] += 1

	if pg[Bj] < 0:
		pg[Bj] = pg[Ai]
		gpc[pg[Bj]] += 1

print(max(gpc))

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)



#始める点xとすでに探索した点の集合mark
# => xと友達な点の集合、探索した点
def dfs(x:int, mark:set):
    if x in mark:
        return , mark
    marked = mark
    a = {x}
    a = a.union(dic[x])
    marked.add(x)
    for i in dic[x]:
        if i not in marked:
            b, addmarked = dfs(i, marked)
            a = a.union(b)
            marked = marked.union(addmarked)
    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 len(a) > res:
            res = len(a)
print(res)

Submission status: Runtime Error

Solution code:
import numpy as np

class union_find:
    def __init__(self,N):
        self.r = np.ones(N)*-1
    
    def root(self,x):
        if self.r[x]<0:
            return int(x)
        else:
            self.r[x] = self.root(int(self.r[x]))
            return int(self.r[x])
        
    def unite(self,x,y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        else:
            self.r[x] += self.r[y]
            self.r[y] = int(x)
            return True
        
    def size(self,x):
        return -self.r[self.root(x)]


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

Union = union_find(N)
for i in range(M):
    x,y = [int(i) for i in input().split()]
    Union.unite(x,y)

Y = 0
for i in range(N):
    Y = max(Y,Union.size(i))
print(int(Y))

Submission status: Runtime Error

Solution code:
from collections import defaultdict
count = 0
def dfs_main(adj,visited,src):
    visited[src] = True
    global count
    count+=1
    for negh in adj[src]:
        if not visited[negh]:
            dfs_main(adj,visited,negh)
def dfs(n,adj):
    visited = defaultdict(lambda: False)
    global count
    mx = -1
    for src in adj:
        if not visited[src]:
            dfs_main(adj,visited,src)
            mx = max(mx,count)
        count = 0
    return(mx)
n,e = map(int,input().split())
adj = defaultdict(set)
for _ in range(e):
    u,v = map(int,input().split())
    adj[u].add(v)
    adj[v].add(u)
print(dfs(n,adj))

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
ans = [set() for i in range(N)]
a,b = map(int,input().split())
ans[0].add(a)
ans[0].add(b)

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

    for j in ans:
        if len(j) == 0:
            j.add(a)
            j.add(b) 
            break            
        if a in j or b in j:
            j.add(a)
            j.add(b) 
            break



print(len(max(ans)))

Submission status: Runtime Error

Solution code:
#coding: utf-8
from collections import defaultdict

N, M = [int(x) for x in input().split()]

G = defaultdict(set)
for i in range(M):
    a, b = [int(x) - 1 for x in input().split()]
    G[a].add(b)
    G[b].add(a)

grp = [-1] * N

def dfs(node, color):
    if grp[node] != -1:
        return 
    grp[node] = color
    for n in G[node]:
        if grp[n] == -1:
            dfs(n, color)

for i in range(N):
    dfs(i, i)

n = defaultdict(int)
for i in range(N):
    n[grp[i]] += 1

ret = 0
for r in n:
    ret = max(ret, n[r])
print(ret)

Submission status: Runtime Error

Solution code:
def search(x, num):
    nodes.remove(x)
    search_list = []
    for y in edge[x]:
        edge[y].remove(x)
        search_list.append(y)
    for y in search_list:
        if y in nodes:
            num = search(y, num)
    return num + 1


(n,m),*d  = [list(map(int, s.split())) for s in open(0)]

edge = [set() for _ in range(n+1)]
for x in d:
    edge[x[0]].add(x[1])
    edge[x[1]].add(x[0])

nodes = set(range(1,n+1))
ans = 1
for x in range(1,n+1):
    if x not in nodes:
        continue
    tmp = search(x, 0)
    ans = max(tmp, ans)
print(ans)

Submission status: Runtime Error

Solution code:
import random
import sys

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)}
ans = list(g_mem.values())
for now in range(1, g_num+1):
    if g_reached[now] == 0:
        g_reached[now] = 1
        if edge.get(now):
            count = g_mem[now]
            queue = set(edge[now])
            while len(queue) > 0:
                next_now = queue.pop()
                if g_reached[next_now] == 0:
                    g_reached[next_now] = 1
                    count += g_mem[next_now]
                    queue |= edge[next_now]
                queue -= {now}
                now = next_now
            ans.append(count)


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

Submission status: Runtime Error

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
def main():
    N,M = map(int,input().split())
    A = [0 for i in range(M)]
    B = [0 for i in range(M)]
    for i in range(M):
        A[i],B[i] = map(int,input().split())
        
    uf = UnionFind(N)
    for i in range(M):
        a,b = A[i]-1,B[i]-1
        uf.union(a, b)
        
    ans = 0
    for i in range(M):
        ans = max(ans,uf.size(i))
        
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
using namespace std;

int getID(vector<int>& v,int idx){
  if(v[idx]==idx)return idx;
  v[idx]=getID(v,v[idx]);
  return v[idx];
}

int main(){
  int N,M;
  cin>>N>>M;
  vector<int> d(N,0);
  vector<int> v(N,-1);
  for(int i=0;i<M;i++){
    int s[2];
    cin>>s[0]>>s[1];
    s[0]--;
    s[1]--;
    
    if(v[s[0]]==-1 && v[s[1]]==-1){
      v[s[0]]=s[0];
      v[s[1]]=s[0];
      d[s[0]]=2;
    }
    else if(v[s[0]]==-1 || v[s[1]]==-1){
      for(int j=0;j<2;j++){
        if(v[s[j]]==-1){
          int id=getID(v,s[(j+1)%2]);
          v[s[j]]=id;
          d[id]++;
        }
      }
    }
    else{
      int r1=getID(v,s[0]);
      int r2=getID(v,s[1]);
      if(r1==r2)continue;
      v[r1]=r2;
      d[r2]+=d[r1];
      d[r1]=0;
    }
    
  }
  int ans=1;
  for(int i=0;i<N;i++){
    ans=max(ans,d[i]);
  }
  cout<<ans<<endl;
}

Submission status: Runtime Error

Solution code:
from collections import Counter

N,M = map(int,input().split())
num = [i for i in range(N+1)]
ab = [list(map(int,input().split())) for _ in range(M)]

ab.sort()

for a,b in ab:
    m = min(num[a],num[b])
    num[a] = num[b] = m

print(max(Coutner(num).values()))

Submission status: Runtime Error

Solution code:
import sys

def main(lines):
  n = int(lines[0].split()[0])
  m = int(lines[0].split()[1])
  friend = [0]*n
  group = 1
  
  for i in range(m):
    g1 = int(lines[i+1].split()[0])
    g2 = int(lines[i+1].split()[1])
    if friend[g1] != 0:
      if friend[g2] !=0:
        if friend[g1] != friend[g2]:
          
      else:
        friend[g2] = friend[g1]
    elif friend[g2] != 0:
      friend[g1] = friend[g2]
    else:
      friend[g1] = group
      friend[g2] = group
      group += 1
  for i in range(n):
    
  
if __name__ == '__main__':
  lines=[]
  for l in sys.stdin:
    lines.append(l.strip('\r\n'))
  main(lines)

Submission status: Runtime Error

Solution code:
import numpy as np
N,M=map(int,input().split())
mat=np.zeros((N,N))
for _ in range(M):
    a,b=map(int,input().split())
    mat[a-1][b-1]=1
    mat[b-1][a-1]=1
mat2=[[j for j in i] for i in mat]
for i in range(N-1):
    for j in range(i+1,N):
        for k in range(j+1,N):
            if (mat[i][j]==1)&(mat[i][k]==1):
                mat[j][k]=1
                mat[k][j]=1
print(str(int(np.max(np.sum(mat,axis=1))+1)))

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

Submission status: Runtime Error

Solution code:
data = input().split(" ")
N = int(data[0])
M = int(data[1])

Comb = [0]*M
List = []
for i in range(M):
  buf = input().split(" ")
  buf[0] = int(buf[0])
  buf[1] = int(buf[1])
  List.extend(buf)
  Comb[i] = buf
List = list(set(List))
#print(Comb,List)

for i in range(len(List)):
  buf = []
  num = len(Comb)
  for j in range(num):
    if List[i] in Comb[j]:
      buf.extend(Comb[j])
      Comb[j] = None
  buf = list(set(buf))
  Comb.append(buf)
  Comb = [i for i in Comb if i != None]
#  print(Comb)

for i in range(len(Comb)):
  Comb[i] = len(Comb[i])
print(max(Comb))

Submission status: Runtime Error

Solution code:
from collections import defaultdict


def main():
    n, m = map(int, input().split())
    friend_group = defaultdict(set)
    for _ in range(m):
        a, b = map(int, input().split())

        for friend in friend_group[b] - friend_group[a] - {a}:
            friend_group[friend].add(a)
            friend_group[a].add(friend)

        for friend in friend_group[a] - friend_group[b] - {b}:
            friend_group[friend].add(b)
            friend_group[b].add(friend)

        friend_group[a].add(b)
        friend_group[b].add(a)
    # print(friend_group)
    print(max([len(friend_group[key]) for key in friend_group]) + 1)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

n,m = map(int, input().split())
uf = UnionFind(n)
for i in range(m):
  a,b = map(int, input().split())
  uf.union(a, b)

ans = 0
for i in list(uf.all_group_members().values()):
  ans = max(len(i),ans)
  
print(ans)

Submission status: Runtime Error

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

a, b = list(map(int, input().split()))
s = set()
s.add(a)
s.add(b)
sets.append(s)
for i in range(1, m):
    a, b = list(map(int, input().split()))
    f = True
    for si in range(len(sets)):
        if a in sets[si] or b in sets[si]:
            sets[si].add(a)
            sets[si].add(b)
            f = False
            break
    if f:
        s = set()
        s.add(a)
        s.add(b)
        sets.append(s)

slen = sorted([len(s) for s in sets])
ans = 0
for l in slen:
    ans += (l - ans)
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import copy
N,M=map(int,input().split())
mat=np.zeros((N,N))
for _ in range(M):
    a,b=map(int,input().split())
    mat[a-1][b-1]=1
    mat[b-1][a-1]=1
mat2=[[j for j in i] for i in mat]
for i in range(N-1):
    for j in range(i+1,N):
        for k in range(j+1,N):
            if (mat[i][j]==1)&(mat[i][k]==1):
                mat[j][k]=1
                mat[k][j]=1
print(str(int(np.max(np.sum(mat,axis=1))+1)))

Submission status: Runtime Error

Solution code:
from collections import defaultdict
mx = -10**18
def dfs_main(adj,visited,src,temp):
    visited[src] = True
    temp.append(src)
    for negh in adj[src]:
        if not visited[negh]:
            dfs_main(adj,visited,negh,temp)
    return len(temp)
def dfs(n,adj):
    visited = {}
    for key in adj:
        visited[key] = False
    count = 0
    global mx
    for ver in adj:
        if not visited[ver]:
            temp = []
            mx = max(mx,dfs_main(adj,visited,ver,temp))
n,e = map(int,input().split())
adj = defaultdict(set)
for _ in range(e):
    u,v = map(int,input().split())
    adj[u].add(v)
    adj[v].add(u)
dfs(n,adj)
print(mx)

Submission status: Runtime Error

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

n,m=map(int,input().split())
p = [tuple(sorted(list(map(int,input().split())))) for ii in range(m)]
p=set(p)

m=len(p)

g=[-1]*(n+1)
r=0

p2=list()

rr=list()

import numpy as np
for pii in p:
  if g[pii[0]]<0 and g[pii[1]]<0:
    g[pii[0]]=r
    g[pii[1]]=r
    rr.append(2)
    r+=1
  elif g[pii[0]]>=0 and g[pii[1]]>=0:
    g0=g[pii[0]]
    g1=g[pii[1]]
    if g0!=g1:
      p2.append((g0,g1))
  elif g[pii[0]]>=0:
    g[pii[1]]=g[pii[0]]
    rr[g[pii[0]]]+=1
  elif g[pii[1]]>=0:
    g[pii[0]]=g[pii[1]]
    rr[g[pii[1]]]+=1

#print(rr)
#print(g)
for p2ii in p2:
  g0=p2ii[0]
  g1=p2ii[1]
  rr[g1]+=rr[g0]
  rr[g0]=0
  #print(g0,g1,rr)
#print(p2)
#print(rr)
print(max(rr))

Submission status: Runtime Error

Solution code:
n,m=input().split()
ab = [map(int, input().split()) for _ in range(m)]
a, b = [list(i) for i in zip(*xy)]
friendnum = [0]*n
for i in range(n):
    for k in range(m):
        if a[k] == i:
            friendnum[i].append(b[i])
        if b[k] == i:
            friendnum[i].append(a[i])
ans = max(ans,len(frindnum[i]))
print(ans)

Submission status: Runtime Error

Solution code:
def search(x, num):
    search_list = []
    for y in edge[x]:
        if y in nodes:
            nodes.remove(y)
            edge[y].discard(x)
            search_list.append(y)
    for y in search_list:
        num = search(y, num)
    return num + 1


(n,m),*d  = [list(map(int, s.split())) for s in open(0)]

edge = [set() for _ in range(n+1)]
for x in d:
    edge[x[0]].add(x[1])
    edge[x[1]].add(x[0])

nodes = set(range(1,n+1))
ans = 1
for x in range(1,n+1):
    if x not in nodes:
        continue
    tmp = search(x, 0)
    ans = max(tmp, ans)
print(ans)

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import connected_components
import numpy as np
#import sys

#imput = sys.stdin.readline
n, m = map(int,input().split())

conne = np.zeros((n,n))

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

    conne[a-1][b-1]=1
    conne[b-1][a-1]=1

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

print(ans)

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]

for _ in range(m):
  x,y=map(int,input().split())
  x,y=find(x-1),find(y-1)
  if x == y: continue
  a[y]=x

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

Submission status: Runtime Error

Solution code:
import queue
from scipy.sparse.csgraph import connected_components
import numpy as np
import sys

#imput = sys.stdin.readline
n, m = map(int,input().split())

conne = np.zeros((n,n))
visited = [0]*n

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

    conne[a-1][b-1]=1
    conne[b-1][a-1]=1

m, labels = connected_components(conne)
ans=0

Submission status: Runtime Error

Solution code:
N,M,*A=map(int,open(0).read().split())
d={}
ss=[]
for i in range(0,len(A),2):
    a=A[i]
    b=A[i+1]
    if a in d:
        d[a].add(b)
    elif b in d:
        d[b].add(a)
    else:
        s=set([a,b])
        ss.append(s)
        d[a]=d[b]=s
print(max([len(s) for s in ss]))

Submission status: Runtime Error

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

a, b = list(map(int, input().split()))
s = set()
s.add(a)
s.add(b)
sets.append(s)
for i in range(1, m):
    a, b = list(map(int, input().split()))
    f = True
    for si in range(len(sets)):
        if a in sets[si] or b in sets[si]:
            sets[si].add(a)
            sets[si].add(b)
            f = False
            break
    if f:
        s = set()
        s.add(a)
        s.add(b)
        sets.append(s)

slen = sorted([len(s) for s in sets])
ans = 0
for l in slen:
    ans += (l - ans)
print(ans)

Submission status: Runtime Error

Solution code:
a,b = list(map(int, input().split()))
friend_li = [[] for _ in range(a)]

result = 0
array = []

def append_child(array,li):
  array += li
  for i in range(len(li)):
    append_child(array,friend_li[li[i]])

for i in range(b):
  c,d = list(map(int, input().split()))
  friend_li[min(c-1,d-1)].append(max(c-1,d-1))

for element in friend_li:
  append_child(array,element)
  li = list(set(array))
  len_ = len(li)
  for i in range(len_):
    del friend_li[li[i]]
  if len_ > result:
    result = len_
  array = []
print(result+1)

Submission status: Runtime Error

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

    def root(self, A):
        if (self.parent[A] < 0):
            return A
        self.parent[A] = self.root(self.parent[A])
        return self.parent[A]

    def size(self, A):
        return -self.parent[self.root(A)]

    def unite(self, A, B):
        A = self.root(A)
        B = self.root(B)

        if (A == B):
            return False

        if (self.size(A) < self.size(B)):
            A, B = B, A

        self.parent[A] += self.parent[B]
        self.parent[B] = A

        return True

    def is_in_same(self, A, B):
        return self.root(A) == self.root(B)


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

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

print(max(uf.size(i)) for i in range(1, N+1))

Submission status: Runtime Error

Solution code:
def dfs(g, start):
    visited[start] = True
    cc.append(0)
    for nbr in g[start]:
        if not visited[nbr]:
            dfs(g, nbr)



from collections import defaultdict
n, m = map(int, input().split())
g = defaultdict(set)

for _ in range(m):
    a, b = map(int, input().split())
    g[a - 1].add(b - 1)
    g[b - 1].add(a - 1)


visited = [False]*n
ans = 0
for i in range(n):
    if not visited[i] and i in g:
        cc = []
        dfs(g, i)
        ans = max(ans, len(cc))

print(ans)

Submission status: Runtime Error

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

g = []

for _ in range(M):
	Ai, Bj = map(int, input().strip().split())
	j = -1
	for i, _g in enumerate(g):
		if Ai in _g or Bj in _g:
			j = i
	if j < 0:
		g.append(set([Ai, Bj]))
	else:
		g[j].add(Ai)
		g[j].add(Bj)

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

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
tmp = 0
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:
        group[AB[i][0]-1] += 1
        group[AB[i][1]-1] += 1
    else:
        if before0 == AB[i][0] and before1 == AB[i][1]:
            before0 = AB[i][0]
            before1 = AB[i][1]
            continue
        group[AB[i][0]-1] += 1
        group[AB[i][1]-1] += 1
        before0 = AB[i][0]
        before1 = AB[i][1]
        
print(max(group))

Submission status: Runtime Error

Solution code:
import collections
n,m = map(int,input().split())
ls = []
for i in range(m):
    a,b = map(int,input().split())
    tmp = 0
    for i in range(len(ls)):
      if (a in ls[i]) and (b in ls[i]):
        tmp = 1
        break
      if (a in ls[i]):
        ls[i].append(b)
        tmp = 1
        break
      elif (b in ls[i]):
        ls[i].append(a)
        tmp = 1
        break
    if tmp == 0:
    	ls.append([a,b])
#print(ls)
if len(ls) == 1:
  print(len(c))
else:
  ans = 0
  for i in ls:
    ans = max(ans,len(i))
  print(ans)

Submission status: Runtime Error

Solution code:
from sys import exit, stdin

input = stdin.readline
import copy

from collections import deque, Counter

# import numpy as np


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

D = [-1] * N

tmp = 0
for i in range(M):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    if D[a] == -1 and D[b] == -1:
        D[a] = tmp
        D[b] = tmp
        tmp += 1
    elif D[a] == -1 and D[b] != -1:
        D[a] = D[b]
    elif D[a] != -1 and D[b] == -1:
        D[b] = D[a]
    elif D[a] != D[b]:
        for k in range(N):
            if D[k] == D[b]:
                D[k] = a


R = Counter(D)
ans = R.most_common(2)
if ans[0][0] == -1:
    print(ans[1][1])
else:
    print(ans[0][1])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
N, M = list(map(int, input().split()))
edges = []
for _i in range(M):
    edges.append(list(map(int, input().split())))

import networkx as nx

G = nx.Graph()
G.add_edges_from(edges)
ans = 1
for comp in nx.connected_components(G):
    ans = max(ans, len(comp))
print(ans)

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]

for _ in range(m):
  x,y=map(int,input().split())
  a[find(y-1)]=find(x-1)

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

Submission status: Runtime Error

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

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

hint_list = get_unique_list(hint_list)

if M == 0:
    print(N)
else:
    friend_list.append(hint_list[0])
    for i in range(1,len(hint_list)):
        for j in range(len(friend_list)):
            if hint_list[i][0] in friend_list[j]:
                if hint_list[i][1] in friend_list[j]:
                    pass
                else:
                    frined_list[j].append(hint_list[i][1])
            elif hint_list[i][1] in friend_list[j]:
                if hint_list[i][0] in friend_list[j]:
                    pass
                else:
                    frined_list[j].append(hint_list[i][0])
            else:
                pass

    friend_length = []

    for i in range(len(friend_list)):
        friend_length.append(len(friend_list[i]))

print(max(friend_length))