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

    person_group = [0] * (N+5)
    group_counter = 0
    member_counter = {0: 0}

    def _marge_group(a, b):
        for i in range(len(person_group)):
            if person_group[i] == b:
                person_group[i] == a
        member_counter[a] = member_counter[a] + member_counter.pop(b)

    for _ in range(M):
        A, B = map(int, input().split())
        A -= 1
        B -= 1
        if person_group[A] == 0 and person_group[B] == 0:
            group_counter += 1
            person_group[A] = group_counter
            person_group[B] = group_counter
            member_counter[group_counter] = 2
        elif person_group[A] != 0 and person_group[B] == 0:
            person_group[B] = person_group[A]
            member_counter[person_group[A]] += 1
        elif person_group[A] == 0 and person_group[B] != 0:
            person_group[A] = person_group[B]
            member_counter[person_group[B]] += 1
        else:
            if person_group[A] == person_group[B]:
                continue
            else:
                _marge_group(person_group[A], person_group[B])
    print(max(member_counter.values()))

if __name__ == "__main__":
    resolve()

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

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

for p2ii in p2:
  g0=g[p2ii[0]]
  g1=g[p2ii[1]]
  rr[g1]+=rr[g0]
  rr[g0]=0

print(max(rr))

Submission status: Runtime Error

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

friends = [set() for i in range(N+1)]
for i in range(M):
    temp = [int(j) for j in input().split()]
    friends[temp[0]].add(temp[1])
    friends[temp[1]].add(temp[0])


def get_friend(p):
    global comp
    try:
        comp.remove(p)
    except:
        return 0
    temp = {p}
    for i in friends[p]:
        temp.add(i)
        get_friend(i)
    return temp


refri = []
comp = {i for i in range(1, N+1)}
for i in range(1, N+1):
    if i in comp:
        refri.append(get_friend(i))


ma = 0
for i in refri:
    if ma < len(i):
        ma = len(i)
print(ma)

Submission status: Runtime Error

Solution code:
import numpy as np

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

N = np.ones(n)*-1
n_group = 0

for i in range(M):
    a,b = [int(i) for i in input().split()]
    
    if N[a]==-1 and N[b]==-1:
        N[a] = n_group
        N[b] = n_group
        n_group += 1
    
    elif N[a]>-1 and N[b]>-1:
        new = min(N[a],N[b])
        old = max(N[a],N[b])
        for i in range(n):
            if N[i] == old:
                N[i] = new
    else:
        if N[a]>-1:
            N[b] = N[a]
        else:
            N[a] = N[b]
Y = 0
for i in range(n_group):
    Y = max(sum(N==i),Y)
print(Y)

Submission status: Runtime Error

Solution code:
from collections import Counter
n,m=map(int,input().split())
l=[]
for i in range(m):
  s=[]
  a,b=map(int,input().split())
  s.append(a)
  s.append(b)
  l.append(s)
def get_unique_list(seq):
    seen = []
    return [x for x in seq if (x or reversed(x)) not in seen and not seen.append(x)]
ls=get_unique_list(l)
cnt=Counter([x[0] for x in ls])
print(max(cnt.values())+1)

Submission status: Runtime Error

Solution code:
import numpy as np


def main():
    n, m = map(int, input().split())
    friends_mat = np.zeros((n, n), dtype=int)
    for i in range(m):
        a, b = map(int, input().split())
        friends_mat[a - 1][b - 1] = 1
        friends_mat[b - 1][a - 1] = 1
    # print(friends_mat)
    print(max(friends_mat.sum(axis=0)+1))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

    person_group = [0] * (N+5)
    group_counter = 0
    member_counter = {0: 0}

    def _marge_group(a, b):
        for i in range(len(person_group)):
            if person_group[i] == b:
                person_group[i] == a
        member_counter[a] = member_counter[a] + member_counter.pop(b)

    for _ in range(M):
        A, B = map(int, input().split())
        if person_group[A] == 0 and person_group[B] == 0:
            group_counter += 1
            person_group[A] = group_counter
            person_group[B] = group_counter
            member_counter[group_counter] = 2
        elif person_group[A] != 0 and person_group[B] == 0:
            person_group[B] = person_group[A]
            member_counter[person_group[A]] += 1
        elif person_group[A] == 0 and person_group[B] != 0:
            person_group[A] = person_group[B]
            member_counter[person_group[B]] += 1
        else:
            if person_group[A] == person_group[B]:
                continue
            else:
                _marge_group(person_group[A], person_group[B])
    print(max(member_counter.values()))

