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.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

N,K,L = list(map(int,input().split()))
Network1 = UnionFind(N)  #道路
Network2 = UnionFind(N)  #鉄道

for i in range(K):
    p,q = list(map(int,input().split()))
    Network1.union(p-1,q-1)  #道路のペアを結合
for i in range(L):
    r,s = list(map(int,input().split()))
    Network2.union(r-1,s-1)  #鉄道のペアを結合

dam=[0]*N  #道路でのグループ_鉄道でのグループ
D = {}
for i in range(N):   #都市0~N-1がNetwork1,2で共に同じグループにいる都市の数見ていくよ
    X = Network1.find(i)  #道路グループでのiの所属
    Y = Network2.find(i)  #道路グループでのiの所属
    dam[i] = str(X) + "_" + str(Y)  #damに保存
    D[str(X) + "_" + str(Y)] = D.get(str(X) + "_" + str(Y), 0) + 1 #DにX_Yがあったらvalueに1足してD[X_Y]の辞書に追加     なかったら0をたす(何もしない)
    #都市  道路でのグループ  鉄道でのグループを調べていき、同じX_Yの個数をDに保存

out=[]
for i in range(N):
    out.append(D[dam[i]])  #都市iはX_Yであり、そのような歳が全部でいくつあるか

print(*out)

Submission status: Accepted

Solution code:
from collections import defaultdict

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


# union-findを実装
root_road = [-1] * N
root_train = [-1] * N


def find_road(x):
    if root_road[x] < 0:
        return x

    root_road[x] = find_road(root_road[x])
    return root_road[x]


def union_road(x, y):
    x = find_road(x)
    y = find_road(y)
    if x == y:
        return

    root_road[x] += root_road[y]
    root_road[y] = x


def same_road(x, y):
    return find_road(x) == find_road(y)


def find_train(x):
    if root_train[x] < 0:
        return x

    root_train[x] = find_train(root_train[x])
    return root_train[x]


def union_train(x, y):
    x = find_train(x)
    y = find_train(y)
    if x == y:
        return

    root_train[x] += root_train[y]
    root_train[y] = x


def same_train(x, y):
    return find_train(x) == find_train(y)


dc = defaultdict(list)
dt = defaultdict(list)
for _ in range(K):
    p, q = map(int, input().split())
    p -= 1
    q -= 1
    dc[p].append(q)
    dc[q].append(p)
    union_road(p, q)

for _ in range(L):
    r, s = map(int, input().split())
    r -= 1
    s -= 1
    dt[r].append(s)
    dt[s].append(r)
    union_train(r, s)

# print(root_road, root_train)
dic = {}
for i in range(N):
    if (find_road(i), find_train(i)) not in dic:
        dic[(find_road(i), find_train(i))] = 1
        continue
    else:
        dic[(find_road(i), find_train(i))] += 1

ans = []
for i in range(N):
    ans.append(dic[(find_road(i), find_train(i))])
print(*ans)

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

N,K,L = list(map(int,input().split()))
Network1 = UnionFind(N)
Network2 = UnionFind(N)

for i in range(K):
    p,q = list(map(int,input().split()))
    Network1.union(p-1,q-1)
for i in range(L):
    r,s = list(map(int,input().split()))
    Network2.union(r-1,s-1)

dam=[0]*N
D = {}
for i in range(N):
    X = Network1.find(i)
    Y = Network2.find(i)
    dam[i] = str(X) + "_" + str(Y)
    D[str(X) + "_" + str(Y)] = D.get(str(X) + "_" + str(Y), 0) + 1 #なかったら0を返す
out=[]
for i in range(N):
    out.append(D[dam[i]])

print(*out)

Submission status: Accepted

Solution code:
from collections import *;M=lambda:map(int,input().split());r=range;n,k,l=M()
def f(m):
 *a,=r(n)
 def g(i):
  if a[i]==i:return i
  a[i]=g(a[i]);return a[i]
 for _ in r(m):p,q=M();a[g(q-1)]=g(p-1)
 return [g(i) for i in r(n)]
z=[*zip(f(k),f(l))];c=Counter(z);print(*(c[x]for x in z))

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, N):
        self.N = N

        # the parent of all node is itself
        # self.parent = list(range(N))
        self.parent = [-1] * N

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

        r = self.root(self.parent[i])
        self.parent[i] = r
        return r

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

        if i == j:
            return

        if i > j:
            i, j = j, i

        self.parent[i] += self.parent[j]
        self.parent[j] = i
        # print(self.parent)

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

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

    def roots(self):
        return [self.root(i) for i in range(self.N)]

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

