Problem:


Score : 400 points

Problem Statement

There are N cities. There are also K roads and L railways, extending between the cities.
The i-th road bidirectionally connects the p_i-th and q_i-th cities, and the i-th railway bidirectionally connects the r_i-th and s_i-th cities.
No two roads connect the same pair of cities. Similarly, no two railways connect the same pair of cities.

We will say city A and B are connected by roads if city B is reachable from city A by traversing some number of roads. Here, any city is considered to be connected to itself by roads.
We will also define connectivity by railways similarly.

For each city, find the number of the cities connected to that city by both roads and railways.

Constraints

2 ≦ N ≦ 2*10^5

1 ≦ K, L≦ 10^5

1 ≦ p_i, q_i, r_i, s_i ≦ N

p_i < q_i

r_i < s_i

When i ≠ j, (p_i, q_i) ≠ (p_j, q_j)

When i ≠ j, (r_i, s_i) ≠ (r_j, s_j)

Input

The input is given from Standard Input in the following format:

N K L
p_1 q_1
:
p_K q_K
r_1 s_1
:
r_L s_L

Output

Print N integers. The i-th of them should represent the number of the cities connected to the i-th city by both roads and railways.

Sample Input 1

4 3 1
1 2
2 3
3 4
2 3

Sample Output 1

1 2 2 1

All the four cities are connected to each other by roads.

By railways, only the second and third cities are connected. Thus, the answers for the cities are 1, 2, 2 and 1, respectively.

Sample Input 2

4 2 2
1 2
2 3
1 4
2 3

Sample Output 2

1 2 2 1

Sample Input 3

7 4 4
1 2
2 3
2 5
6 7
3 5
4 5
3 4
6 7

Sample Output 3

1 1 2 1 2 2 2



Sample input:
4 3 1
1 2
2 3
3 4
2 3


Sample output:
1 2 2 1

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n
 
    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            # 経路の圧縮
            self.table[x] = self._root(self.table[x])
            return self.table[x]
 
    def find(self, x, y):
        return self._root(x) == self._root(y)
 
    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2

if __name__ == "__main__":
    N,K,L = map(int,input().split())
    pq = []
    rs = []
    for i in range(K):
        pq.append(list(map(int,input().split())))
    for i in range(L):
        rs.append(list(map(int,input().split())))
    
    uf_d = UnionFind(N)
    uf_t = UnionFind(N)

    for i in pq:
        uf_d.union(i[0]-1,i[1]-1)

    for i in rs:
        uf_t.union(i[0]-1,i[1]-1)
    
    dic = {}
    
    for i in range(N):
        tmp = (uf_d._root(i),uf_t._root(i))
        #print(tmp)
        if tmp in dic:
            dic[tmp] += 1
        else:
            dic[tmp] = 1
    
    res = []

    for i in range(N):
        tmp = (uf_d._root(i),uf_t._root(i))
        res.append(dic[tmp])
    
    print(*res)

Submission status: Accepted