if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

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

friends = [set() for i in range(N+1)]
print(friends)
for i in range(M):
    temp = [int(j) for j in input().split()]
    friends[temp[0]].add(temp[1])
    friends[temp[1]].add(temp[0])


def get_friend(p):
    global comp
    try:
        comp.remove(p)
    except:
        return 0
    temp = {p}
    for i in friends[p]:
        temp.add(i)
        get_friend(i)
    return temp


refri = []
comp = {i for i in range(1, N+1)}
for i in range(1, N+1):
    if i in comp:
        refri.append(get_friend(i))

print(refri)

ma = 0
for i in refri:
    if ma < len(i):
        ma = len(i)
print(ma)

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)

if len(c) == 1:
    print(n)
else:
    print(max(c.values()))

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 = list()
    hitDict = set()
    for i in range(M):
        args = list(map(lambda x: int(x), input().split()))

        hit0 = args[0] in hitDict
        hit1 = args[1] in hitDict
        hitDict.add(args[0])
        hitDict.add(args[1])

        if hit0 and hit1:
            group0 = 0
            group1 = 0
            for group in groupList:
                if args[0] in group:
                    group0 = group
                if args[1] in group:
                    group1 = group

            if group0 != group1:
                groupList.remove(group0)
                groupList.remove(group1)
                groupList.add(group0 + group1)

        elif (not hit0) and (not hit1):
            groupList.append({args[0], args[1]})
        elif hit0:
            for group in groupList:
                if args[0] in group:
                    group.add(args[1])
                    break
        elif hit1:
            for group in groupList:
                if args[1] in group:
                    group.add(args[0])
                    break

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

    print(maxNum)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from itertools import combinations

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

x = [[] for _ in range(N + 1)]
for a, b in AB:
    x[a].append(b)
    x[b].append(a)

for row in x:
    if len(row) >= 2:
        for v in combinations(row, 2):
            x[v[0]].append(v[1])
            x[v[1]].append(v[0])

l1 = []
l2 = [False] * (N + 1)
for i in range(1, N + 1):
    if l2[i]:
        continue
    l1.append([i])
    l2[i] = True
    for j in range(1, N + 1):
        if j == i or l2[j]:
            continue
        for k in l1[-1]:
            if j in x[k]:
                flag=True
                break
        if flag:
            continue
        l1[-1].append(j)
        l2[j] = 1
print(len(l1))

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
        groupn = 1
        nums[i] = gnum
    for f in friends[i]:
        if nums[f] == 0:
            nums[f] = gnum
            groupn += 1
            if groupn > nmax:
                nmax = groupn
            find_route(f)

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

print(max(nmax, 1))

Submission status: Runtime Error

Solution code:
N, M = [int(i) for i in input().split()]
a, b = input().split()
tomodachi_list = [[a,b]] #同じグループにしてはいけないリスト

for _ in range(M-1):
    a, b = input().split()
    flag = 0
    for group in tomodachi_list:
        if a in group and b in group:
            break
        elif a in group and b not in group:
            group += b
            break
        elif a not in group and b in group:
            group += a
            break
        else:
            flag = 1
            pass
        if flag == 1:
            tomodachi_list.append([a,b])

m = 0
for i in tomodachi_list:
    if m < len(i):
        m = len(i)
print(m)

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

print(max(F))

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+1)
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:
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 type(frl[number[a-1]-1]) == int:
		number[a-1] = frl[number[a-1]-1]
	if number[b-1] != 0 and type(frl[number[b-1]-1]) == int:
		number[b-1] = frl[number[b-1]-1]
	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] = number[a-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:
n, m = map(int, input().split())
F = [list(map(int, input().split())) for i in range(m)]


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

for f in F:
    a=f[0]-1
    b=f[1]-1
    #print(a,b)

    if people[a]==-1 and people[b]==-1:
        friends.append(2)
        people[a]=num
        people[b]=num
        num+=1

    elif people[a]!=-1 and people[b]!=-1 and people[a]!=people[b]:
        A=people[a]
        B=people[b]
        friends[A] +=friends[B]
        for i in friends[B]:
            people[i]=A

    elif people[a]!=-1 and people[b]==-1:
        friends[people[a]]+=1
        people[b]=people[a]

    elif people[a]==-1 and people[b]!=-1:
        friends[people[b]]+=1
        people[a]=people[b]

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

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):
    count = max(dfs(node), count)
