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())
friendlist={i+1:0 for i in range(N)}
sumg=0
for m in range(M):
  A,B=map(int,input().split())
  if friendlist[A]==0 and friendlist[B]==0:
    sumg+=1
    friendlist[A]=sumg
    friendlist[B]=sumg
  elif friendlist[A]==0:
    friendlist[A]=friendlist[B]
  elif friendlist[B]==0:
    friendlist[B]=friendlist[A]
  elif friendlist[A]!=friendlist[B]:
    k=friendlist[B]
    for i in range(1,N+1):
      if friendlist[i]==k:
        friendlist[i]=friendlist[A]
maxlist=[0 for _ in range(sumg+1)]
for i in range(1,N+1):
  maxlist[friendlist[i]]+=1
print(max(maxlist[1:]))

Submission status: Runtime Error

Solution code:
import collections
import numpy as np
N,M = map(int,input().split())
a = []
for i in range(M):
  a.append(sorted(list(map(int,input().split()))))
  
def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

k = get_unique_list(a)
k = np.ravel(k)
s = collections.Counter(k)
print(s.most_common()[0][1]+1)

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)]=e
    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
input = sys.stdin.readline
INF = 10**18
sys.setrecursionlimit(10**6)

def li():
    return [int(x) for x in input().split()]

N, M = li()
L = []
for i in range(M):
    a, b = sorted(li())
    L.append((a, b))

L = set(L)

cnts = [0] * (N+1)

for l in L:
    a, b = l
    cnts[a] += 1
    cnts[b] += 1
# print(cnts)
p = cnts.index(max(cnts))
# print(p)

others = []
for l in L:
    a, b = l
    if a == p:
        others.append(b)
    elif b == p:
        others.append(a)

anothers = []
for other in others:
    for l in L:
        a, b = l
        if a == other:
            anothers.append(b)
        elif b == other:
            anothers.append(a)
#
# print(others)
# print(anothers)

all = list(set(others + anothers))
all.remove(p)
ans = len(all) + 1
print(ans)

Submission status: Runtime Error

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

def main():
    N, M = map(int, input().split())
    a, b = map(int, input().split())
    groups = []
    groups.append({a, b})
    for _ in range(1, M):
        a, b = map(int, input().split())
        flag = True
        for g in groups:
            if a in g:
                g.add(b)
                flag = False
            if b in g:
                g.add(a)
                flag = False
        if flag:
            groups.append({a, b})
    ans = 0
    for g in groups:
        ans = max(ans, len(g))

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import numpy as np

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

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

g = np.zeros(N, dtype = int)
n = np.zeros(N, dtype = int)

num = 1

for i in range(len(c)):
    
    s = g[c[i][0]-1]
    t = g[c[i][1]-1]
    
    if s != 0 and t != 0:
        if s == t:
            pass
        else:
            matched = np.count_nonzero(g==t)
            n[s-1] += matched
            n[t-1] -= matched
            g[g==t] = s

    elif s != 0:
        t = s
        n[s-1] += 1
    elif t != 0:
        s = t
        n[t-1] += 1
    else:
        s = num
        t = num
        n[num-1] += 2
        num += 1

print(max(n) or 1)

Submission status: Runtime Error

Solution code:
たとえば
6 3
1 2
1 3
4 5
だったら、
1 2 と 1 3を連結させて
1 2 3
にして
1 2 3
4 5
6
というようにするとかして最も連結が長くなっているものの連結数(今回の場合は1 2 3 で3つ)が
解答となるようなプログラムを書けばいい。

Submission status: Runtime Error

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

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

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
      break
  for j in range(len(lol)):
    if b in lol[j]:
      found_b = j
      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:
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 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:
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(lambda x:find(int(x)-1),input().split())
  if x != y: a[x] = y

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

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const int INF = 1e9;

#define PB push_back
#define PF push_front
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vpi vector<pii>
#define vll vector<ll>
#define vpl vector<pll>
#define vvi vector<vector<int>>
#define vvl vector<vector<ll>>
#define MX(x) *max_element(all(x))
#define MN(x) *min_element(all(x))
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pr_d(x) cout << fixed << setprecision(15) << x << endl
#define ud(c, x) distance(c.begin(), upper_bound(all(c), x))
#define ld(c, x) distance(c.begin(), lower_bound(all(c), x))
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define rep3(i, n) for (int i = (n - 1); i >= 0; --i)
#define rep4(i, a, b) for (int i = (a); i > (b); --i)
#define pb push_back
#define out(x) cout << x << "\n"
bool odd(int i)
{
    return i % 2;
}

#define all(v) v.begin(), v.end()

int gcd(int a, int b)
{
    return __gcd(a, b);
}
int lcm(int a, int b) { return a * (b / gcd(a, b)); }
void Yes_No(bool f)
{
    if (f)
        printf("Yes\n");
    else
        printf("No\n");
}
void YES_NO(bool f)
{
    if (f)
        printf("YES\n");
    else
        printf("NO\n");
}

