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:
class UnionFind:
    def __init__(self, n):
        self.p = list(range(n+1))
    def find(self, x):
        if x == self.p[x]:  return x
        self.p[x] = self.find(self.p[x])
        return self.p[x]
    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            self.p[x] = y

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

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

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, n):
        self.p = list(range(n+1))
    def find(self, x):
        if x == self.p[x]:  return x
        self.p[x] = self.find(self.p[x])
        return self.p[x]
    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            self.p[x] = y

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

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

Submission status: Runtime Error

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

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

indexlist=[-1]*n

def findroot(x):
    while 1:
        if indexlist[x-1] < 0:
            return x
        else:
            x=indexlist[x-1]
            
def merge(a,b):
    art=findroot(a)
    brt=findroot(b)
    if not art == brt:
        indexlist[art-1]+=indexlist[brt-1]
        indexlist[brt-1]=a
        return
    else:
        return     

for j in range(m):
    a1=a[j]
    b1=b[j]
    merge(a1,b1)

ans=min(indexlist)*(-1)
print(ans)

Submission status: Runtime Error

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

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

indexlist=[-1]*n

def findroot(x):
    while 1:
        if indexlist[x-1] < 0:
            return x
        else:
            x=indexlist[x-1]
            


def merge(a,b):
    art=findroot(a)
    brt=findroot(b)
    if not art == brt:
        indexlist[art-1]+=indexlist[brt-1]
        indexlist[brt-1]=a
        return
    else:
        return
        

for j in range(m):
    a1=a[j]
    b1=b[j]
    merge(a1,b1)

ans=min(indexlist)*(-1)
print(ans)

Submission status: Runtime Error

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

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

indexlist=[-1]*n

def findroot(x):
    while 1:
        if indexlist[x-1] < 0:
            return x
        else:
            x=indexlist[x-1]
            


def merge(a,b):
    art=findroot(a)
    brt=findroot(b)
    art_ix=indexlist[art-1]
    brt_ix=indexlist[brt-1]
    if not art_ix<0 == brt_ix<0:
        indexlist[art-1]+=brt_ix
        indexlist[brt-1]=a
        return
    else:
        return
        

for j in range(m):
    a1=a[j]
    b1=b[j]
    merge(a1,b1)

ans=min(indexlist)*(-1)
print(ans)

Submission status: Runtime Error

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

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


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

uf = UnionFind(n+1)

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

ans = 1
for i in range(1, n+1):
    ans = max(ans, uf.size(i))

print(ans)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
G = [[] for i in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)

chk = [0 for i in range(N)]
L = [0 for i in range(N)]
def search(G,v,cnt,L,chk):
    chk[v]=1
    L[v]=cnt
    for tmp in G[v]:
        if chk[tmp]!=0:
            continue
        search(G,tmp,cnt,L,chk)

cnt = 0
for i in range(N):
    if chk[i]!=0:
        continue
    cnt += 1
    search(G,i,cnt,L,chk)

ans = 0

for c in range(cnt):
    res = 0
    for i in range(N):
        if (c+1)==L[i]:
            res +=1
    ans =max(ans,res)

print(ans)

Submission status: Runtime Error

Solution code:
import collections
n, m = map(int, input().split())
par = [i for i in range(n + 5)]
# print(par)
s = list()


# union find(parには0も入れているので、par[1]=1になる)
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]