print(count)

Submission status: Runtime Error

Solution code:
import numpy as np

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

N = np.ones(n)*-1
n_group = 0

for i in range(M):
    a,b = [int(i) for i in input().split()]
    
    if N[a]==-1 and N[b]==-1:
        N[a] = n_group
        N[b] = n_group
        n_group += 1
    
    elif N[a]>-1 and N[b]>-1:
        new = min(N[a],N[b])
        old = max(N[a],N[b])
        for i in range(n):
            if N[i] == old:
                N[i] = new
    else:
        if N[a]>-1:
            N[b] = N[a]
        else:
            N[a] = N[b]
Y = 0
for i in range(n_group):
    Y = max(sum(N==i+1),Y)
print(Y)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
li=[]
ans=0
if m!=0: 
    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(deque([a,b]))
        #print(li)
    ans=max([len(li[i]) for i in range(len(li))])
print(ans if m!=0 else 1)

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
#define rep(i,n) for(ll i=0;i<(ll)n;++i)

struct UnionFind{
  vector<int> d; //子なら親のID,根なら-サイズを保存
  UnionFind(int n=0) : d(n,-1) {} //最初はみんな根でサイズ1 (コンストラクタ :と{}の間には初期化子が入る)
  int find(int x){
    //自分が根なら自分を、そうでなければ親のfind結果を返す(再帰)
    if( d.at(x) < 0 )  return x;
    return d.at(x) = find(d.at(x)); //親のfindの結果で上書き(メモ化で木のサイズを小さくする)
  }
  bool unite(int x,int y){
    x = find(x); y = find(y);
    if( x == y ) return false; //元々同じグループなら、やることはない (falseはminimun spaning treeで使えるので便利)
    if( -d.at(x) < -d.at(y) ) swap(x,y); //サイズが大きい方に小さい方をくっつけたい
    d.at(x) += d.at(y); //xにyをくっつける
    d.at(y) = x;
    return true;
  }
  //同じ集合に属しているか判定する関数
  bool same(int x,int y){ return find(x) == find(y); }
  //要素の属する集合のサイズを返す関数
  int size(int x){ return -d.at( find(x) ); }
};

int main(){
  ll n,m;cin >> n >> m;
  vector<int> deg(n);
  vector<<vector<ll>> to(n,vector<ll>(0));
  UnionFind uf(n);
  //友達関係
  rep(i,m){
    int a,b;
    cin >> a >> b;
    a--; b--;
    deg.at(a)++;
    deg.at(b)++;
    uf.unite(a,b);
  }
  ll ans = -1;
  rep(i,n){
    ans = max(uf.size(i),ans);
  }
  cout << ans << endl;
  return 0;
}

Submission status: Runtime Error

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

matrix = [[0 for i in range(n)] for j in range(n)]
# print(matrix)
for i in range(m):
	matrix[frends[i][0]-1][frends[i][1]-1] = 1
	matrix[frends[i][1]-1][frends[i][0]-1] = 1
# print(matrix)

ans = 0
for i in renge(n):
	cnt = matrix[i][i+1:].count(0)
	ans = max(ans, cnt)

print(cnt)

Submission status: Runtime Error

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

li = list(set() for _ in range(m))

count = -1
for _ in range(m):
    flag = False
    one, two = map(int, input().split())
    for i in range(count):
        if one in li[i] or two in li[i]:
            li[i].add(one)
            li[i].add(two)
            flag = True
            break
    if flag is False:
        count += 1
        li[count].add(one)
        li[count].add(two)

max = 0
for j in li:
    if max < j:
        max = j
print(max)

Submission status: Runtime Error

Solution code:
import math

n=int(input())