Solution code:
#UnionFindクラス
class UnionFind(object):

  def __init__(self, n=1):
    self.par = [i for i in range(n)]
    self.rank = [0 for _ in range(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]
  
  # xとyの根を結合させる
  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x != y:
      if self.rank[x] < self.rank[y]:
        x, y = y, x
      if self.rank[x] == self.rank[y]:
        self.rank[x] += 1
      self.par[y] = x
  
  # x,yの根が同じかどうかを返す（根が同じ:True、根が異なる:False）
  def is_same(self, x, y):
    return self.find(x) == self.find(y)

n,k,l = map(int,input().split())
    
uf_road = UnionFind(n)
uf_rail = UnionFind(n)
for i in range(k):
  tmp1,tmp2 = map(int,input().split())
  uf_road.union(tmp1-1,tmp2-1)
  
for i in range(l):
  tmp1,tmp2 = map(int,input().split())
  uf_rail.union(tmp1-1,tmp2-1)

memo = {}
for i in range(n):
  if str(uf_rail.find(i))+" "+str(uf_road.find(i)) not in memo:
    memo[str(uf_rail.find(i))+" "+str(uf_road.find(i))] = 1
  else:
    memo[str(uf_rail.find(i))+" "+str(uf_road.find(i))] += 1

for i in range(n):
  print(memo[str(uf_rail.find(i))+" "+str(uf_road.find(i))])

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
from collections import defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


n, k, l = LI()

# UnionFind
class UnionFind:
    # 負: ルートで値は木の深さを表す
    # 正: 子で値は次のノードを表す
    def __init__(self, size: int) -> None:
        self.nodes = [-1] * size  # 初期状態では全てのノードがルート

    def find(self, x: int) -> int:
        if self.nodes[x] < 0:
            return x
        else:
            self.nodes[x] = self.find(self.nodes[x])
            return self.nodes[x]

    def unite(self, x: int, y: int) -> None:
        root_x, root_y = self.find(x), self.find(y)
        if root_x != root_y:
            if self.nodes[root_x] != self.nodes[root_y]:  # グラフの高さが異なる場合
                # 木のランクが高い方のルートに併合させる
                # 併合後にランクの変動はない
                if self.nodes[root_x] < self.nodes[root_y]:
                    self.nodes[root_y] = root_x
                else:
                    self.nodes[root_x] = root_y
            else:
                # ランクが等しい木同士を併合させるので
                # 併合後は木のランクが1つ上がる
                self.nodes[root_x] += -1
                self.nodes[root_y] = root_x


ufa = UnionFind(n)
ufb = UnionFind(n)

for _ in range(k):
    a, b = LI_()
    ufa.unite(a, b)
for _ in range(l):
    a, b = LI_()
    ufb.unite(a, b)

cnt = defaultdict(int)
keys = []
for i in range(n):
    key = (ufa.find(i), ufb.find(i))
    cnt[key] += 1
    keys.append(key)

print(*[cnt[key] for key in keys])

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)] #親
        self.rank = [0 for _ in range(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]

    #xとyの属する集合のマージ
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            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, K, L = map(int, input().split())
    
p = [list(map(int, input().split())) for _ in range(K)]

r = [list(map(int, input().split())) for _ in range(L)]

res = [1 for _ in range(N)]
    
load = UnionFind(N)
train = UnionFind(N)

for i in range(K):
    load.unite(p[i][0]-1, p[i][1]-1)
    
for i in range(L):
    train.unite(r[i][0]-1, r[i][1]-1)
    
    
dic= {}
for i in range(N):
    tmp = (load.find(i), train.find(i))
    if tmp in dic:
        dic[tmp] += 1
    else:
        dic[tmp] = 1

        
for i in range(N):
    tmp = (load.find(i), train.find(i))
    res[i] = dic[tmp]
    
result = ''
for i in range(N):
    result += str(res[i]) + ' '
    
print(result)

Submission status: Accepted

Solution code:
class UnionFind():
    n=1
    par=[0]
    rnk=[0]
    def __init__(self,size):
        self.n=size
        self.par=[0 for i in range(self.n)]
        self.rnk=[0 for i in range(self.n)]
        for i in range(self.n):
            self.par[i]=i
            self.rnk[i]=0
    def find(self,vertex1):
        if self.par[vertex1]==vertex1:
            return vertex1
        else:
            self.par[vertex1]=self.find(self.par[vertex1])
            return self.par[vertex1]
    def unite(self,vertex1,vertex2):
        vertex1=self.find(vertex1)
        vertex2=self.find(vertex2)
        if vertex1==vertex2:
            return
        if (self.rnk[vertex1]<self.rnk[vertex2]):
            self.par[vertex1]=vertex2
        else:
            self.par[vertex2]=vertex1
            if(self.rnk[vertex1]==self.rnk[vertex2]):
                self.rnk[vertex1]+=1
    def same(self,vetrex1,vertex2):
        return self.find(vetrex1)==self.find(vertex2)
N,K,L=map(int,input().split())
road=UnionFind(N)
train=UnionFind(N)
for i in range(K):
    p,q=map(int,input().split())
    road.unite(p-1,q-1)
for i in range(L):
    r,s=map(int,input().split())
    train.unite(r-1,s-1)
X=[(road.find(i),train.find(i)) for i in range(N)]
D=dict()
for i in range(N):
    if not(X[i] in D):
        D[X[i]]=0
    D[X[i]]+=1
ans=[D[X[i]] for i in range(N)]
print(" ".join([str(i) for i in ans]))

Submission status: Accepted

Solution code:
n,k,l=map(int,input().split())
road=[list(map(int,input().split())) for _ in range(k)]
rail=[list(map(int,input().split())) for _ in range(l)]

class UnionFind:
    def __init__(self,n):
        self.par=[i for i in range(n+1)]
        self.rank=[0]*(n+1)
    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 x==y:
            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
    def same_check(self,x,y):
        return self.find(x)==self.find(y)

from collections import Counter
uf_road=UnionFind(n)
uf_rail=UnionFind(n)
ans=0
for i,j in road:
    uf_road.union(i-1,j-1)
for i,j in rail:
    uf_rail.union(i-1,j-1)
pairs=[None]*n
for i in range(n):
    pairs[i]=(uf_road.find(i), uf_rail.find(i))
cnt=Counter(pairs)
ans=[]
for i in range(n):
    ans.append(cnt[pairs[i]])
print(' '.join(map(str,ans)))

Submission status: Accepted

Solution code:
from collections import Counter

def dfs(r, c, g, color):
    s = [r]
    color[r] = c
    while len(s) != 0:
        u = s.pop()
        for i in range(len(g[u])):
            v = g[u][i]
            if color[v] is None:
                color[v] = c
                s.append(v)


def assignColor(n, g, color):
    color_id = 1
    for u in range(n):
        if color[u] is None:
            dfs(u, color_id, g, color)
            color_id += 1


N, K, L = [int(v) for v in input().split()]
road = [[] for i in range(N)]
train = [[] for i in range(N)]
for i in range(K):
    p, q = [int(v) - 1 for v in input().split()]
    road[p].append(q)
    road[q].append(p)
for i in range(L):
    r, s = [int(v) - 1 for v in input().split()]
    train[r].append(s)
    train[s].append(r)

road_color = [None] * N
train_color = [None] * N
assignColor(N, road, road_color)
assignColor(N, train, train_color)

color_pairs = [(c1, c2) for c1, c2 in zip(road_color, train_color)]
pairs_cnt = Counter(color_pairs)
ans = [str(pairs_cnt[p]) for p in color_pairs]

print(' '.join(ans))

Submission status: Accepted

Solution code:
from collections import defaultdict as dd

class UnionFind(object):
    def __init__(self,n):
        self.parent={i:i for i in range(1,n+1)}
        self.size={i:1 for i in range(1,n+1)}
    def find(self,a):
        if self.parent[a]!=a:
            self.parent[a]=self.find(self.parent[a])
        return self.parent[a]
    def unite(self,a,b):
        a=self.find(a)
        b=self.find(b)
        if a==b:return
        if self.size[a]>self.size[b]:
            self.size[a]+=self.size[b]
            self.parent[b]=a
        else:
            self.size[b]+=self.size[a]
            self.parent[a]=b
    def isunited(self,a,b):
        return self.find(a)==self.find(b)

n,k,l=map(int,input().split())
uft_road=UnionFind(n)
uft_train=UnionFind(n)

for _ in range(k):
    p,q=map(int,input().split())
    uft_road.unite(p,q)

for _ in range(l):
    r,s=map(int,input().split())
    uft_train.unite(r,s)

dc=dd(int)
du={}
for i in range(1,n+1):
    du[i]=(uft_road.find(i),uft_train.find(i))
    dc[du[i]]+=1

print(*(dc[du[i]] for i in range(1,n+1)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)
class UnionFind:
    def __init__(self, n):
        self.p=[i for i in range(n)]
        self.r=[0 for i in range(n)]
    
    def root(self,x):
        if self.p[x]==x:
            return x
        else:
            self.p[x] = self.root(self.p[x])
            return self.p[x]
    
    def uni(self,x,y):
        x=self.root(x)
        y=self.root(y)
        if(x==y):
            return
        if self.r[x]<self.r[y]:
            self.p[x]=y
        else:
            self.p[y]=x
            if self.r[x]==self.r[y]:
                self.r[x]+=1
    
    def same(self,x,y):
        return self.root(x)==self.root(y)

n,k,l=map(int,input().split())
uf_d=UnionFind(n)
uf_m=UnionFind(n)
for i in range(k):
    a,b=map(int,input().split())
    uf_d.uni(a-1,b-1)
for i in range(l):
    a,b=map(int,input().split())
    uf_m.uni(a-1,b-1)

dic={}
d=[]
for i in range(n):
    ky=(uf_d.root(i),uf_m.root(i))
    if ky in dic:
        dic[ky]+=1
    else:
        dic[ky]=1
    d.append(ky)
for i in range(n):
    print(dic[d[i]],end=' 'if i!=n-1 else '\n')

Submission status: Accepted

Solution code:
from collections import Counter


class UnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n + 1)]

    def root(self, i):
        if self.parents[i] == i:
            return i
        else:
            self.parents[i] = self.root(self.parents[i])
            return self.parents[i]

    def unite(self, i, j):
        self.parents[self.root(self.parents[i])] = self.root(j)

    def is_unite(self, i, j):
        return self.root(i) == self.root(j)