def union(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    else:
        par[x] = y


# 各要素をunionする
for j in range(m):
    a, b = map(int, input().split())
    union(a - 1, b - 1)

s = [0 for i in range(n + 5)]

# 1～nの親を探してsに入れていき、一番多い親を答えにする
for k in range(n):
    s[find(k)] += 1

print(max(s))

Submission status: Runtime Error

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


root = list(range(n + 1))


from collections import defaultdict
d = defaultdict(set)



def find(i):
    if i == root[i]:
        return i
    root[i] = find(root[i])
    return root[i]

def union(u, v):
    fu, fv = find(u), find(v)
    if fu == fv:
        d[min(fu, fv)].add(max(u, v))
        return
    root[max(u, v)] = min(fu, fv)
    # root[u] = fv
    d[min(fu, fv)].add(max(u, v))



for i in range(m):
    u, v = map(int, input().split())
    union(u, v)



# print(d)
print(max(map(len, d.values())) + 1)

Submission status: Runtime Error

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


root = list(range(n + 1))


from collections import Counter
d = Counter()



def find(i):
    if i == root[i]:
        return i
    root[i] = find(root[i])
    return root[i]

def union(u, v):
    fu, fv = find(u), find(v)
    if fu == fv:
        return
    root[max(u, v)] = min(fu, fv)
    # root[u] = fv
    d[min(fu, fv)] += 1



for i in range(m):
    u, v = map(int, input().split())
    union(u, v)



# print(d)
print(max(d.values()) + 1)

Submission status: Runtime Error

Solution code:
import collections
n, m = map(int, input().split())
par = [i for i in range(0,n+1)]
# print(par)
s = list()

# union find(parには0も入れているので、par[1]=1になる)
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
def union(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    else:
        par[x] = y

# 各要素をunionする
for j in range(m):
    a, b = map(int, input().split())
    union(a,b)

# 1～nの親を探してsに入れていき、一番多い親を答えにする
for k in range(1,n+1):
    s.append(find(k))
# print(s)
print(1)
# c = collections.Counter(s)
# print(max(c.values()))

Submission status: Runtime Error

Solution code:
import collections
n, m = map(int, input().split())
par = [i for i in range(0,n+1)]
# print(par)
s = list()

# union find(parには0も入れているので、par[1]=1になる)
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
def union(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    else:
        par[x] = y

# 各要素をunionする
for j in range(m):
    a, b = map(int, input().split())
    union(a,b)

# 1～nの親を探してsに入れていき、一番多い親を答えにする
for k in range(1,n+1):
    s.append(find(k))
# print(s)
c = collections.Counter(s)
print(max(c.values()))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split(" "))
g = [[] for i in range(n)]
vis = [False for j in range(n)]
count = 0


def dfs(r):
    global count
    vis[r] = True
    count += 1
    for v in g[r]:
        if not vis[v]:
            dfs(v)


def solve():
    global count
    mx = 0
    for i in range(n):
        if i not in vis:
            count = 0
            dfs(i)
            mx = max(mx, count)
    print(mx)

for j in range(m):
    a, b = map(int, input().split(" "))
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)
solve()

Submission status: Runtime Error

Solution code:
# 方針　union findで解く
n, m = map(int, input().split())  # 入力の受け取り
par = [i for i in range(1, n + 1)]  # 親のリストを作成


# find関数を作成。自分の値とリスト番号を比べ、親ならば返し、子ならば親を探す
# par[x-1]としているのは、例えばpar[0]=1になっているため
def find(x):
    if par[x - 1] == x:
        return x
    else:
        par[x - 1] = find(par[x - 1])
        return par[x - 1]


# union関数を作成。2つの引数の親を比べ、違う場合は一方の親を一方の子にする
def union(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    par[x - 1] = y


# 入力すべてでunionする
for j in range(m):
    a, b = map(int, input().split())
    union(a, b)


# n人の親を探して、リストsに入れ、それぞれ親の数をカウントし、最頻値をグループ数とする。
s = [find(i) for i in range(1, n + 1)]
print(1)
#import collections
#c = collections.Counter(s)
#print(max(c.values()))

Submission status: Runtime Error

Solution code:
# 方針　union findで解く
n, m = map(int, input().split())  # 入力の受け取り
par = [i for i in range(1, n + 1)]  # 親のリストを作成


# find関数を作成。自分の値とリスト番号を比べ、親ならば返し、子ならば親を探す
# par[x-1]としているのは、例えばpar[0]=1になっているため
def find(x):
    if par[x - 1] == x:
        return x
    else:
        par[x - 1] = find(par[x - 1])
        return par[x - 1]


# union関数を作成。2つの引数の親を比べ、違う場合は一方の親を一方の子にする
def union(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    par[x - 1] = y


# 入力すべてでunionする
for j in range(m):
    a, b = map(int, input().split())
    union(a, b)

# n人の親を探して、リストsに入れ、それぞれ親の数をカウントし、最頻値をグループ数とする。
s = [find(i) for i in range(1, n + 1)]
import collections
c = collections.Counter(s)
print(max(c.values()))

Submission status: Runtime Error

Solution code:
# 方針　union findで解く
n, m = map(int, input().split())  # 入力の受け取り
par = [i for i in range(1, n + 1)]  # 親のリストを作成


# find関数を作成。自分の値とリスト番号を比べ、親ならば返し、子ならば親を探す
# par[x-1]としているのは、例えばpar[0]=1になっているため
def find(x):
    if par[x - 1] == x:
        return x
    else:
        par[x - 1] = find(par[x - 1])
        return par[x - 1]


# union関数を作成。2つの引数の親を比べ、違う場合は一方の親を一方の子にする
def union(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    par[x - 1] = y


# 入力すべてでunionする
for j in range(m):
    a, b = map(int, input().split())
    union(a, b)

# n人の親を探して、リストsに入れ、それぞれ親の数をカウントし、最頻値をグループ数とする。
#s = [find(i) for i in range(1, n + 1)]
import collections
c = collections.Counter(s)
print(max(c.values()))

Submission status: Runtime Error

Solution code:
N,M=[int(a) for a in input().split()]
AB=list()
for i in range(M):
    AB.append([int(a) for a in input().split()])
#print(N,M,AB)

flists=list()
for pair in AB:
    list0=-1
    list1=-1
    for j,flist in enumerate(flists):
        if pair[0] in flist:
            list0=j
        if pair[1] in flist:
            list1=j
    if list0==-1 and list1==-1:
        flists.append(set([pair[0],pair[1]]))
    elif list0!=-1 and list1!=-1 and list0!=list1:
        flists[list0]=flist[list0]|flist[list1]
        flists.pop(list1)
    elif list0==-1 and list1!=-1:
        flists[list1].add(pair[0])
    elif list0!=-1 and list1==-1:
        flists[list0].add(pair[1])
#print(flists)

ans=1        
for flist in flists:
    l=len(flist)
    if l>ans:
        ans=l

print(ans)

Submission status: Runtime Error

Solution code:
# 方針　union findで解く
n, m = map(int, input().split()) # 入力の受け取り
par = [i for i in range(1,n+1)] # 親のリストを作成

# find関数を作成。自分の値とリスト番号を比べ、親ならば返し、子ならば親を探す
# par[x-1]としているのは、例えばpar[0]=1になっているため
def find(x):
    if par[x-1] == x:
        return x
    else:
        par[x-1] = find(par[x-1])
        return par[x-1]
    
# union関数を作成。2つの引数の親を比べ、違う場合は一方の親を一方の子にする
def union(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    par[x-1] = y

# 入力すべてでunionする
for j in range(m):
    a,b = map(int, input().split())
    union(a,b)

# n人の親を探して、リストsに入れ、それぞれ親の数をカウントし、最頻値をグループ数とする。
s = [find(i) for i in range(1,n+1)]
import collections
c = collections.Counter(s)
print(max(c.values()))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
par = [i for i in range(1,n+1)]
def find(x):
    if par[x-1] == x:
        return x
    else:
        par[x-1] = find(par[x-1])
        return par[x-1]
def union(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    par[x-1] = y
for j in range(m):
    a,b = map(int, input().split())
    union(a,b)
# print(par)
s = [find(i) for i in range(1,n+1)]
import collections
c = collections.Counter(s)
print(max(c.values()))

Submission status: Runtime Error

Solution code:
from collections import defaultdict

def main():
    N, M = map(int, input().split())
    g = defaultdict(set)

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

    from functools import lru_cache
    def dfs(u, visited: set):
        visited.add(u)
        for v in g[u]:
            if v not in visited:
                dfs(v, visited)

    count = dict()       
    for u in range(N):
        if u in count:
            continue
        visited = set()
        dfs(u, visited)
        # print(visited)
        count[u] = len(visited)
        for v in visited:
            count[v] = len(visited)

    print(max(count.values()))


if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10000)
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict

def main():
    N, M = map(int, input().split())
    g = defaultdict(set)

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

    from functools import lru_cache
    def dfs(u, visited: set):
        visited.add(u)
        for v in g[u]:
            if v not in visited:
                dfs(v, visited)

    count = dict()       
    for u in range(N):
        if u in count:
            continue
        visited = set()
        dfs(u, visited)
        # print(visited)
        count[u] = len(visited)
        for v in visited:
            count[v] = len(visited)

    print(max(count.values()))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
n, m = map(int, input().split())
info = [tuple(map(int, s.split())) for s in sys.stdin.readlines()]

pars = [-1]*n

def get_root(x):
    if pars[x] < 0:
        return x
    else:
        pars[x] = get_root(pars[x])
        return pars[x]

def combine(x, y):
    if x == y:
        return
    r_x = get_root(x)
    r_y = get_root(y)
    if r_x > r_y:
        r_x, r_y = r_y, r_x
    if r_x != r_y:
        pars[r_x] += pars[r_y] # 足して経路長を求めるのに使う
        pars[r_y] = r_x

def size(x):
    return -pars[get_root(x)]

for x, y in info:
    combine(x, y)

print(-min(pars))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
info = [tuple(map(int, s.split())) for s in sys.stdin.readlines()]

pars = [-1]*n

def get_root(x):
    if pars[x] < 0:
        return x
    else:
        return get_root(pars[x])


def combine(x, y):
    if x == y:
        return
    r_x = get_root(x)
    r_y = get_root(y)
    if r_x > r_y:
        r_x, r_y = r_y, r_x
    if r_x != r_y:
        pars[r_x] += pars[r_y] # 足して経路長を求めるのに使う
        pars[r_y] = r_x

def size(x):
    return -pars[get_root(x)]

for x, y in info:
    combine(x, y)

print(-min(pars))

Submission status: Runtime Error

Solution code:
nm = input().split(" ")
n = int(nm[0])
m = int(nm[1])

pars = [-1]*n

def get_root(x):
    if pars[x] < 0:
        return x
    else:
        return get_root(pars[x])


def combine(x, y):
    if x == y:
        return
    r_x = get_root(x)
    r_y = get_root(y)
    if r_x > r_y:
        r_x, r_y = r_y, r_x
    if r_x != r_y:
        pars[r_x] += pars[r_y] # 足して経路長を求めるのに使う
        pars[r_y] = r_x

def size(x):
    return -pars[get_root(x)]

for i in range(m):
    pair = input().split(" ")
    x = int(pair[0]) - 1 # 入力が1スタートなので
    y = int(pair[1]) - 1 # 入力が1スタートなので
    combine(x, y)

max_len = 0
for i in range(n):
    len = size(i)
    if len > max_len:
        max_len = len

print(max_len)

Submission status: Runtime Error

Solution code:
nm = input().split(" ")
n = int(nm[0])
m = int(nm[1])

pars = [-1]*n

def get_root(x):
    if pars[x] < 0:
        return x
    else:
        return get_root(pars[x])


def combine(x, y):
    r_x = get_root(x)
    r_y = get_root(y)
    if r_x > r_y:
        r_x, r_y = r_y, r_x
    if r_x != r_y:
        pars[r_x] += pars[r_y] # 足して経路長を求めるのに使う
        pars[r_y] = r_x

def size(x):
    return -pars[get_root(x)]

for i in range(m):
    pair = input().split(" ")
    x = int(pair[0]) - 1 # 入力が1スタートなので
    y = int(pair[1]) - 1 # 入力が1スタートなので
    combine(x, y)

max_len = 0
for i in range(n):
    len = size(i)
    if len > max_len:
        max_len = len

print(max_len)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
tomo =[]
a = list(map(int,input().split()))
tomo += a
for i in range(m-1):
    a,b=map(int,input().split())
    for j in range(len(tomo)):
        if(a == tomo[j] or b == tomo[j]):
            tomo.append(a)
            tomo.append(b)
ans = set(tomo)
print(len(ans))

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
tomo =[]
a = list(map(int,input().split()))
tomo += a
for i in range(m-1):
    a,b=map(int,input().split())
    for j in range(len(tomo)):
        if(a == tomo[j] or b == tomo[j]):
            tomo.append(a)
            tomo.append(b)
ans = set(tomo)
#print(ans)
print(len(ans))

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
tomo =[]
a = list(map(int,input().split()))
tomo += a
for i in range(m-1):
    a,b=map(int,input().split())
    for j in range(len(tomo)):
        if(a == tomo[j] or b == tomo[j]):
            tomo.append(a)
            tomo.append(b)
ans = set(tomo)
print(ans)
print(len(ans))

Submission status: Runtime Error

Solution code:
'''
	We can show that if u and v belong to the same connected component, then they are friends w/ each other
	So everyone in a given connected component is friends with one another
	So everyone in a given connected component must be separated into different groups

	If we have a CC of with sz nodes in it, then we need at least sz different groups

	So, the minimum number of groups needed is max sz(CC)
'''
import sys
sys.setrecursionlimit(2*10**5)

n, m = map(int,input().split())
adj = [[] for u in range(n+1)]
for i in range(m):
	u, v = map(int,input().split())
	adj[u].append(v)
	adj[v].append(u)

vis = [False for u in range(n+1)]
def dfs(u):
	if vis[u]:
		return 0
	vis[u] = True

	sz = 1
	for v in adj[u]:
		sz += dfs(v)
	return sz

CCs = []
for u in range(1,n+1):
	if not vis[u]:
		CCs.append(dfs(u))

print(max(CCs))

Submission status: Runtime Error

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

group_list = []
group_index = [0] * N

for _ in range(M):
    a, b = map(int, input().split())
    if group_index[a-1] == 0 and group_index[b-1] == 0:
        group_index[a-1] = len(group_list) + 1
        group_index[b-1] = len(group_list) + 1
        group_list.append(set([a, b]))

    elif group_index[a-1] == 0:
        group_index[a-1] = group_index[b-1]
        group_list[group_index[b-1] - 1].add(a)

    elif group_index[b-1] == 0:
        group_index[b-1] = group_index[a-1]
        group_list[group_index[a-1] - 1].add(b)

    elif group_index[a-1] != group_index[b-1]:
        group_id_b = group_index[b-1] - 1
        for p in group_list[group_id_b]:
            group_index[p-1] = group_index[a-1]
            group_list[group_index[a-1] - 1].add(p)
        group_list[group_id_b].clear()

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

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
ans=0
relationships = [list(map(int, input().split())) for i in range(m)]
for i in range(m):
    relationships[i].sort()

relationships.sort()
groups = []
groups.append(set(relationships[0]))
for i in range(1, m):
    for j in range(len(groups)):
        if relationships[i][0] in groups[j]:
            groups[j].add(relationships[i][1])
        elif relationships[i][1] in groups[j]:
            groups[j].add(relationships[i][0])
        else:
            groups.append(set(relationships[i]))

for group in groups:
    ans=max(ans, len(group))

print(ans)

Submission status: Runtime Error

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

group_list = []

group_index = [0] * N

last_group = 1

for a, b in zip(A, B):
    if group_index[a-1] == 0 and group_index[b-1] == 0:
        group_index[a-1] = last_group
        group_index[b-1] = last_group
        group_list.append(set([a, b]))
        last_group += 1
    elif group_index[a-1] == 0:
        group_index[a-1] = group_index[b-1]
        group_list[group_index[b-1] - 1].add(a)
    elif group_index[b-1] == 0:
        group_index[b-1] = group_index[a-1]
        group_list[group_index[b-1] - 1].add(b)
    elif group_index[a-1] != group_index[b-1]:
        for p in group_list[group_index[b-1] - 1]:
            group_index[p - 1] = group_index[a-1]
            group_list[group_index[a-1] - 1].add(p)
        group_list[group_index[b-1] - 1] = set()

#print(group_index)
#print(group_list)


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

Submission status: Runtime Error

Solution code:
import sys
class UnionFind():
    def __init__(self, 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


N, M = map(int, input().split())
info = [tuple(map(int, s.split())) for s in sys.stdin.readlines()]
#print(info)

uf = UnionFind(N)

for a, b in info:
    a -= 1; b -= 1
    uf.union(a, b)

#ans = min(uf.parents)

print(-ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from itertools import combinations

N, M = map(int, input().split())
A = []
B = []
for _ in range(M):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

group_list = []

#D = defaultdict(set)
for a, b in zip(A, B):
    if len(group_list) == 0:
        group_list.append(set([a, b]))
    else:
        flag = True
        for g in group_list:
            if a in g:
                g.add(b)
                flag = False
                break
            if b in g:
                g.add(a)
                flag = False
                break
        if flag:
            group_list.append(set([a, b]))

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

Submission status: Runtime Error

Solution code:
import collections

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

A = [0] * n

mamimum = 1

B = []
C = []

for i in range(m):
    b, c = map(int, input().split())
    B.append(b)
    C.append(c)

D = zip(B, C)
D = sorted(D)
B, C = zip(*D)

for i, j in zip(B, C):
    i -= 1
    j -= 1
    if A[i] == 0 and A[j] == 0:
        A[i] = mamimum
        A[j] = mamimum
        mamimum += 1
    elif A[i] == 0:
        A[i] = A[j]
    elif A[j] == 0:
        A[j] = A[i]

D = collections.Counter(A)
print(max(D.values()))

Submission status: Runtime Error

Solution code:
'''
	We can show that if u and v belong to the same connected component, then they are friends w/ each other
	So everyone in a given connected component is friends with one another
	So everyone in a given connected component must be separated into different groups

	If we have a CC of with sz nodes in it, then we need at least sz different groups

	So, the minimum number of groups needed is max sz(CC)
'''
import sys
sys.setrecursionlimit(4e5)

n, m = map(int,input().split())
adj = [[] for u in range(n+1)]
for i in range(m):
	u, v = map(int,input().split())
	adj[u].append(v)
	adj[v].append(u)

vis = [False for u in range(n+1)]
def dfs(u):
	if vis[u]:
		return 0
	vis[u] = True

	sz = 1
	for v in adj[u]:
		sz += dfs(v)
	return sz

CCs = []
for u in range(1,n+1):
	if not vis[u]:
		CCs.append(dfs(u))

print(max(CCs))

Submission status: Runtime Error

Solution code:
'''
	We can show that if u and v belong to the same connected component, then they are friends w/ each other
	So everyone in a given connected component is friends with one another
	So everyone in a given connected component must be separated into different groups

	If we have a CC of with sz nodes in it, then we need at least sz different groups

	So, the minimum number of groups needed is max sz(CC)
'''
n, m = map(int,input().split())
adj = [[] for u in range(n+1)]
for i in range(m):
	u, v = map(int,input().split())
	adj[u].append(v)
	adj[v].append(u)

vis = [False for u in range(n+1)]
def dfs(u):
	if vis[u]:
		return 0
	vis[u] = True

	sz = 1
	for v in adj[u]:
		sz += dfs(v)
	return sz

CCs = []
for u in range(1,n+1):
	if not vis[u]:
		CCs.append(dfs(u))

print(max(CCs))

Submission status: Runtime Error

Solution code:
N,M = tuple(map(int,input().split()))
# matchlist = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(M)]
#最大のグループの大きさを出す
friendlist = list(range(N))
# [所属先,[所属メンバー]]
gplist = [[i] for i in range(N)]

def getgroup(a):
    A = friendlist[a]
    if A == a:
        return a
    else:
        return getgroup(A)

def match(ab):
    A = getgroup(ab[0])
    B = getgroup(ab[1])
    if A==B:
        return
    else:
        gplist[A].extend(gplist[B])
        friendlist[B] = A

for i in range(M):
    # print(friendlist)
    # print(gplist)
    match(tuple(map(lambda x:int(x)-1,input().split())))

# print(friendlist)
# print(gplist)

print(max([len(item) for item in gplist]))

Submission status: Runtime Error

Solution code:
from collections import Counter

# 再帰回数のエラー？と思われるので再帰上限を変更 10**3 → 10**9
# 変更したら RE がなくなったのでおそらくこれのせいで通らなかった
import sys
sys.setrecursionlimit(10 ** 9)

lst = [n for n in range(N)] # 初期値はすべてがそれぞれ根である状態

def get_root(x):    # 根を得る関数
    if lst[x] == x: # それ自身が根である場合
        return x
    else:   # 根が別のものである場合
        lst[x] = get_root(lst[x])   # 経路圧縮あり (ある種「メモ再帰化」)
        return lst[x]
        # return get_root(lst[x]) # 経路圧縮なし (わかりやすい，ただの再帰関数) → ちなみにこれだとTLEになってしまった．

def unite(x, y):    # 集合の連結を行う関数
    root_x = get_root(x)
    root_y = get_root(y)
    if root_x != root_y:    # 根が違う (=異なる集合) ならば
        lst[root_x] = root_y

def main(N, M, C):
    {unite(*c) for c in C}  # 集合の連結を行う．
    print(max(Counter(map(get_root, lst)).values()))    # 一番大きい集合の大きさを得る．


if __name__ == '__main__':
    N, M = list(map(int, input().split()))
    C = set()
    for _ in range(M):
        C.add(tuple(map(lambda x:int(x)-1, input().split())))   # pythonのindexに合わせるために "-1"
    main(N, M, C)

Submission status: Runtime Error

Solution code:
n, m =map(int,input().split())
l = [{int(x) for x in input().split()}]
ans = 0
for _ in range(m-1):
    a = {int(x) for x in input().split()}
    for j, s in enumerate(l):
        if s & a:
            l[j] |= a
            ans = max(ans, len(l[j]))
            if ans >= n:
                print(ans)
                exit()
            break
    else:
        l.append(a)
print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter

def main(N, M, C):
    lst = [n for n in range(N)] # 初期値はすべてがそれぞれ根である状態

    def get_root(x):    # 根を得る関数
        if lst[x] == x: # それ自身が根である場合
            return x
        else:   # 根が別のものである場合
            lst[x] = get_root(lst[x])   # 経路圧縮あり (ある種「メモ再帰化」)
            return lst[x]
            # return get_root(lst[x]) # 経路圧縮なし (わかりやすい，ただの再帰関数)

    def unite(x, y):    # 集合の連結を行う関数
        root_x = get_root(x)
        root_y = get_root(y)
        if root_x != root_y:    # 根が違う (=異なる集合) ならば
            lst[root_x] = root_y

    {unite(*c) for c in C}  # 集合の連結を行う．

    print(max(Counter(map(get_root, lst)).values()))


if __name__ == '__main__':
    N, M = list(map(int, input().split()))
    C = set()
    for _ in range(M):
        C.add(tuple(map(lambda x:int(x)-1, input().split())))   # pythonのindexに合わせるために "-1"
    main(N, M, C)

Submission status: Runtime Error

Solution code:
from collections import Counter

def main(N, M, C):
    lst = [n for n in range(N)] # 初期値はすべてがそれぞれ根である状態

    def get_root(x):    # 根を得る関数
        if lst[x] == x: # それ自身が根である場合
            return x
        else:   # 根が別のものである場合
            # lst[x] = get_root(lst[x])   # 経路圧縮あり (ある種「メモ再帰化」)
            # return lst[x]
            return get_root(lst[x]) # 経路圧縮なし (わかりやすい，ただの再帰関数)

    def unite(x, y):    # 集合の連結を行う関数
        root_x = get_root(x)
        root_y = get_root(y)
        if root_x != root_y:    # 根が違う (=異なる集合) ならば
            lst[root_x] = root_y

    {unite(*c) for c in C}  # 集合の連結を行う．

    print(max(Counter(map(get_root, lst)).values()))


if __name__ == '__main__':
    N, M = list(map(int, input().split()))
    C = set()
    for _ in range(M):
        C.add(tuple(map(lambda x:int(x)-1, input().split())))   # pythonのindexに合わせるために "-1"
    main(N, M, C)

Submission status: Runtime Error

Solution code:
n, m =map(int,input().split())
l = [{int(x) for x in input().split()}]
ans = 0
for _ in range(m-1):
    a = {int(x) for x in input().split()}
    for j, s in enumerate(l):
        if s & a:
            l[j] |= a
            break
    else:
        l.append(a)
for s in l:
    ans = max(ans, len(s))
print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
group = [set() for _ in range(n+1)]
for _ in range(m):
  a, b = map(int, input())
  group[a].add(b)
  group[b].add(a)

lst = [True] * (n+1)
ans = 0
for i in range(1, n+1):
  if lst[i]:
    friends = group[i]
    for friend in group[i]:
      friends = friends | group[friend]
      lst[friend] = False
    cnt = len(friends)
    ans = max(ans, cnt)
print(ans)