A=list(map(int,input().split()))
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
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())
L = []
N2 = [[0]*N for i in range(N)]
ans = 0
for _ in range(M):
  A, B = map(int, input().split())
  N2[A-1][B-1] = 1; N2[B-1][A-1] =1
sumN2 = []
for i in range(N):
    sumN2.append(N[i]+1)
print(max(sumN2))

Submission status: Runtime Error

Solution code:
import numpy as np
from copy import deepcopy
from heapq import heappop, heappush
from bisect import bisect_left, bisect
from collections import Counter, defaultdict, deque
from itertools import product, permutations, combinations

N, M = map(int, input().split())
A = [0] * M
B = [0] * M

R = {i: set() for i in range(N)}

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

    R[a - 1].update(R[i] | {b - 1})


for i in range(N-1):
    for j in range(i + 1, N):
        # print(i, j, R[i], R[j])
        if len(R[i] & R[j]) > 0:
            R[i].update(R[j])
            R[j].clear()

s = 0
for i in range(N):
    s += len(R[i])

print(s)
exit()

Submission status: Runtime Error

Solution code:
import numpy as np
N,M = list(map(int,input().split()))
newlist = [[] for i in range(N)]
for i in range(M):
    A,B=input().split()
    newlist[int(A)-1].append(int(A))
    newlist[int(A)-1].append(int(B))
    newlist[int(A)-1]=list(set(newlist[int(A)-1]))
for  i in range(0,N-1):
	for j in range(i+1,N):
		if(newlist[i]&newlist[j]>0):
			newlist[i].append(newlist[j])
			newlist[i]=list(set(newlist[i]))
			newlist[j]=[]
count=0
length=0
for i in range (0,N):
  count=len(newlist[i])
	if (count>length):
      length=count
print(length)

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
        groupn = 1
        nums[i] = gnum
    for f in friends[i]:
        if nums[f] == 0:
            nums[f] = gnum
            groupn += 1
            if groupn > nmax:
                nmax = groupn
            find_route(f)

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

print(nums)
print(max(nmax, 1))

Submission status: Runtime Error

Solution code:
from collections import Counter
n,m=map(int,input().split())
l=[]
for i in range(m):
  s=[]
  a,b=map(int,input().split())
  s.append(a)
  s.append(b)
  l.append(s)
def get_unique_list(seq):
    seen = []
    return [x for x in seq if (x or reversed(x)) not in seen and not seen.append(x)]
ls=get_unique_list(l)
cnt=Counter([x[0] for x in ls])
print(max(cnt.values)+1)

Submission status: Runtime Error

Solution code:
def main():
    N, M = map(int, input().split())
    relations = dict()
    for _ in range(M):
        r_a, r_b = map(int, input().split())
        min_r, max_r = min(r_a, r_b), max(r_a, r_b)
        if min_r not in relations:
            relations[min_r] = {max_r}
        else:
            relations[min_r].add(max_r)

    print(relations)
    D = {}
    for i in range(N):
        calc(relations, i, D)
    print(D)

    print(max(D.values()))


def calc(relations, i, D):
    if i not in relations:
        return 1
    answer = 1
    for j in relations.get(i):
        if j in D:
            answer += D[j]
        else:
            answer += calc(relations, j, D)
            D[j] = answer
    return answer


if __name__ == "__main__":
    main()


'''
1-2, 1-5, 3-4
1-2-5, 3-4

1-2, 1-3, 1-4, 2-3, 2-4, 3-4
1-2-3-4, 2-3-4, 3-4

1-3, 1-4, 2-4, 5-9
1-3-4, 2-4, 5-9
'''

Submission status: Runtime Error

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

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

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


def dfs(x:int, mark:set):
    marked = mark
    a = 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
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):
    for j in range(i+1,N):
        for k in range(j+1,N):
            if (mat[i][j]==1)&(mat[i][k]==1):
                mat2[j][k]=1
                mat2[k][j]=1