template <typename T>
void deb1(T x)
{
    cout << x << "\n";
}

template <typename T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
template <typename T>
bool chmin(T &a, const T &b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
//-------------------ここから回答する-----------------------

void solve(void)
{
    int n, m;
    cin >> n >> m;
    vector<set<int>> g(n);
    rep(i, m)
    {
        int a, b;
        cin >> a >> b;
        --a, --b;
        g[a].insert(b);
        g[b].insert(a);
    }
    vector<int> dist(n, INF);
    int ans = 0;
    rep(i, n)
    {
        if (dist[i] == INF)
        {
            int res = 1;
            queue<int> q;
            dist[i] = 1;
            q.push(i);
            while (!q.empty())
            {
                auto x = q.back();
                q.pop();
                for (auto j : g[x])
                {
                    if (dist[j] == INF)
                    {
                        res++;
                        dist[j] = dist[x] + 1;
                        q.push(j);
                    }
                }
            }
            ans = max(ans, res);
        }
    }
    cout << ans << endl;
}
int main(void) { solve(); }

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

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([])
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:
import numpy as np
from collections import deque

N, M = map(int, input().split())
rel_matrix = np.zeros((N, N), dtype='bool')
for i in range(M):
    A, B = map(int, input().split())
    rel_matrix[A-1, B-1] = True
    rel_matrix[B-1, A-1] = True

people = list(np.arange(N))

max_cluster_size = 0
while len(people) != 0:
    cluster_size = 0
    leader = people[0]
    people.remove(leader)
    cluster = deque([leader])
    cluster_size += 1

    while True:
        try:
            subleader = cluster.popleft()
        except IndexError:
            break

        del_supposed = []
        for i in people:
            if rel_matrix[subleader, i] == True:
                cluster.append(i)
                cluster_size += 1
                del_supposed.append(i)

        for i in del_supposed:
            people.remove(i)

    if cluster_size > max_cluster_size:
        max_cluster_size = cluster_size
    continue

print(max_cluster_size)

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 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 collections
a=input()
a=a.split()
n=int(a[0])
m=int(a[1])
l=[0]*(n)
k=1
for i in range(m):
    x=input()
    x=x.split()
    xa=int(x[0])-1
    xb=int(x[1])-1
    if l[xa]==0 and l[xb]==0:
        l[xa]=k
        l[xb]=k
        k+=1
    if l[xa]==0 and l[xb]!=0:
        l[xa]=l[xb]
    if l[xa]!=0 and l[xb]==0:
        l[xb]=l[xa]
    if l[xa]!=0 and l[xb]!=0 and l[xa]!=l[xb]:
        p=min(l[xa],l[xb])
        q=max(l[xa],l[xb])
        l=[p if z==q else z for z in l]
l=[z for z in l if z!=0]
c=collections.Counter(l)
print(max(c.values()))

Submission status: Runtime Error

Solution code:
import numpy as np

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

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

g = np.zeros(N, dtype = int)
n = np.zeros(N, dtype = int)

num = 1

for i in range(len(c)):
    
    s = g[c[i][0]-1]
    t = g[c[i][1]-1]
    
    if s != 0 and t != 0:
        if s == t:
            pass
        else:

            for j in range(len(g)):
                if g[j] == t:
                    g[j] = s
                    n[s-1] += 1
                    n[t-1] -= 1

    elif s != 0:
        t = s
        n[s-1] += 1
    elif t != 0:
        s = t
        n[t-1] += 1
    else:
        s = num
        t = num
        n[num-1] += 2
        num += 1

print(max(n) or 1)

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(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:
N,M=map(int,input().split())
friends_set=set()
for i in range(M):
    a,b=map(int,input().split())
    if a>b:
        a,b=b,a
    friends_set.add((a,b)) 
    
friends_list=[[] for _ in range(N)]
for f in friends_set:
    friends_list[f[0]].append(f[1])
    friends_list[f[1]].append(f[0])

max_len=0
for i in friends_list:
    max_len=max(max_len,len(i)+1)
    
print(max_len)

Submission status: Runtime Error

Solution code:
import collections

class UnionFindBasic():
    def __init__(self, n):
        self.parents = list(range(n))

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

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

        if x == y:
            return

        self.parents[y] = x

n, m = map(int, input().split(" "))
ufb = UnionFindBasic(n)

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

c = collections.Counter([ufb.find(i) for i in range(n)])
print(max(c.values()))

Submission status: Runtime Error

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

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

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

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

            else:
                set_x = Sets.pop( Dicto[a] )
                Sets[ Dicto[b] ] |= ( set_x )
                l_set_x = list( set_x )
                for j in l_set_x:
                    Dicto[j] = Dicto[b]

    #print(Sets)
    #print(Dicto)

    max_len = 1

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

    print(max_len)


main()

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = list()
B = list()
for _ in range(M):
    a, b = map(int, input().split())
    A.append(a-1)
    B.append(b-1)

largest = 1
group = []
people = [-1] * N
for a, b in zip(A, B):
    if people[a] != -1 and people[b] != -1 and people[a] != people[b]:
        group[people[a]] |= group[people[b]]
        for gb in group[people[b]]:
            people[gb] = people[a]
        group[people[b]] = None
    elif people[a] != -1:
        people[b] = people[a]
        group[people[a]].add(b)
    elif people[b] != -1:
        people[a] = people[b]
        group[people[b]].add(a)
    else:
        group.append(set([a, b]))
        people[a] = len(group)-1
        people[b] = people[a]
    largest = max(len(group[people[a]]), largest)

print(largest)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
ed = [0] * (n+1)


def rm(nu):
    if len(vr) == 0:
        return 0
    curr = vr.pop(vr.index(nu))
    if ed[curr] == 0:
        return 1
    else:
        tmp = 1
        for p in ed[curr]:
            tmp += rm(p)
        return tmp


for i in range(m):
    t1, t2 = map(int, input().split())
    if t1 > t2:
        t2, t1 = t1, t2
    if ed[t1] == 0:
        ed[t1] = [t2]
    else:
        if t2 not in ed[t1]:
            ed[t1].append(t2)
vr = list(range(n, 0, -1))
maxs = 0

while len(vr) != 0:
    maxs = max(maxs, rm(vr[-1]))
print(maxs)

Submission status: Runtime Error

Solution code:
import numpy as np
i4 = np.int32
i8 = np.int64


def find(x, parents):
    if parents[x] == x:
        return x
    else:
        return find(parents[x], parents)


def union (x, y, parents, depth):
    x = find(x, parents)
    y = find(y, parents)
    if x == y:
        return

    if depth[x] == depth[y]:
        depth[x] += 1
        parents[y] = x
    elif depth[x] > depth[y]:
        parents[y] = x
    else:
        parents[x] = y


def main(in_file):
    stdin = open(in_file)
    N, M = [int(x) for x in stdin.readline().split()]
    a = np.empty(M, i8)
    b = np.empty(M, i8)
    for i in range(M):
        a[i], b[i] = [int(x) - 1 for x in stdin.readline().split()]
    parents = np.arange(N)
    depth = np.zeros(N, i8)
    for i in range(M):
        union(a[i], b[i], parents, depth)
    num = np.zeros(M, i8)
    for i in range(N):
        p = find(i, parents)
        num[p] += 1
    ans = num.max()
    print(ans)


main('/dev/stdin')

Submission status: Runtime Error

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


def main():
    N,M = list(map(int, sys.stdin.readline().split()))
    AB_list = [ list(map(int, sys.stdin.readline().split())) for _ in range(M) ]


    edge = {}  
    # { int : set }
    # { the number of human : {friends} }

    for a,b in AB_list:
        edge.setdefault(a, set())
        edge[a].add(b)

        edge.setdefault(b, set())
        edge[b].add(a)
    

    visited = [None] + [0]*N
    #  0: not visited,  1:visited


    max_relation = 0

    for i in range(1, N+1):
        if visited[i] == 0:
            visited[i] = 1
            ret = dfs(edge, visited, i, 0)
            max_relation = max(max_relation, ret)
    
    
    print( max_relation + 1 )


def dfs(edge, visited, num, cnt):
    max_cnt = cnt

    if num in edge:
        for next_node in edge[num]:
            if visited[next_node] == 0:
                visited[next_node] = 1
                cnt += 1
                ret = dfs(edge, visited, next_node, cnt)
                max_cnt = max(max_cnt, ret)

    return max_cnt


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
graph = [[0]*N for _ in range(N)]
sum_g = 0
for _ in range(M):
    a, b = map(int, input().split())
    graph[a-1][b-1] = 1
    graph[b-1][a-1] = 1 
for i in range(N):
    sum_g = max(sum_g, sum(graph[i]))
print(sum_g+1)

Submission status: Runtime Error

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

for a,b in M:
    if a>b:
        a,b=b,a
    d[a].add(b)

val = max(d,key=d.get)
for i in d[val]:
    if d[i]!=set():
        d[val]|=d[i]
print(len(d[val])+1)

Submission status: Runtime Error

Solution code:
import collections
N,M = tuple(map(int,input().split()))
friend_list = []
for i in range(M):
  a,b = map(int,input().split())
  friend_list.append(a)
  friend_list.append(b)
  
#print(friend_list)
friend_list.sort()
#print(friend_list)
c = collections.Counter(friend_list)

collect = c.most_common()[0][1]+1
if collect > N:
  print(N)
else:
  print(collect)

Submission status: Runtime Error

Solution code:
from collections import Counter

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

print(UF.par)

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

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

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

if M==0:
    print(1)
    sys.exit()
    
friends_map = np.zeros(shape=(N, N))

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

ans = int(max(np.sum(friends_map, axis=1))+1)

print(ans)

Submission status: Runtime Error

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

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

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

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

            else:
                set_x = Sets.pop( Dicto[a] )
                Sets[ Dicto[b] ] |= ( set_x )
                l_set_x = list( set_x )
                for j in l_set_x:
                    Dicto[j] = Dicto[b]

    #print(Sets)
    #print(Dicto)

    max_len = 1

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

    print(max_len)


main()

Submission status: Runtime Error

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

for a,b in M:
    if a>b:
        a,b=b,a
    d[a].add(b)

val = max(d,key=d.get)
for i in d[val]:
    d[val]|=d[i]
print(len(d[val])+1)

Submission status: Runtime Error

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

G = []
lookup_tab = {}

AB = [list(sorted((map(int, input().split())))) for _ in range(M)]
AB.sort()
for a, b in AB:
    if a not in lookup_tab and b not in lookup_tab:
        G.append({a, b})
        lookup_tab[a] = len(G) - 1
        lookup_tab[b] = len(G) - 1
    elif a in lookup_tab and b not in lookup_tab:
        gid = lookup_tab[a]
        lookup_tab[b] = gid
        G[gid].add(b)
    elif b in lookup_tab and a not in lookup_tab:
        gid = lookup_tab[b]
        lookup_tab[a] = gid
        G[gid].add(a)
    else:
        assert(lookup_tab[a] == lookup_tab[b])
        continue

if G:
    print(max([len(g) for g in G]))
else:
    print(1)

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(lambda x:int(x)-1,input().split())
  a[find(y)]=find(x)

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

Submission status: Runtime Error

Solution code:
import collections
N, M = map(int, input().split())
A = [0]*M
B = [0]*M
for i in range(M):
  A[i],B[i] = map(int,input().split())
ans = 0
f = [-1]*N
for i in range(M):
  if f[A[i]-1] == -1 and f[B[i]-1] == -1:
    f[A[i]-1] = i
    f[B[i]-1] = i
  elif f[A[i]-1] != -1 and f[B[i]-1] == -1:
    f[B[i]-1] = f[A[i]-1]
  else:
    f[A[i]-1] = f[B[i]-1]
ff = [i for i in f if i != -1]
print(max(collections.Counter(ff).values()))

Submission status: Runtime Error

Solution code:
N, M = (int(x) for x in input().split())
import collections
Parent = [i for i in range(N)]
def fp(i):
    global Parent
    if Parent[i] == i:
        return i
    else:
        Parent[i] == fp(Parent[i])
        return Parent[i]

for _ in range(M):
    a, b = (int(x) for x in input().split())
    Parent[max(a,b)-1] = fp(min(a,b)-1)

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

Submission status: Runtime Error

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

    # xの属する根を求める
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            # if they have the same parent, no need to union
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


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

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

# from collections import Counter
# c = Counter(uf.par)

# print(max(c.values()))

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

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:
a = list(map(int,input().split()))
n = a[0]
m = a[1]
ab = [map(int, input().split()) for _ in range(m)]
a, b = [list(i) for i in zip(*ab)]

set_list = [{a[0],b[0]}]
for i in range(1,m):
  flag = 0
  for j in range(len(set_list)):
    if a[i] in set_list[j] or b[i] in set_list[j]:
      set_list[j].add(a[i])
      set_list[j].add(b[i])
      flag = 1
      break
  if flag == 0:
    set_list.append({a[i],b[i]})

#print(set_list)

ans = 0
for i in range(len(set_list)):
  ans = max(ans, len(set_list[i]))
  
print(ans)

Submission status: Runtime Error

Solution code:
import networkx as nx
n, m = map(int, input().split())
tree1 = nx.Graph()
for _ in range(m):
  a, b = map(int, input().split())
  tree1.add_edge(a, b)
res = 0
for i in range(1, n + 1):
  res = max(res, tree1.degree(i))
print(res + 1)

Submission status: Runtime Error

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

l = []

A, B = map(int, input().split())
l.append((A, B))
for i in range(M-1):
    A, B = map(int, input().split())
    hit = None
    for tup in l:
        if A in tup or B in tup:
            if hit != None:
                hit = tuple(set(hit+tup+(A, B)))
            else:
                hit = tuple(set(tup+(A, B)))
            l.remove(tup)
    if hit != None:
        l.append(hit)
    else:
        l.append((A, B))
ans = 0

for item in (l):
    if ans < len(item):
        ans = len(item)
print(ans)