road = UnionFind(N)
rail = UnionFind(N)

for _ in range(K):
    p, q = map(int, input().split())
    p += -1
    q += -1
    road.unite(p, q)

for _ in range(L):
    r, s = map(int, input().split())
    r += -1
    s += -1
    rail.unite(r, s)

pair = {}
for i,j in zip(road.roots(), rail.roots()):
    t = (i, j)

    if t in pair:
        pair[t] += 1
    else:
        pair[t] = 1

ans = ' '.join([str(pair[(i, j)]) for i,j in zip(road.roots(), rail.roots())])
print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    n, 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)]
    uf1 = UnionFind(n)
    for a, b in p:
        uf1.union(a-1, b-1)
    uf2 = UnionFind(n)
    for a, b in r:
        uf2.union(a-1, b-1)
    dic = {}
    for i in range(n):
        rt1, rt2 = uf1.find(i), uf2.find(i)
        if (rt1, rt2) in dic:
            dic[(rt1, rt2)] += 1
        else:
            dic[(rt1, rt2)] = 1
    for i in range(n):
        rt1, rt2 = uf1.find(i), uf2.find(i)
        print(dic[(rt1, rt2)], end=" ")

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
import sys
import os
from operator import mul
from collections import Counter

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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


N,K,L = LI()
pq = [LI() for _ in range(K)]
rs = [LI() for _ in range(L)]

road = UnionFind(N)
for r in pq:
    f = r[0]-1
    t = r[1]-1
    road.union(f,t)

rail = UnionFind(N)
for r in rs:
    f = r[0]-1
    t = r[1]-1
    rail.union(f,t)

# ans = [-1]*N
# for i in range(N):
#     if not ans[i]==-1:
#         continue
#     road_set = set(road.members(i))
#     rail_set = set(rail.members(i))
#     group = road_set & rail_set
#     count = len(group)
#     for j in group:
#         ans[j]=count

union_sets=[(road.find(i),rail.find(i)) for i in range(N)]
# (0,1),(0,1),(2,2)
# 共通の親を持つ数をカウント
counts=Counter(union_sets)
# (0,1):2, (2,2):1
ans=[counts[union_set] for union_set in union_sets]

