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

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.sz = [ -1 for i in range(n)]

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


    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.sz[x] > self.sz[y]:
            x,y = y,x
        self.sz[x] += self.sz[y]
        self.sz[y] = x

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

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


N,K,L = map(int,input().split())
ufpq = UnionFind(N)
ufrs = UnionFind(N)
for i in range(K):
    a,b = map(int,input().split())
    ufpq.union(a-1,b-1)
for i in range(L):
    a,b = map(int,input().split())
    ufrs.union(a-1,b-1)

pq = []
rs = []
from collections import defaultdict
d = defaultdict(int)
for i in range(N):
    d[(ufpq.find(i),ufrs.find(i))] += 1

ans = []
for i in range(N):
    ans.append(d[(ufpq.find(i),ufrs.find(i))])
print(" ".join(map(str,ans)))

Solution (Python):
from collections import Counter

N,K,L = map(int, input().split())
pq_list = []
for _ in range(K):
    pq_list.append(list(map(int, input().split())))

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

class UnionFind():
    def __init__(self):
        self.roots = {}
        self.ranks = {}

    def connect(self,x,y):
        root_x = self.pick_root(x)
        root_y = self.pick_root(y)
        



        
        if not root_x == root_y:
            if self.ranks[root_x] >= self.ranks[root_y]:
                
                
                self.roots[root_y] = root_x
            else:
                self.roots[root_x] = root_y

            if self.ranks[root_x]==self.ranks[root_y]:
                
                self.ranks[x] += 1

    def pick_root(self,k):
        if not k in self.roots:
            self.roots[k] = k
            self.ranks[k] = 1
            return k

        k_root = self.roots[k]
        if k_root == k:
            return k
        else:
            
            self.roots[k] = self.pick_root(self.roots[k_root])
            return self.roots[k]


UF_pq = UnionFind()
for p,q in pq_list:
    UF_pq.connect(p, q)

UF_rs = UnionFind()
for r,s in rs_list:
    UF_rs.connect(r, s)

root_tuples = []
for i in range(1,N+1):
    
    
    
    if not i in UF_pq.roots:
        root_tuples.append((None,None))
        continue
    if not i in UF_rs.roots:
        root_tuples.append((None,None))
        continue
    pq_root = UF_pq.pick_root(i)
    rs_root = UF_rs.pick_root(i)
    
    
    
    root_tuples.append((pq_root,rs_root))

counter = Counter(root_tuples)
counter[(None,None)] = 1

kotae_list = []
for i in range(N):
    kotae_list.append(counter[root_tuples[i]])

print(" ".join(map(str,kotae_list)))

Solution (Python):
from itertools import accumulate
from math import*
from collections import deque
from collections import defaultdict
from itertools import permutations
import heapq
import bisect
from collections import Counter
from itertools import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = 10**10
from functools import reduce

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

  def union(self, a, b):
    a = self.root(a)
    b = self.root(b)
    if(a == b):
      return
    if(self.size(a) < self.size(b)):
      a, b = b, a
    self.tree[a] += self.tree[b]
    self.tree[b] = a

  def root(self, a):
    if(self.tree[a] < 0):
      return a
    res = self.root(self.tree[a])
    self.tree[a] = res
    return res

  def size(self, a):
    return -self.tree[self.root(a)]

n,k,l = map(int,input().split())
uf1 = UnionFind(n)
uf2 = UnionFind(n)
for i in range(k):
    p,q = map(int,input().split())
    p -= 1
    q -= 1
    uf1.union(p,q)
for i in range(l):
    r,s = map(int,input().split())
    r -= 1
    s -= 1
    uf2.union(r,s)
ab = [(uf1.root(i),uf2.root(i)) for i in range(n)]
c = Counter(ab)
print(" ".join(map(str,[c[i] for i in ab])))