def solve(N, K, L, PQs, RSs):
    road_cities = UnionFind(N)
    train_cities = UnionFind(N)

    for p, q in PQs:
        road_cities.unite(p, q)
    for r, s in RSs:
        train_cities.unite(r, s)

    counts = Counter([
        (road_cities.root(i), train_cities.root(i))
        for i in range(1, N + 1)
    ])

    ans = [
        counts[(road_cities.root(i), train_cities.root(i))]
        for i in range(1, N + 1)
    ]

    return " ".join([str(c) for c in ans])


if __name__ == "__main__":
    N, K, L = map(int, input().split(" "))
    PQs = []
    RSs = []
    for _ in range(K):
        PQs.append(tuple(map(int, input().split(" "))))
    for _ in range(L):
        RSs.append(tuple(map(int, input().split(" "))))
    print(solve(N, K, L, PQs, RSs))

Submission status: Accepted

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

"""
参考：https://img.atcoder.jp/arc065/editorial.pdf
・Union-Find木
"""

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

from collections import Counter

# Union-Find木
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        # 1-indexedのままでOK、その場合は[0]は未使用
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0）
        self.rank = [0] * (n+1)

    # 検索
    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
            # 木の高さが同じなら片方を1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

N, K, L = map(int, input().split())
uf1 = UnionFind(N)
uf2 = UnionFind(N)
for i in range(K):
    p, q = map(int, input().split())
    uf1.union(p, q)