print(*ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
input = sys.stdin.buffer.readline


def grouping(adj):
    "0-indexed の無向グラフを連結成分に分解する。"
    n = len(adj)
    ret = [-1] * n
    g = 0
    for v in range(n):
        if ret[v] == -1:
            ret[v] = g
            stack = [v]
            while stack:
                v = stack.pop()
                for nv in adj[v]:
                    if ret[nv] == -1:
                        ret[nv] = ret[v]
                        stack.append(nv)
            g += 1
    return ret


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

pq_adj = [[] for _ in range(N)]
for _ in range(K):
    p, q = map(int, input().split())
    p -= 1
    q -= 1
    pq_adj[p].append(q)
    pq_adj[q].append(p)

rs_adj = [[] for _ in range(N)]
for _ in range(L):
    r, s = map(int, input().split())
    r -= 1
    s -= 1
    rs_adj[r].append(s)
    rs_adj[s].append(r)


group = [(g1 << 32) + g2 for g1, g2 in zip(grouping(pq_adj), grouping(rs_adj))]
c = Counter(group)
for v in range(N):
    print(c[group[v]])

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components

input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

N, K, L = map(int, input().split())
pq_and_rs = list(map(int, read().split()))

ps = pq_and_rs[:2*K:2]
qs = pq_and_rs[1:2*K:2]
rs = pq_and_rs[2*K::2]
ss = pq_and_rs[2*K+1::2]

pq_adj = csr_matrix(([1] * (2 * K), (ps + qs, qs + ps)), shape=(N+1, N+1))
rs_adj = csr_matrix(([1] * (2 * L), (rs + ss, ss + rs)), shape=(N+1, N+1))

group = ((connected_components(pq_adj)[1].astype(np.int64) << 32) + connected_components(rs_adj)[1]).tolist()
group_to_elements = defaultdict(list)
for v, g in enumerate(group):
    group_to_elements[g].append(v)

for v in range(1, N+1):
    print(len(group_to_elements[group[v]]))

Submission status: Accepted

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

def f(m):
    *a, = range(N)
    def g(i):
        if a[i] == i:
            return i
        a[i] = g(a[i])
        return a[i]
    for _ in range(m):
        p, q = map(int,input().split())
        a[g(q-1)] = g(p-1)
    return g

x, y = f(K), f(L)
c = Counter((x(i),y(i)) for i in range(N))
print(*((c[x(i),y(i)]) for i in range(N)))

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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


N,K,L = list(map(int,input().split()))
Network1 = UnionFind(N)
Network2 = UnionFind(N)

for i in range(K):
    P,Q=list(map(int,input().split()))
    Network1.union(P-1, Q-1)

for i in range(L):
    R,S=list(map(int,input().split()))
    Network2.union(R-1, S-1)

D = {}
memo = [0]*N
for i in range(N):
    X=Network1.find(i)
    Y=Network2.find(i)
    memo[i] = str(X)+"_"+str(Y)
    D[str(X)+"_"+str(Y)] = D.get(str(X)+"_"+str(Y),0)+1
out = []
for i in range(N):
    out.append(D[memo[i]])
print(*out)

Submission status: Accepted

Solution code:
N, K, L = map(int, input().split())
#Parent List(PL)
road = [i for i in range(N)]
rail = [i for i in range(N)]

def fp(x,P): #findParent
    if x == P[x]:
        return x
    else:
        P[x] = fp(P[x],P)
        return P[x]

for i in range(K+L):
    PL = (lambda x:road if x < K else rail)(i)
    p, q = map(lambda x:int(x)-1, input().split())
    p, q = fp(p,PL), fp(q,PL)
    PL[p] = PL[q] = min(p,q)

from collections import defaultdict as dd
Wconnected = dd(lambda:0)
for i in range(N):
    Wconnected[fp(i,road),fp(i,rail)] += 1
print(*[Wconnected[fp(i,road),fp(i,rail)] for i in range(N)])

Submission status: Accepted

Solution code:
from collections import Counter

class UnionFind():
  def __init__(self,n):
    self.parents=[-1]*n
  
  def find(self,x):
    if self.parents[x]<0:
      return x
    
    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,K,L=map(int,input().split())
uf_road=UnionFind(N+1)
uf_train=UnionFind(N+1)

for _ in range(K):
  p,q=map(int,input().split())
  uf_road.union(p,q)

for _ in range(L):
  s,t=map(int,input().split())
  uf_train.union(s,t)
  
union_sets=[(uf_road.find(i),uf_train.find(i)) for i in range(1,N+1)]
counts=Counter(union_sets)
ans=[counts[union_set] for union_set in union_sets]

print(' '.join(str(a) for a in ans))

Submission status: Accepted

Solution code:
from collections import Counter

class UnionFind():
  def __init__(self,n):
    self.parents=[-1]*n
  
  def find(self,x):
    if self.parents[x]<0:
      return x
    
    self.parents[x]=self.find(self.parents[x])
    return self.parents[x]
  
  def union(self,x,y):
    x=self.find(x)
    y=self.find(y)
    
    if x==y:
      return
    
    if self.parents[x]>self.parents[y]:
      x,y=y,x
      
    self.parents[x]+=self.parents[y]
    self.parents[y]=x
    
  def size(self,x):
    return abs(self.parents[self.find(x)])
  

N,K,L=map(int,input().split())
uf_road=UnionFind(N+1)
uf_train=UnionFind(N+1)
road_dict=dict()
train_dict=dict()

for _ in range(K):
  p,q=map(int,input().split())
  uf_road.union(p,q)

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

set_id_pairs = [(uf_road.find(i), uf_train.find(i)) for i in range(1,N+1)]
counter = Counter(set_id_pairs)
counts = [counter[set_id_pairs[i]] for i in range(N)]
print(' '.join(str(c) for c in counts))

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    def find_root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]
        
    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
                
    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def count(self, x):
        return -self.root[self.find_root(x)]
    
    
f=lambda:map(int,input().split())
N,K,L=f()
uf_road=UnionFind(N+1)
uf_rail=UnionFind(N+1)
for _ in [0]*K:
    uf_road.unite(*f())
for _ in [0]*L:
    uf_rail.unite(*f())

from bisect import bisect_left as bl
from bisect import bisect_right as br
    
roots=[(uf_road.find_root(i),uf_rail.find_root(i)) for i in range(1,N+1)]
sorted_roots=sorted(roots)