Solution (Python):
class UnionFind:
    def __init__(self, size):
        self.__data = [-1 for _ in range(size)]
    def find(self, x):
        if self.__data[x] < 0:
            return x
        else:
            self.__data[x] = self.find(self.__data[x])
            return self.__data[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            if self.__data[y] < self.__data[x]:
                x, y = y, x
            self.__data[x] += self.__data[y]
            self.__data[y] = x
        return (x != y)
    def same(self, x, y):
        return (self.find(x) == self.find(y))
    def size(self, x):
        return -self.__data[self.find(x)]
    def get_data(self):
        return [a if a >= 0 else i for i, a in enumerate(self.__data)]

N, K, L = [int(i) for i in input().split()]

uf1 = UnionFind(N)
for _ in range(K):
    p, q = [int(i) - 1 for i in input().split()]
    uf1.union(p, q)

uf2 = UnionFind(N)
for _ in range(L):
    r, s = [int(i) - 1 for i in input().split()]
    uf2.union(r, s)

for i in range(N):
    uf1.find(i)
    uf2.find(i)

from collections import Counter
Z = [(a, b) for a, b in zip(uf1.get_data(), uf2.get_data())]
C = Counter(Z)
print(*[C[z] for z in Z])

Solution (Python):
class UnionFind:
    def __init__(self, size):
        self.__data = [-1 for _ in range(size)]
    def find(self, x):
        if self.__data[x] < 0:
            return x
        else:
            self.__data[x] = self.find(self.__data[x])
            return self.__data[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            if self.__data[y] < self.__data[x]:
                x, y = y, x
            self.__data[x] += self.__data[y]
            self.__data[y] = x
        return (x != y)
    def same(self, x, y):
        return (self.find(x) == self.find(y))
    def size(self, x):
        return -self.__data[self.find(x)]

N, K, L = [int(i) for i in input().split()]

uf1 = UnionFind(N)
for _ in range(K):
    p, q = [int(i) - 1 for i in input().split()]
    uf1.union(p, q)

uf2 = UnionFind(N)
for _ in range(L):
    r, s = [int(i) - 1 for i in input().split()]
    uf2.union(r, s)

from collections import Counter
C = Counter((uf1.find(i), uf2.find(i)) for i in range(N))
print(*[C[(uf1.find(i), uf2.find(i))] for i in range(N)])

Solution (Python):
class UnionFind:
    def __init__(self, size):
        self.data = [-1 for _ in range(size)]
    def find(self, x):
        if self.data[x] < 0:
            return x
        else:
            self.data[x] = self.find(self.data[x])
            return self.data[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            if self.data[y] < self.data[x]:
                x, y = y, x
            self.data[x] += self.data[y]
            self.data[y] = x
        return (x != y)
    def same(self, x, y):
        return (self.find(x) == self.find(y))
    def size(self, x):
        return -self.data[self.find(x)]

N, K, L = [int(i) for i in input().split()]

uf1 = UnionFind(N)
for _ in range(K):
    p, q = [int(i) - 1 for i in input().split()]
    uf1.union(p, q)

uf2 = UnionFind(N)
for _ in range(L):
    r, s = [int(i) - 1 for i in input().split()]
    uf2.union(r, s)

from collections import Counter
C = Counter((uf1.find(i), uf2.find(i)) for i in range(N))
print(*[C[(uf1.find(i), uf2.find(i))] for i in range(N)])

Solution (Python):
class UnionFind:
    def __init__(self, size):
        self.data = [i for i in range(size)]
    def find(self, x):
        if self.data[x] != x:
            self.data[x] = self.find(self.data[x])
        return self.data[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            self.data[x] = min(x, y)
            self.data[y] = self.data[x]

N, K, L = [int(i) for i in input().split()]

uf1 = UnionFind(N)
for _ in range(K):
    p, q = [int(i) - 1 for i in input().split()]
    uf1.union(p, q)

uf2 = UnionFind(N)
for _ in range(L):
    r, s = [int(i) - 1 for i in input().split()]
    uf2.union(r, s)

from collections import defaultdict
d = defaultdict(int)
for i in range(N):
    d[(uf1.find(i), uf2.find(i))] += 1

l = ""
for i in range(N):
    l += str(d[(uf1.find(i), uf2.find(i))]) + " "
print(l[:-1])

Solution (Python):
class UnionFind:
    def __init__(self, elems):
        self.parent = dict()
        for e in elems:
            self.parent[e] = e

    def root(self, e):
        if self.parent[e] == e:
            return e

        self.parent[e] = self.root(self.parent[e])
        return self.parent[e]

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

    def unite(self, x, y):
        if self.same(x, y):
            return

        rx = self.root(x)
        ry = self.root(y)
        self.parent[rx] = ry


n, k, l = map(int, input().split())
uf1 = UnionFind(list(range(n)))
uf2 = UnionFind(list(range(n)))

for i in range(k):
    a, b = map(lambda x: int(x) - 1, input().split())
    uf1.unite(a, b)

for i in range(l):
    a, b = map(lambda x: int(x) - 1, input().split())
    uf2.unite(a, b)


ps = [(uf1.root(i), uf2.root(i)) for i in range(n)]
counts = dict()
for p in ps:
    if p in counts:
        counts[p] += 1
    else:
        counts[p] = 1


nums = [counts[p] for p in ps]
print(' '.join(map(str, nums)))

Solution (Python):
from collections import defaultdict

N, K, L = [int(a) for a in input().split(" ")]
P, Q = zip(*[[int(v) for v in input().split(" ")] for i in range(K)])
R, S = zip(*[[int(v) for v in input().split(" ")] for i in range(L)])

def find(tab, a):
    if tab[a] == -1: return a
    tab[a] = find(tab, tab[a])
    return tab[a]

def union(tab, a, b):
    pa, pb = (find(tab, a), find(tab, b))
    if pa!=pb:
        tab[pb] = pa

loads = [-1]*N
rails = [-1]*N
both = [-1]*N
for p, q in zip(P, Q):
    union(loads, p-1, q-1)

for r, s in zip(R, S):
    union(rails, r-1, s-1)

dic = defaultdict(lambda: 0)
ans = []
for i in range(N):
    key = (find(loads, i), find(rails, i))
    ans.append(key)
    dic[key] += 1

ans = [dic[key] for key in ans]
print(" ".join([str(cnt) for cnt in ans]))

Solution (Python):
from collections import defaultdict
def main():
	N, K, L = map(int, input().split())
	road = [0]*K
	rail = [0]*L
	road_graph = [[i, 0] for i in range(N+1)]
	rail_graph = [[i, 0] for i in range(N+1)]

	def root(graph, i):
		parent = graph[i][0]
		if parent == i:
			return i
		return root(graph, parent)

	def is_same_tree(graph, i, j):
		return root(graph, i) == root(graph, j)

	def unite(graph, i, j):
		if is_same_tree(graph, i, j):
			return
		l = graph[root(graph, i)]
		r = graph[root(graph, j)]
		if l[1] < r[1]:
			l[0] = r[0]
			r[1] += 1
		else:
			r[0] = l[0]
			l[1] += 1

	ans_list = [""]*N

	for i in range(K):
		road[i] = list(map(int, input().split()))
		unite(road_graph, road[i][0], road[i][1])
	for i in range(L):
		rail[i] = list(map(int, input().split()))
		unite(rail_graph, rail[i][0], rail[i][1])

	ans_memo = defaultdict(int)
	road_memo = [0]*(N+1)
	rail_memo = [0]*(N+1)
	for i in range(1, N+1):
		road_root = root(road_graph, i)
		rail_root = root(rail_graph, i)
		road_memo[i] = road_root
		rail_memo[i] = rail_root
		ans_memo[(road_root, rail_root)] += 1

	for i in range(1, N+1):
		road_root = road_memo[i]
		rail_root = rail_memo[i]
		this_ans = str(ans_memo[road_root, rail_root])
		ans_list[i-1] = this_ans

	ans = " ".join(ans_list)
	print(ans)


if __name__ == '__main__':
	main()

Solution (Python):
n, k, l = [int(item) for item in input().split()]
pq = [[int(item) for item in input().split()] for _ in range(k)]
rs = [[int(item) for item in input().split()] for _ in range(l)]

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

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

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

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

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

UFA = UnionFind(n)
UFB = UnionFind(n)
for p, q in pq:
    UFA.union(p-1, q-1)
for r, s in rs:
    UFB.union(r-1, s-1)

par = []
for i in range(n):
    par.append([UFA.find(i), UFB.find(i), i])
par = sorted(par, key=lambda x:(x[0], x[1]))
prev_a, prev_b = -1, -1
ans = [0] * n
count = 0
member = []
for a, b, index in par:
    if prev_a != a or prev_b != b:
        for mem in member:
            ans[mem] = count
        count = 1
        member = [index]
        prev_a = a
        prev_b = b
    else:
        member.append(index)
        count += 1
for mem in member:
    ans[mem] = count
print(" ".join([str(item) for item in ans]))

Solution (Python):
from collections import defaultdict

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.par = [-1 for _ in range(n)]
 
    def same(self, x, y):
        return self.root(x)==self.root(y)
 
    def root(self, x):
        if self.par[x]<0:
            return x
        self.par[x] = self.root(self.par[x])
        return self.par[x]
 
    def unite(self,x,y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
 
        if self.par[x] > self.par[y]:
            x, y = y, x
 
        self.par[x] += self.par[y]
        self.par[y] = x
        
N, K, L = map(int, input().split())

uf = UnionFind(N)
for i in range(K):
    p, q = map(int, input().split())
    uf.unite(p - 1, q - 1)
    
uf2 = UnionFind(N)
for i in range(L):
    r, s = map(int, input().split())
    uf2.unite(r - 1, s - 1)

d = defaultdict(int)
for i in range(N):
    n = uf.root(i)
    m = uf2.root(i)
    d[(n, m)] += 1

ans = []
for i in range(N):
    n = uf.root(i)
    m = uf2.root(i)
    ans.append(d[(n, m)])

print(* ans)

Solution (Python):
import sys
from collections import defaultdict

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

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

    def unite(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] < self.rank[ry]:
            self.root[rx] = ry
        else:
            self.root[ry] = rx
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

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

def main():
    input = sys.stdin.readline
    N, K, L = map(int, input().split())
    road = UnionFind(N)
    rail = UnionFind(N)

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

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

    d = defaultdict(lambda: 0)
    for i in range(N):
        n = road.find(i)
        m = rail.find(i)
        d[(n, m)] += 1

    ans = []
    for i in range(N):
        n = road.find(i)
        m = rail.find(i)
        ans.append(d[(n, m)])

    return print(*ans)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict
from fractions import gcd

from math import sqrt
from math import ceil
from itertools import permutations
from heapq import *
class UnionFindNode(object):
    """
    Union-Find構造
    ノードのグループ併合や、所属グループ判定を高速に処理する
    """

    def __init__(self, group_id, parent=None, value=None):
        self.group_id_ = group_id
        self.parent_ = parent
        self.value = value
        self.size_ = 1

    def __str__(self):
        template = "UnionFindNode(group_id: {}, \n\tparent: {}, value: {}, size: {})"
        return template.format(self.group_id_, self.parent_, self.value, self.size_)

    def is_root(self):
        return not self.parent_

    def root(self):
        parent = self
        while not parent.is_root():
            parent = parent.parent_
            self.parent_ = parent
        return parent

    def find(self):
        parent = self.root()
        return parent.group_id_

    def size(self):
        parent = self.root()
        return parent.size_

    def unite(self, unite_node):
        parent = self.root()
        unite_parent = unite_node.root()

        if parent.group_id_ != unite_parent.group_id_:
            if parent.size() > unite_parent.size():
                unite_parent.parent_ = parent
                parent.size_ = parent.size_ + unite_parent.size_
            else:
                parent.parent_ = unite_parent
                unite_parent.size_ = parent.size_ + unite_parent.size_


N,K,L=map(int,input().split())
inf1=[]
for _ in range(K):
    inf1.append(list(map(int,input().split())))
inf2=[]
for _ in range(L):
    inf2.append(list(map(int,input().split())))
U=[UnionFindNode(i) for i in range(N+1)]
for i in range(K):
    x=inf1[i][0]
    y=inf1[i][1]
    U[x].unite(U[y])
U_=[UnionFindNode(i) for i in range(N+1)]
for i in range(L):
    x=inf2[i][0]
    y=inf2[i][1]
    U_[x].unite(U_[y])
d=defaultdict(int)
for i in range(1,N+1):
    k=(U[i].find(),U_[i].find())
    d[k]+=1
ans=[]
for i in range(1,N+1):
    k=(U[i].find(),U_[i].find())
    ans.append(d[k])
print(" ".join(map(str,ans)))

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

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

N, K, L = MAP()

tree_pq = UnionFind(N+1) 
tree_rs = UnionFind(N+1)
pq = [LIST() for _ in range(K)]
for p, q in pq:
	tree_pq.union(p, q) 
group_pq = [tree_pq.find(i) for i in range(N+1)]

rs = [LIST() for _ in range(L)]
for r, s in rs:
	tree_rs.union(r, s)
group_rs = [tree_rs.find(i) for i in range(N+1)]


keys = []
dic = {}
pairs = [(group_pq[i], group_rs[i]) for i in range(N+1)]
for i in range(1, N+1):
	pair = (group_pq[i], group_rs[i])
	keys.append(pair)
	if pair in dic:
		dic[pair] += 1
	else:
		dic[pair] = 1

ans = [str(dic[key]) for key in keys]
print(" ".join(ans))

Solution (Python):
n, k, l = map(int, input().split())
load = [-1] * (n + 1)
train = [-1] * (n + 1)

def find_load(x, u = load):
    if u[x] < 0 :
        return x
    else:
        u[x] = find_load(u[x])
        return u[x]

def find_train(x, u = train):
    if u[x] < 0 :
        return x
    else:
        u[x] = find_train(u[x])
        return u[x]

for i in range(k):

    p, q = map(int, input().split())
    p, q = map(find_load, [p, q])
    p, q = sorted((p, q))
    if p != q:
        load[q] = p

load = [i if x < 0 else x for i, x in enumerate(load)]

for i in range(l):
    r, s = map(int, input().split())
    r, s = map(find_train, [r, s])
    r, s = sorted((r, s))
    if r != s:
        train[s] = r
train = [i if x < 0 else x for i, x in enumerate(train)]

keys = []
dic  = {}

for node in range(n):
    key = (find_load(load[node + 1]), find_train(train[node + 1]))
    keys.append(key)
    if key in dic:
        dic[key] += 1
    else:
        dic[key] = 1

ans = [str(dic[key]) for key in keys]
print(" ".join(ans))

Solution (Python):
class UnionFind:
    def __init__(self, size: int):
        self.__size = size
        self.__root = [-1] * size

    def root(self, x: int)->int:
        if self.__root[x] < 0:
            return x
        self.__root[x] = self.root(self.__root[x])
        return self.__root[x]

    def size(self, x: int)->int:
        root = self.root(x)
        return self.__root[root]

    def same(self, x: int, y: int)->bool:
        return self.root(x) == self.root(y)

    def unite(self, x: int, y: int):
        rx, ry = self.root(x), self.root(y)

        if rx == ry:
            return

        if ry < rx:
            rx, ry = ry, rx

        self.__root[rx] += self.__root[ry]
        self.__root[ry] = rx


def connectivity(N: int, K: int, L: int, roads: list, rails: list)->list:
    road_uf, rail_uf = UnionFind(N), UnionFind(N)

    for p, q in roads:
        road_uf.unite(p-1, q-1)

    for r, s in rails:
        rail_uf.unite(r-1, s-1)

    freq = {}
    for i in range(N):
        p = (road_uf.root(i), rail_uf.root(i))
        freq.setdefault(p, 0)
        freq[p] += 1

    return [freq[(road_uf.root(i), rail_uf.root(i))] for i in range(N)]


if __name__ == "__main__":
    K = 0
    L = 0
    N, K, L = map(int, input().split())
    roads = [tuple(int(s) for s in input().split()) for _ in range(K)]
    rails = [tuple(int(s) for s in input().split()) for _ in range(L)]
    ans = connectivity(N, K, L, roads, rails)
    print(' '.join(map(str, ans)))

Solution (Python):
import sys
input = sys.stdin.readline

from collections import Counter

class Unionfind:

    __slots__ = ['nodes','size']

    def __init__(self, n):
        self.nodes = list(range(n))
        self.size = [1]*n

    def root(self, x):
        if self.nodes[x] == x:
            return x
        else:
            root_x = self.root(self.nodes[x])
            self.nodes[x] = root_x
            return root_x

    def unite(self, x, y):
        x = self.root(x); y = self.root(y)
        if x == y:
            return
        if self.size[x] < self.size[y]:
            x, y = y, x
        self.size[x] += self.size[y]
        self.nodes[y] = x

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

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

uf1 = Unionfind(N)
uf2 = Unionfind(N)

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

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




keys = []
dic = Counter()

for node in range(N):
    key = (uf1.root(node),uf2.root(node))
    keys.append(key)
    dic[key] += 1

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

Solution (Python):
import sys
input = sys.stdin.readline

class Unionfind:

    __slots__ = ['nodes','size']

    def __init__(self, n):
        self.nodes = list(range(n))
        self.size = [1]*n

    def root(self, x):
        if self.nodes[x] == x:
            return x
        else:
            root_x = self.root(self.nodes[x])
            self.nodes[x] = root_x
            return root_x

    def unite(self, x, y):
        x = self.root(x); y = self.root(y)
        if x == y:
            return
        if self.size[x] < self.size[y]:
            x, y = y, x
        self.size[x] += self.size[y]
        self.nodes[y] = x

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

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

uf1 = Unionfind(N)
uf2 = Unionfind(N)

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

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

keys = []
dic = {}

for node in range(N):
    key = (uf1.root(node),uf2.root(node))
    keys.append(key)
    if key in dic:
        dic[key] += 1
    else:
        dic[key] = 1

ans = [str(dic[key]) for key in keys]
print(" ".join(ans))

Solution (Python):
import collections


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

    def root(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.rank[x] > self.rank[y]:
            self.par[y] = x
        else:
            self.par[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

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


N, K, L = map(int, input().split())
graph_road = UnionFind(N)
graph_train = UnionFind(N)
for k in range(K):
    p, q = map(int, input().split())
    graph_road.unite(p-1, q-1)

for l in range(L):
    r, s = map(int, input().split())
    graph_train.unite(r-1, s-1)

pair = collections.defaultdict(int)
for i in range(N):
    road = graph_road.root(i)
    train = graph_train.root(i)
    pair[(road, train)] += 1

for i in range(N):
    road = graph_road.root(i)
    train = graph_train.root(i)
    print(pair[(road, train)])

Solution (Python):
import collections


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

    def root(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.rank[x] > self.rank[y]:
            self.par[y] = x
        else:
            self.par[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

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


N, K, L = map(int, input().split())
graph_road = UnionFind(N)
graph_train = UnionFind(N)
for k in range(K):
    p, q = map(int, input().split())
    graph_road.unite(p-1, q-1)

for l in range(L):
    r, s = map(int, input().split())
    graph_train.unite(r-1, s-1)

pair = collections.defaultdict(int)
for i in range(N):
    road = graph_road.root(i)
    train = graph_train.root(i)
    pair[(road, train)] += 1

for i in range(N):
    road = graph_road.root(i)
    train = graph_train.root(i)
    print(pair[(road, train)])

Solution (Python):
N, K, L = map(int, input().split())
pq = [map(int, input().split()) for _ in range(K)]
rs = [map(int, input().split()) for _ in range(L)]

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

    def root(self, x):
        if self.par[x] == x:
            return x
        r = self.root(self.par[x])
        self.par[x] = r
        return r

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx != ry:
            if self.rank[rx] > self.rank[ry]:
                self.par[ry] = rx
            else:
                self.par[rx] = ry
                if self.rank[rx] == self.rank[ry]:
                    self.rank[ry] += 1

    def is_same(self, x, y):
        return self.root(x) == self.root(y)

uf_road = UnionFind(N)
uf_train = UnionFind(N)

for p, q in pq:
    uf_road.unite(p, q)
for r, s in rs:
    uf_train.unite(r, s)

from collections import Counter
c = Counter()
for i in range(1, N+1):
    k = (uf_road.root(i), uf_train.root(i))
    c[k] += 1

ret = []
for i in range(1, N+1):
    k = (uf_road.root(i), uf_train.root(i))
    ret.append(c[k])

print(" ".join(str(v) for v in ret))

Solution (Python):


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.par = [-1 for _ in range(n)]

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

    def root(self, x):
        if self.par[x]<0:
            return x
        self.par[x] = self.root(self.par[x])
        return self.par[x]

    def unite(self,x,y):
        x = self.root(x)
        y = self.root(y)
        if x==y:
            return

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

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

    def size(self,x):
        return -self.par[self.root(x)]

n,k,l = map(int, input().split())
road = UnionFind(n)
for _ in range(k):
    p,q = map(int, input().split())
    road.unite(p-1, q-1)

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

d = {}
for i in range(n):
    x = (road.root(i), rail.root(i))
    if x not in d:
        d[x] = 0
    d[x] +=1

res = [d[(road.root(i), rail.root(i))] for i in range(n)]
print(*res)