for i in range(L):
    p, q = map(int, input().split())
    uf2.union(p, q)

# (道路グループ番号, 鉄道グループ番号) のペアを各都市について作る
pairs = [None] * N
for i in range(N):
    pairs[i] = (uf1.find(i+1), uf2.find(i+1))

# 同じ内容のペアについて数える
c = Counter(pairs)

ans = [0] * N
for i in range(N):
    # 自分のペアのカウント数を各都市について取得
    ans[i] = c[pairs[i]]
print(*ans)

Submission status: Accepted

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

def union(parents, x1, x2):
    y1 = find(parents, x1)
    y2 = find(parents, x2)
    if y1 != y2:
        parents[y1] = y2


n, k, l = map(int, input().split())

parents1 = list(range(n))
for _ in range(k):
    p, q = map(int, input().split())
    union(parents1, p - 1, q - 1)

parents2 = list(range(n))
for _ in range(l):
    r, s = map(int, input().split())
    union(parents2, r - 1, s - 1)

import collections

counter = collections.defaultdict(int)
for i in range(n):
    p1, p2 = find(parents1, i), find(parents2, i)
    counter[(p1, p2)] += 1

ans = ' '.join(str(counter[(find(parents1, i), find(parents2, i))]) for i in range(n))
print(ans)