print(str(int(np.max(np.sum(mat2,axis=1))+1)))

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].remove(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:
N,M = map(int,input().split())
f = []
for i in range(M):
    A,B = map(int,input().split())
    a = {A,B}
    for i in f:
        if i & a != set():
            a = i | a
            f.remove(i)
#            print(f,a,i)
    f.append(a)

#print(f)
print(len(max(f)))

Submission status: Runtime Error

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

def main():
    from collections import deque
    N, M = MI()
    fri_list = []
    num_list = [0] * (N + 1)
    for i in range(M):
        a, b = MI()
        if num_list[a] == 0 and num_list[b] == 0:
            fri_list.append([a, b])
        elif num_list[a] == 0 or num_list[b] == 0:
            for l in fri_list:
                if a in l:
                    l.append(b)
                elif b in l:
                    l.append(a)
        else:
            continue
        num_list[a] = num_list[b] = 1

    len_list = []
    for l in fri_list:
        x = len(l)
        len_list.append(x)
    ans = max(len_list)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]


    
    
def main():
    N, M = MI()
    mylist = [[] for i in range(N)]
    for i in range(M):
        a, b = MI()
        mylist[a-1].append(b-1)
        mylist[b-1].append(a-1)
    
    dic = defaultdict(int)
    
    visit = [True]*N
    index = 0

    for i in range(N):
        dq = deque()
        if visit[i]:
            dq.append(i)
            while dq:
                temp = dq.popleft()
                for j in mylist[temp]:
                    if visit[j]:
                        dic[index]+=1
                        visit[j] = False
                        dq.append(j)
            index+=1
                
        
        
        
    #グループ数
    all_group_num = sorted(dic.values())
    res = 0
    all_num = N
    min_num = 0
    group = len(all_group_num)
    if group < N:
        all_group_num = [1]*(N-group)+all_group_num
    
    
    
    while True:
        index = bisect_right(all_group_num, min_num)
        all_num -= (group-index)*(all_group_num[index]-min_num)
        res+= all_group_num[index]-min_num
        
        min_num = all_group_num[index]
        
        if all_num == 0:
            break
        
    print(res)

    
    
    
    
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
from copy import deepcopy
from heapq import heappop, heappush
from bisect import bisect_left, bisect
from collections import Counter, defaultdict, deque
from itertools import product, permutations, combinations

N, M = map(int, input().split())
A = [0] * M
B = [0] * M

R = {i: set() for i in range(N)}

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

    R[a - 1].update(R[i] | {b - 1})


for i in range(N-1):
    for j in range(i + 1, N):
        # print(i, j, R[i], R[j])
        if len(R[i] & R[j]) > 0:
            R[i].update(R[j])
            R[j].clear()

s = 0
for i in range(N):
    print(R[i])
    s += len(R[i])

print(s)
exit()

Submission status: Runtime Error

Solution code:
def make_group(checked, a, friends):
  group = []
  if checked[a]:
    return group
  group.append(a)
  checked[a] = True
  for b in friends[a]:
    group += make_group(checked, b, friends)
  return group
  
n, m = map(int, input().split())
friends = {}
checked = {}
for i in range(1, n+1):
  friends[i] = set()
  checked[i] = False
for i in range(m):
  a, b = map(int, input().split())
  friends[a].add(b)
  friends[b].add(a)
for i in range(1, n+1):
  friends[i] = list(friends[i])
minimum = -float('inf')
for i in range(1, n+1):
  group = make_group(checked, i, friends)
  if group:
    minimum = max(minimum, len(group))
print(minimum)

Submission status: Runtime Error

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

li_all = []
for i in range(m):
  li = list(map(int, input().split()))
  li_all.append(li)

li_g = []
for i in range(1, m+1):
  li_g.append([])
  for j in range(m):
    if i in li_all[j]:
      li_g[i-1].extend(li_all[j])
  li_g[i-1] = list(set(li_g[i-1]))

def conbine(li, check_num):
  kabutta = []
  for i in range(len(li)):
    if len(set(li[check_num]) & set(li[i])) != 0:  # 重複あり
      li[check_num].extend(li[i])
      kabutta.append(i)
  kabutta.reverse()
  len_li = len(li)
  for i in kabutta:
    del li[i]
  return li, len(kabutta), len_li

result = 0
while len(li_g) > 0:
  li_g, kabutta, len_li = conbine(li_g, 0)
  if kabutta != 0:
    if len_li > result:
      result = len_li
    del li_g[0]
  if len(li_g) == 1:
    if len(set(li_g[0])) > result:
      result = len(set(li_g[0]))
    break

print(result)