res=[]
for n in range(N):
    res.append(br(sorted_roots,roots[n])-bl(sorted_roots,roots[n]))
print(*res)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
def input(): return sys.stdin.readline().strip()

class UnionFind():
    """
    https://note.nkmk.me/python-union-find/
    DFSの上位互換と考えて良い
    ２要素x, yがpath-connectedかどうかをlogオーダーで判定する（螺旋本の14.1節参照）
    さらに連結成分の要素数がO(1)で取得可能なように改造してある
    """
    def __init__(self, n):
        """
        要素数をnとして、各ノードを0,1,...,(n-1)の番号で管理する
        parentsは各ノードの属する木の根を表す
        ただし根ノードのparentには(その木のノード数)*(-1)を格納する
        """
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        """
        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, yのそれぞれ属する木Tx, Tyの根同士を繋ぐ
        このとき木の要素数が小さい方を大きい方に繋ぐ（rankではなくsizeを用いる）
        """
        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):
        """
        xの属する木の要素数を返す
        根の親を要素数の(-1)倍で定めておいたおかげでO(1)で取得可能
        """
        return -self.parents[self.find(x)]

    def same(self, x, y):
        """
        xとyがpath-connectedかを判定する
        """
        return self.find(x) == self.find(y)

    def members(self, x):
        """
        xの属する木の要素を列挙する
        """
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        """
        連結成分の代表元のリストを返す
        """
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        """
        連結成分の個数を返す
        """
        return len(self.roots())

    def all_group_members(self):
         """
         連結成分およびそれぞれの代表元をまとめた辞書を返す
         代表元がキーになってる
         """
         return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        """
        連結成分およびその代表元を出力
        """
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    N, K, L = map(int, input().split())
    road = UnionFind(N)
    for _ in range(K):
        p, q = map(int, input().split())
        road.union(p - 1, q - 1)
    train = UnionFind(N)
    for _ in range(L):
        r, s = map(int, input().split())
        train.union(r - 1, s - 1)

    road_component = [road.find(i) for i in range(N)]
    train_component = [train.find(i) for i in range(N)]
    d = defaultdict(int)
    for r1, r2 in zip(road_component, train_component):
        d[(r1, r2)] += 1
    ans = [d[(r1, r2)] for r1, r2 in zip(road_component, train_component)]
    print(" ".join(map(str, ans)))





if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.parents = [-1 for _ in range(n)]  # 各要素の親 自分が根の場合は -1 * (木の要素数)

    def root(self, x):  # xが属する木の根を返す
        if self.parents[x] < 0:  # 自分が根の場合
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]

    def merge(self, x, y):  # xが属する木とyが属する木を合体する
        x_root = self.root(x)  # xの根
        y_root = self.root(y)  # yの根

        if x_root == y_root:  # 同じ木に属する
            return

        if abs(self.parents[x_root]) >= abs(self.parents[y_root]):  # 要素数の比較
            self.parents[x_root] += self.parents[y_root]
            self.parents[y_root] = x_root
        else:
            self.parents[y_root] += self.parents[x_root]
            self.parents[x_root] = y_root

    def size(self, x):  # xが属する木の要素数
        return -self.parents[self.root(x)]

    def same(self, x, y):  # xとyが同じ木に属するか判定
        return self.root(x) == self.root(y)

    def roots(self):  # すべての根を求める
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):  # 木が何個あるか
        return len(self.roots())


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

    uf_road = UnionFind(n)
    uf_train = UnionFind(n)

    for _ in range(k):
        p, q = map(int, input().split())
        uf_road.merge(p - 1, q - 1)

    for _ in range(l):
        r, s = map(int, input().split())
        uf_train.merge(r - 1, s - 1)

    count_dict = dict()
    for i in range(n):
        p = (uf_road.root(i), uf_train.root(i))
        if p in count_dict:
            count_dict[p] += 1
        else:
            count_dict[p] = 1

    for i in range(n):
        print(count_dict[(uf_road.root(i), uf_train.root(i))], end=" ")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter


class UnionFind:

    def __init__(self, n: int) -> None:
        self.parent = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

    def find(self, i: int) -> None:
        if self.parent[i] == i:
            return i
        else:
            return self.find(self.parent[i])

    def unite(self, i: int, j: int) -> None:
        root_i = self.find(i)
        root_j = self.find(j)
        if root_i == root_j:
            return
        if self.rank[root_i] < self.rank[root_j]:
            self.parent[root_i] = root_j
        else:
            self.parent[root_j] = root_i
            if self.rank[root_i] == self.rank[root_j]:
                self.rank[root_i] += 1

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