Submission status: Accepted

Solution code:
import collections
N,K,L = map(int, input().split())
p = []
q = []
for i in range(K):#h:高さ
    pi, qi = map(int, input().split())
    p.append(pi)
    q.append(qi)
r = []
s = []
for i in range(L):#h:高さ
    ri, si = map(int, input().split())
    r.append(ri)
    s.append(si)

class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0）
        self.rank = [0] * (n + 1)

    # 検索
    # 根ならその番号を返す
    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
        # 木の高さが同じなら片方を1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

u = UnionFind(N)
for i in range(K):
    u.union(p[i],q[i])


u2 = UnionFind(N)
for i in range(L):
    u2.union(r[i],s[i])

li = [None]*(N)
liw = [None]*(N)
for i in range(N):
    li[i] = (u.find(i + 1), u2.find(i + 1), i + 1)
    liw[i] = (u.find(i + 1), u2.find(i + 1))
#li.sort(key=lambda x:(x[0], x[1]))

liws = collections.Counter(liw)

ansli = [0]*(N+1)
for i in range(N):
    ansli[i + 1] = liws[(li[i][0], li[i][1])]

for i in range(1, N + 1):
    print(ansli[i], "", end="")

Submission status: Accepted

Solution code:
N, K, L = [int(_) for _ in input().split()]


def find(a, x):
    stack = []
    while a[x] != x:
        stack += [x]
        x = a[x]
    while stack:
        a[stack.pop()] = x
    return x


def unite(a, x, y):
    x = find(a, x)
    y = find(a, y)
    if x != y:
        a[x] = min(x, y)
        a[y] = a[x]


a_road = [i for i in range(N)]
for _ in range(K):
    p, q = [int(_) - 1 for _ in input().split()]
    unite(a_road, p, q)
a_railway = [i for i in range(N)]
for _ in range(L):
    r, s = [int(_) - 1 for _ in input().split()]
    unite(a_railway, r, s)
memo = {}
for i in range(N):
    memo[a_road[i], a_railway[i]] = memo.get(
        (find(a_road, i), find(a_railway, i)), 0) + 1

print(' '.join(str(memo[a_road[i], a_railway[i]]) for i in range(N)))

Submission status: Accepted

Solution code:
N, K, L = [int(_) for _ in input().split()]


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


def unite(a, x, y):
    x = find(a, x)
    y = find(a, y)
    if x != y:
        a[x] = min(x, y)
        a[y] = a[x]


a_road = [i for i in range(N)]
for _ in range(K):
    p, q = [int(_) - 1 for _ in input().split()]
    unite(a_road, p, q)
a_railway = [i for i in range(N)]
for _ in range(L):
    r, s = [int(_) - 1 for _ in input().split()]
    unite(a_railway, r, s)
memo = {}
for i in range(N):
    memo[a_road[i], a_railway[i]] = memo.get(
        (find(a_road, i), find(a_railway, i)), 0) + 1

print(' '.join(str(memo[a_road[i], a_railway[i]]) for i in range(N)))

Submission status: Accepted

Solution code:
from collections import Counter
def find(x):
  if x==Tree[x]:
      return x
  else:
      Tree[x]=find(Tree[x])
      return Tree[x]
def unite(x,y):
  s1=find(x)
  s2=find(y)
  if s1!=s2:
    Tree[s2]=s1
def find2(x):
  if x==Tree2[x]:
      return x
  else:
      Tree2[x]=find2(Tree2[x])
      return Tree2[x]
def unite2(x,y):
  s1=find2(x)
  s2=find2(y)
  if s1!=s2:
    Tree2[s2]=s1
N,K,L=map(int,input().split())
Tree=[i for i in range(N)]
Tree2=[i for i in range(N)]
ans=[]
for i in range(K):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  unite(a,b)
for i in range(L):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  unite2(a,b)
l=[(find(i),find2(i)) for i in range(N)]
lc=Counter(l)
for i in range(N):
  ans.append(lc[l[i]])
print(" ".join(map(str,ans)))

Submission status: Accepted

Solution code:
from collections import defaultdict
N, K, L = map(int, input().split())


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size = [1] * 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 x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
            self.size[x] = 0
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

    # すべての頂点に対して親を検索する
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)


UF_road = UnionFind(N)
for k in range(K):
    p, q = map(int, input().split())
    p, q = p - 1, q - 1
    UF_road.union(p, q)
UF_road.all_find()

UF_train = UnionFind(N)
for l in range(L):
    r, s = map(int, input().split())
    r, s = r - 1, s - 1
    UF_train.union(r, s)
UF_train.all_find()

D = defaultdict(int)
for r, t in zip(UF_road.par, UF_train.par):
    D[(r, t)] += 1

ans = [D[(r, t)] for r, t in zip(UF_road.par, UF_train.par)]
print(*ans, sep=' ')

Submission status: Accepted

Solution code:
import sys
from collections import Counter

sys.setrecursionlimit(10 ** 5)


class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n + 1)]
        self.rank = [0 for _ in range(n + 1)]

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y

        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


N, K, L = map(int, input().split())
r_union_find = UnionFind(N)
t_union_find = UnionFind(N)
for i in range(K):
    p, q = map(int, input().split())
    r_union_find.union(p, q)

for i in range(L):
    r, s = map(int, input().split())
    t_union_find.union(r, s)

pair = []

for i in range(1, N + 1):
    count = 0
    r_p = r_union_find.find(i)
    t_p = t_union_find.find(i)
    pair.append((r_p, t_p))

counter = Counter(pair)

answers = []
for p in pair:
    answers.append(counter[p])

answers = map(str, answers)
print(" ".join(answers))

Submission status: Accepted

Solution code:
N, K, L = [int(_) for _ in input().split()]
V1 = [[int(_) - 1 for _ in input().split()] for i in range(K)]
V2 = [[int(_) - 1 for _ in input().split()] for i in range(L)]


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n + 1)]
        self.rank = [0] * (n + 1)

    # 検索
    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 x != 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

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


uf1 = UnionFind(N)
for p, q in V1:
    uf1.union(p, q)

uf2 = UnionFind(N)
for r, s in V2:
    uf2.union(r, s)

from collections import defaultdict
d = defaultdict(int)

for i in range(N):
    d[(uf1.find(i), uf2.find(i))] += 1

for i in range(N):
    print(d[(uf1.find(i), uf2.find(i))], end=' ')
print()

Submission status: Accepted

Solution code:
from collections import defaultdict
N,K,L = map(int,input().split())
 
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
    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 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
    def check(self, x, y):
        return self.find(x) == self.find(y)

# 道路
A = UnionFind(N)
for i in range(K):
    x,y = map(int,input().split())
    A.unite(x,y)

# 鉄道
B = UnionFind(N)
for i in range(L):
    x,y = map(int,input().split())
    B.unite(x,y)

dic = defaultdict(int)
for i in range(1,N+1):
    dic[A.find(i),B.find(i)] += 1

Ans = list(dic[A.par[i],B.par[i]] for i in range(1,N+1))
print(" ".join(map(str,Ans)))

Submission status: Accepted

Solution code:
class DisjointSet:
    def __init__(self):
        self.rank = {}
        self.p = {}

    def makeSet(self, x):
        self.p[x] = x
        self.rank[x] = 0

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

    def unite(self, x, y):
        self.link(self.findSet(x), self.findSet(y))

    def link(self, x, y):
        if(self.rank[x] > self.rank[y]):
            self.p[y] = x
        else:
            self.p[x] = y
            if(self.rank[x] == self.rank[y]):
                self.rank[y] += 1

    def findSet(self, x):
        if(x != self.p[x]):
            self.p[x] = self.findSet(self.p[x])
        return self.p[x]

from collections import Counter
N, K, L = map(int, input().split())

ds = DisjointSet()
ds2 = DisjointSet()
for i in range(N):
    ds.makeSet(i+1)
    ds2.makeSet(i+1)