uf1 = UnionFind(N)
for _ in range(K):
    i, j = map(int, input().split())
    uf1.unite(i - 1, j - 1)

uf2 = UnionFind(N)
for _ in range(L):
    i, j = map(int, input().split())
    uf2.unite(i - 1, j - 1)

set_id_pairs = [(uf1.find(i), uf2.find(i)) for i in range(N)]
counter = Counter(set_id_pairs)
counts = [counter[set_id_pairs[i]] for i in range(N)]
print(' '.join(str(c) for c in counts))

Submission status: Accepted

Solution code:
from collections import *;M=lambda:map(int,input().split());r=range;n,k,l=M()
def f(m):
 *a,=r(n)
 def g(i):
  if a[i]==i:return i
  a[i]=g(a[i]);return a[i]
 for _ in r(m):p,q=M();a[g(q-1)]=g(p-1)
 return g
x,y=f(k),f(l);c=Counter((x(i),y(i))for i in r(n));print(*(c[x(i),y(i)]for i in r(n)))

Submission status: Accepted

Solution code:
from collections import *;M=lambda:map(int,input().split());r=range;n,k,l=M()
def f(m):
 *a,=r(n)
 def g(i):
  if a[i]==i:return i
  a[i]=g(a[i]);return a[i]
 for _ in r(m):p,q=M();a[g(q-1)]=g(p-1)
 return g
x,y=f(k),f(l);c=Counter((x(i),y(i))for i in r(n));print(*((c[x(i),y(i)])for i in r(n)))

Submission status: Accepted

Solution code:
from collections import *;M=lambda:map(int,input().split());r=range;n,k,l=M()
def f(m):
  *a,=r(n)
  def g(i):
    if a[i]==i:return i
    a[i]=g(a[i]);return a[i]
  for _ in r(m):p,q=M();a[g(q-1)]=g(p-1)
  return g
x,y=f(k),f(l);c=Counter((x(i),y(i))for i in r(n));print(*((c[x(i),y(i)])for i in r(n)))

Submission status: Accepted

Solution code:
from collections import *;M=lambda:map(int,input().split());r=range;n,k,l=M()
def f(m):
  a=list(r(n))
  def g(i):
    if a[i]==i:return i
    a[i]=g(a[i]);return a[i]
  for _ in r(m):p,q=M();a[g(q-1)]=g(p-1)
  return g
x,y=f(k),f(l);c=Counter((x(i),y(i))for i in r(n));print(*(c[x(i),y(i)]for i in r(n)))

Submission status: Accepted

Solution code:
from collections import Counter
import sys


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

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return 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
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1


def main():
    n, k, l = map(int, sys.stdin.buffer.readline().split())
    a = UnionFind(n)
    b = UnionFind(n)
    cnt = 0
    for x in sys.stdin.buffer.readlines():
        p, q = map(int, x.split())
        cnt += 1
        if cnt <= k:
            a.union(p-1, q-1)
        else:
            b.union(p-1, q-1)

    pairs = [(a._root(i), b._root(i)) for i in range(n)]
    d = Counter(pairs)
    ans = [d[x] for x in pairs]
    print(*ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
import sys


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

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return 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
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1


def main():
    n, k, l = map(int, sys.stdin.buffer.readline().split())
    a = UnionFind(n)
    b = UnionFind(n)
    cnt = 0
    for x in sys.stdin.buffer.readlines():
        p, q = map(int, x.split())
        cnt += 1
        if cnt <= k:
            a.union(p-1, q-1)
        else:
            b.union(p-1, q-1)

    pairs = []
    for i in range(n):
        pairs.append((a._root(i), b._root(i)))

    d = Counter(pairs)
    ans = [d[x] for x in pairs]
    print(*ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
from typing import AnyStr


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

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return 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
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1


def main():
    n, k, l = map(int, input().split())
    a = UnionFind(n)
    b = UnionFind(n)
    for _ in range(k):
        p, q = map(int, input().split())
        a.union(p-1, q-1)
    for _ in range(l):
        r, s = map(int, input().split())
        b.union(r-1, s-1)
    pairs = []
    for i in range(n):
        pairs.append((a._root(i), b._root(i)))

    d = Counter(pairs)
    ans = [d[x] for x in pairs]
    print(*ans)


if __name__ == '__main__':
    main()