for i in range(K):
    p, q = map(int, input().split())
    ds.unite(p, q)

for i in range(L):
    r, s = map(int, input().split())
    ds2.unite(r, s)

a = [(ds.findSet(i), ds2.findSet(i)) for i in range(1, N+1)]
c = Counter(a)

print(' '.join([str(c[i]) for i in a]))

Submission status: Accepted

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

#print(N,K,L,D,T)

class UnionFind:
    def __init__(self, n: int) -> None:
        #マイナスならルートでその深さを表す。プラスならルートのノードを指す。
        self.nodes = [-1]*n

    def find_root(self, x: int) -> int:
        if self.nodes[x] < 0:
            return x
        else:
            self.nodes[x] = self.find_root(self.nodes[x])
            return self.nodes[x]

    def unite(self, x: int, y: int) -> None:
        x, y = self.find_root(x), self.find_root(y)
        #浅い方につなぐ
        if (x != y):
            if (x < y):
                self.nodes[y] += self.nodes[x]
                self.nodes[x] = y
            else:
                self.nodes[x] += self.nodes[y]
                self.nodes[y] = x
        
    # 同じ集合に属するか判定
    #def same_check(self, x, y):
    #    return self.find(x) == self.find(y)

def uniteOne(num, uf):
    for _ in range(num):
        d0, d1 = map(int, input().split())
        uf.unite(d0-1, d1-1)
        
uf_D = UnionFind(N)
uf_T = UnionFind(N)

uniteOne(K, uf_D)
uniteOne(L, uf_T)

pairs = []
for i in range(N):
    pairs.append((uf_D.find_root(i), uf_T.find_root(i)))
 
pairs_count = {}
for p in pairs:
    if not p in pairs_count:
        pairs_count[p] = 1
    else:
        pairs_count[p] += 1
 
res = [0] * N
for i in range(N):
    res[i] = pairs_count[pairs[i]]
#print(*(res[i] for i in range(N)))
print(" ".join([str(i) for i in res]))

Submission status: Accepted

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

#print(N,K,L,D,T)

class UnionFind:
    def __init__(self, n: int) -> None:
        self.par = [i for i in range(n)]
        self.rank = [0] * n

    def find(self, x: int) -> int:
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x: int, y: int) -> None:
        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
        
    # 同じ集合に属するか判定
    #def same_check(self, x, y):
    #    return self.find(x) == self.find(y)

def uniteOne(num, uf):
    for _ in range(num):
        d0, d1 = map(int, input().split())
        uf.unite(d0-1, d1-1)
        
uf_D = UnionFind(N)
uf_T = UnionFind(N)

uniteOne(K, uf_D)
uniteOne(L, uf_T)

from collections import Counter

keys = []
counts = Counter()

for i in range(N):
    key = uf_D.find(i), uf_T.find(i)
    keys.append(key)
    counts[key] += 1

print(*(counts[key] for key in keys))

Submission status: Accepted

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

#print(N,K,L,D,T)

class UnionFind:
    def __init__(self, n: int) -> None:
        self.par = [i for i in range(n)]
        self.rank = [0] * n

    def find(self, x: int) -> int:
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x: int, y: int) -> None:
        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
        
    # 同じ集合に属するか判定
    #def same_check(self, x, y):
    #    return self.find(x) == self.find(y)

def uniteOne(num, uf):
    for _ in range(num):
        d0, d1 = map(int, input().split())
        uf.unite(d0-1, d1-1)
        
uf_D = UnionFind(N)
uf_T = UnionFind(N)

uniteOne(K, uf_D)
uniteOne(L, uf_T)

pairs = []
for i in range(N):
    pairs.append((uf_D.find(i), uf_T.find(i)))

pairs_count = {}
for p in pairs:
    if not p in pairs_count:
        pairs_count[p] = 1
    else:
        pairs_count[p] += 1

res = [0] * N
for i in range(N):
    res[i] = pairs_count[pairs[i]]
#print(*(res[i] for i in range(N)))
print(" ".join([str(i) for i in res]))