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):
from collections import defaultdict
class UnionFind:


    def __init__(self,n):
        self.parent = [i for i in range(n)]
        self.rank = [0]*n
        self.n = n
    def find(self,x):
        if self.parent[x] == x:
            return x
        else:self.parent[x] = self.find(self.parent[x])
        x = self.parent[x]
        return 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.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same(self,x,y):
        return bool(self.find(x)==self.find(y))

from sys import stdin
def main():
    N,K,L = map(int,stdin.readline().split())
    uf = UnionFind(N)
    uf1 = UnionFind(N)

    for _ in range(K):
        p,q = map(int,stdin.readline().split())
        uf.union(p-1,q-1)
    for _ in range(L):
        r,s = map(int,stdin.readline().split())
        uf1.union(r-1,s-1)
    d = defaultdict(int)
    for i in range(N):
        d[(uf.find(i),uf1.find(i))] += 1
    print(*(d[uf.find(i),uf1.find(i)]for i in range(N)))
    

if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict
class UnionFind:


    def __init__(self,n):
        self.parent = [i for i in range(n)]
        self.rank = [0]*n
        self.n = n
    def find(self,x):
        if self.parent[x] == x:
            return x
        while x != self.parent[x]:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return 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.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same(self,x,y):
        return bool(self.find(x)==self.find(y))

from sys import stdin
def main():
    N,K,L = map(int,stdin.readline().split())
    uf = UnionFind(N)
    uf1 = UnionFind(N)

    for _ in range(K):
        p,q = map(int,stdin.readline().split())
        uf.union(p-1,q-1)
    for _ in range(L):
        r,s = map(int,stdin.readline().split())
        uf1.union(r-1,s-1)
    d = defaultdict(int)
    for i in range(N):
        d[(uf.find(i),uf1.find(i))] += 1
    print(*(d[uf.find(i),uf1.find(i)]for i in range(N)))
    

if __name__ == "__main__":
    main()

Solution (Python):
import bisect
import collections
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 32


def lmi():
    return list(map(int, input().split()))


def llmi(n):
    return [lmi() for _ in range(n)]


N, K, L = lmi()
pq = llmi(K)
rs = llmi(L)


class _UnionFind(object):
    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())


class UnionFind(_UnionFind):
    pass


uf_road = UnionFind(N)
for p, q in pq:
    uf_road.union(p - 1, q - 1)
uf_train = UnionFind(N)
for p, q in rs:
    uf_train.union(p - 1, q - 1)








d = collections.defaultdict(int)
for i in range(N):
    key = uf_road.find(i), uf_train.find(i)
    d[key] += 1

print(' '.join(str(d[(uf_road.find(i), uf_train.find(i))]) for i in range(N)))

Solution (Python):


def main():
    import sys
    input = sys.stdin.readline

    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))

    
    class UnionFind():
        """
        parents : 親要素(findしない場合は根ではないことの注意)，根の場合は"-(要素数）"
        find(x):要素xの属するグループの根を返す
        size(x):要素xの属するグループの要素数を返す
        same(x,y):x,yが同じグループに属しているか返す
        members(x):要素xが属するグループに属する要素をリストで返す
        roots:全ての根の要素を返す
        group_count():グループの数を返す
        all_group_members():{根要素：[そのグループに含まれる要素のリスト]}の辞書を返す
        """
        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):
            arr=[]
            for r in range(self.roots()):
                arr.append(set(self.members(r)))
            return arr

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

    mod=10**9+7
    N,K,L=MI()
    uf1 = UnionFind(N)
    uf2 = UnionFind(N)
    ans=[0]*N

    for i in range(K):
        p,q=MI()
        p-=1
        q-=1
        uf1.union(p,q)
        
    for i in range(L):
        p,q=MI()
        p-=1
        q-=1
        uf2.union(p,q)
        
    from collections import defaultdict
    dd = defaultdict(int)
    
    for i in range(N):
        a=uf1.find(i)
        b=uf2.find(i)
        dd[(a,b)]+=1
        
    for i in range(N):
        a=uf1.find(i)
        b=uf2.find(i)
        ans[i]=dd[(a,b)]
        
    print(' '.join(map(str, ans)))
    
    
    
        
        
    


main()

Solution (Python):
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 sample():
    uf = UnionFind(6)
    print(uf.parents)
    uf.union(0, 2)
    print(uf.parents)
    uf.union(1, 3)
    print(uf.parents)
    uf.union(4, 5)
    print(uf.parents)

def atc001():
    n, q = map(int, input().split())
    uf = UnionFind(n)
    for i in range(q):
        p, a, b = map(int, input().split())
        if p == 0:
            uf.union(a, b)
        else:
            if uf.same(a, b):
                print("Yes")
            else:
                print("No")

def abc049():
    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.union(p - 1, q - 1)
    for i in range(l):
        p, q = map(int, input().split())
        train.union(p - 1, q - 1)

    pair = []
    pair_cnt = {}
    for i in range(n):
        t, r = road.find(i), train.find(i)
        pair.append([t, r])
        key = t * (10 ** 6) + r
        if key in pair_cnt:
            pair_cnt[key] += 1
        else:
            pair_cnt[key] = 1

    for i in range(n):
        [t, r] = pair[i]
        key = t * (10 ** 6) + r
        print(pair_cnt[key], end = " ")

abc049()

Solution (Python):
from collections import defaultdict
N, K, L = map(int,input().split())
data = [[0, 0] for _ in range(N)]
Lpath = [[] for _ in range(N)]
Tpath = [[] for _ in range(N)]

for _ in range(K):
    p, q = map(int,input().split())
    p -= 1
    q -= 1
    Lpath[p].append(q)
    Lpath[q].append(p)
    
for _ in range(L):
    r, s = map(int,input().split())
    r -= 1
    s -= 1
    Tpath[r].append(s)
    Tpath[s].append(r)
    
for i in range(N):
    if data[i][0]:
        continue
    data[i][0] = i + 1
    stack = [i]
    while stack:
        s = stack.pop()
        for to in Lpath[s]:
            if data[to][0]:
                continue
            data[to][0] = i + 1
            stack.append(to)

for i in range(N):
    if data[i][1]:
        continue
    data[i][1] = i + 1
    stack = [i]
    while stack:
        s = stack.pop()
        for to in Tpath[s]:
            if data[to][1]:
                continue
            data[to][1] = i + 1
            stack.append(to)

ans = [0] * N
d = defaultdict(int)         
for i in range(N):
    d[tuple(data[i])] += 1
for i in range(N):
    ans[i] = d[tuple(data[i])]

print(*ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

from collections import Counter


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

GRAPH = [[] for _ in range(n + 1)]
for _ in range(k):
    p, q = map(int, input().split())
    GRAPH[p].append(q); GRAPH[q].append(p)

def dfs(now):
    A[now] = a
    SEARCHED[now] = True
    for v in GRAPH[now]:
        if SEARCHED[v]:
            continue
        next = v
        dfs(next)

A = [0] * (n + 1)
SEARCHED = [False] * (n + 1)

a = 1
for i in range(1, n + 1):
    if SEARCHED[i]:
        continue
    dfs(i)
    a += 1

GRAPH = [[] for _ in range(n + 1)]
for _ in range(l):
    r, s = map(int, input().split())
    GRAPH[r].append(s); GRAPH[s].append(r)

def dfs(now):
    B[now] = b
    SEARCHED[now] = True
    for v in GRAPH[now]:
        if SEARCHED[v]:
            continue
        next = v
        dfs(next)

B = [0] * (n + 1)
SEARCHED = [False] * (n + 1)

b = 1
for i in range(1, n + 1):
    if SEARCHED[i]:
        continue
    dfs(i)
    b += 1

AB = [ab for ab in zip(A, B)]
COUNTS = Counter(AB)

for i in range(1, n + 1):
    print(COUNTS[AB[i]])

Solution (Python):
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 
    if self.root[x] > self.root[y]:
      x, y = y, x
    self.root[x] += self.root[y]
    self.root[y] = x 
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)
  def Count(self, x): 
    return -self.root[self.Find_Root(x)]
  def Members(self, x): 
    return [i for i in range(self.n) if self.Find_Root(i)==self.Find_Root(x)]
  def Roots(self): 
    return [i for i, x in enumerate(self.root) if x < 0]
  def Group_Count(self): 
    return len(self.Roots())

n, k, l = map(int, input().split())
uf_road = UnionFind(n)
uf_train = UnionFind(n)
connect = {}

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

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

for i in range(n):
  par1, par2 = uf_road.Find_Root(i), uf_train.Find_Root(i)
  if (par1, par2) in connect.keys():
    connect[(par1, par2)] += 1
  else:
    connect[(par1, par2)] = 1

ans = []
for i in range(n):
  par1, par2 = uf_road.Find_Root(i), uf_train.Find_Root(i)
  ans += [str(connect[(par1, par2)])]

print(" ".join(ans))

Solution (Python):
class UnionFind:
    def __init__(self, elements):
        self.elements = elements

    def same(self, a, b):
        return self.find(a) == self.find(b)

    def find(self, a):
        parent = self.elements[a]
        if parent < 0:
            return a
        self.elements[a] = self.find(parent)
        return self.elements[a]

    def unite(self, a, b):
        a_parent = self.find(a)
        b_parent = self.find(b)

        
        if a_parent == b_parent:
            return

        self.elements[a_parent] += self.elements[b_parent]
        self.elements[b_parent] = a_parent


N, K, L = map(int, input().split())
road_union = UnionFind([-1 for i in range(N)])
for _ in range(K):
    a, b = map(int, input().split())
    road_union.unite(a - 1, b - 1)

train_union = UnionFind([-1 for i in range(N)])
for _ in range(L):
    a, b = map(int, input().split())
    train_union.unite(a - 1, b - 1)

ma = dict()
for i in range(N):
    p = (road_union.find(i), train_union.find(i))
    ma[p] = ma.get(p, 0) + 1

for i in range(N):
    p = (road_union.find(i), train_union.find(i))
    print(ma[p], end=' ')

Solution (Python):
class UnionFind:
    def __init__(self, elements):
        self.elements = {e: -1 for e in elements}

    def same(self, a, b):
        return self.find(a) == self.find(b)

    def find(self, a):
        parent = self.elements[a]
        if parent < 0:
            return a
        self.elements[a] = self.find(parent)
        return self.elements[a]

    def unite(self, a, b):
        a_parent = self.find(a)
        b_parent = self.find(b)

        
        if a_parent == b_parent:
            return

        self.elements[a_parent] += self.elements[b_parent]
        self.elements[b_parent] = a_parent


N, K, L = map(int, input().split())
road_union = UnionFind(i for i in range(1, N + 1))
for _ in range(K):
    a, b = map(int, input().split())
    road_union.unite(a, b)

train_union = UnionFind(i for i in range(1, N + 1))
for _ in range(L):
    a, b = map(int, input().split())
    train_union.unite(a, b)

ma = dict()
for i in range(N):
    p = (road_union.find(i + 1), train_union.find(i + 1))
    ma[p] = ma.get(p, 0) + 1

for i in range(N):
    p = (road_union.find(i + 1), train_union.find(i + 1))
    print(ma[p], end=' ')

Solution (Python):
class UnionFindTree():
    
    
    
    
    def __init__(self, node_size):
        
        
        
        
        
        self.parent =[x for x in range(node_size)]
        self.node_size = node_size
        self.size = [1] * node_size
        self.rank = [1] * node_size

        
        self.member_dict = {}
    
    def find_root(self,node):
        
        
        if self.parent[node] == node:             
            root = node
        else:                                   
            root = self.find_root(self.parent[node]) 
            self.parent[node] = root            
        return root

    def unite(self,node0, node1):
        
        
        
        root_node0 = self.find_root(node0) 
        root_node1 = self.find_root(node1)

        if root_node0 != root_node1:
            
            

            
            if self.rank[root_node0] == self.rank[root_node1]: 
                self.parent[root_node1] = root_node0
                self.rank[root_node0] += 1
                self.size[root_node0] += self.size[root_node1]

            
            elif self.rank[root_node0] > self.rank[root_node1]:
                self.parent[root_node1] = root_node0
                self.size[root_node0] += self.size[root_node1]

            
            else:
                self.parent[root_node0] = root_node1
                self.size[root_node1] += self.size[root_node0]

    def same(self,node0,node1):
        
        return self.find_root(node0)==self.find_root(node1)




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

road_uft = UnionFindTree(N)
train_uft = UnionFindTree(N)

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

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


pair_dict = {}
pair_list = []
for i in range(N):
    road_root = road_uft.find_root(i)
    train_root = train_uft.find_root(i)
    pair = (road_root,train_root)
    pair_list.append(pair)
    if pair in pair_dict:
        pair_dict[pair] +=1
    else:
        pair_dict[pair] = 1

ans = ""
for i in range(N):
    pair = pair_list[i]
    ans += str(pair_dict[pair]) + " "
print(ans)

Solution (Python):
from collections import defaultdict
import sys
input = lambda: sys.stdin.readline().rstrip()

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

road_union = UnionFind(N)
rails_union = UnionFind(N)

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

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

    r -= 1
    s -= 1
    rails_union.union(r,s)

d = defaultdict(int)

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


print(*[d[(road_union.find(i),rails_union.find(i))] for i in range(N)])

Solution (Python):

class UnionFindTree():
    
    
    
    
    def __init__(self, node_size):
        
        
        
        
        
        self.parent =[x for x in range(node_size)]
        self.node_size = node_size
        self.size = [1] * node_size
        self.rank = [1] * node_size

        
        self.member_dict = {}
    
    def find_root(self,node):
        
        
        if self.parent[node] == node:             
            root = node
        else:                                   
            root = self.find_root(self.parent[node]) 
            self.parent[node] = root            
        return root

    def unite(self,node0, node1):
        
        
        
        root_node0 = self.find_root(node0) 
        root_node1 = self.find_root(node1)

        if root_node0 != root_node1:
            
            

            
            if self.rank[root_node0] == self.rank[root_node1]: 
                self.parent[root_node1] = root_node0
                self.rank[root_node0] += 1
                self.size[root_node0] += self.size[root_node1]

            
            elif self.rank[root_node0] > self.rank[root_node1]:
                self.parent[root_node1] = root_node0
                self.size[root_node0] += self.size[root_node1]

            
            else:
                self.parent[root_node0] = root_node1
                self.size[root_node1] += self.size[root_node0]

    def same(self,node0,node1):
        
        return self.find_root(node0)==self.find_root(node1)




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

road_uft = UnionFindTree(N)
train_uft = UnionFindTree(N)

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

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


pair_dict = {}
pair_list = []
for i in range(N):
    road_root = road_uft.find_root(i)
    train_root = train_uft.find_root(i)
    pair = (road_root,train_root)
    pair_list.append(pair)
    if pair in pair_dict:
        pair_dict[pair] +=1
    else:
        pair_dict[pair] = 1

ans = ""
for i in range(N):
    pair = pair_list[i]
    ans += str(pair_dict[pair]) + " "
print(ans)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations
    
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    

    

    N,K,L = map(int, input().split())
    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]
        
    douro = UnionFind(N+1)
    tetudou = UnionFind(N+1)
    for _ in range(K):
        p,q = map(int, input().split())
        douro.union(p,q)
    for _ in range(L):
        r,s = map(int, input().split())
        tetudou.union(r,s)
    dic = {}
    parlis = []
    for i in range(1, N+1):
        p1 = douro.find(i)
        p2 = tetudou.find(i)
        parlis.append((p1,p2))
        if (p1,p2) in dic:
            dic[(p1,p2)] += 1
        else: 
            dic[(p1,p2)] = 1
    print(' '.join([str(dic[parlis[i]]) for i in range(N)]))


if __name__ == '__main__':
    main()

Solution (Python):
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 unite(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 isSame(self, x, y):
        return self.find(x) == self.find(y)

from collections import defaultdict
def solve():
    N, K, L = map(int, input().split())
    road_uf = UnionFind(N)
    train_uf = UnionFind(N)

    for i in range(K):
        p, q = map(lambda x: int(x)-1, input().split())
        road_uf.unite(p, q)

    for i in range(L):
        r, s = map(lambda x: int(x)-1, input().split())
        train_uf.unite(r, s)

    ma = defaultdict(int)
    for v in range(N):
        root_road = road_uf.find(v)
        root_train = train_uf.find(v)
        ma[str(root_road) + "_" + str(root_train)] += 1
    
    for v in range(N):
        root_road = road_uf.find(v)
        root_train = train_uf.find(v)
        print(ma[str(root_road) + "_" + str(root_train)], end=' ')

if __name__ == '__main__':
    solve()

Solution (Python):
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 unite(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 isSame(self, x, y):
        return self.find(x) == self.find(y)

from collections import defaultdict
def solve():
    N, K, L = map(int, input().split())
    road_uf = UnionFind(N)
    train_uf = UnionFind(N)

    for i in range(K):
        p, q = map(lambda x: int(x)-1, input().split())
        road_uf.unite(p, q)

    for i in range(L):
        r, s = map(lambda x: int(x)-1, input().split())
        train_uf.unite(r, s)

    ma = defaultdict(int)
    for v in range(N):
        root_road = road_uf.find(v)
        root_train = train_uf.find(v)
        ma[str(root_road) + "_" + str(root_train)] += 1
    
    for v in range(N):
        root_road = road_uf.find(v)
        root_train = train_uf.find(v)
        print(ma[str(root_road) + "_" + str(root_train)], end=' ')

if __name__ == '__main__':
    solve()

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

R=[[] for i in range(N)]
T=[[] for i in range(N)]


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 isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  
  def Count(self, x):
    return -self.root[self.Find_Root(x)]

uniR=UnionFind(N)
for i in range(K):
  p,q=map(int, input().split())
  R[p-1].append(q-1)
  R[q-1].append(p-1)
  
  uniR.Unite(p-1,q-1)
uniT=UnionFind(N)  
for i in range(L):
  r, s=map(int, input().split())
  T[r-1].append(s-1)
  T[s-1].append(r-1)
  
  uniT.Unite(r-1,s-1)
dic = {}  
for i in range(N):
    val = (uniR.Find_Root(i), uniT.Find_Root(i))
    if val in dic:
        dic[val] += 1
    else:
        dic[val] = 1
        
for i in range(N):
    print(dic[(uniR.Find_Root(i), uniT.Find_Root(i))], end=" ")

Solution (Python):
from collections import defaultdict
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
n,k,l = map(int,input().split())
road = [list(map(int,input().split())) for i in range(k)]
train = [list(map(int,input().split())) for i in range(l)]
rg = [[] for i in range(n+1)]
rv = [0 for i in range(n+1)]
tg = [[] for i in range(n+1)]
tv = [0 for i in range(n+1)]
def connect(road,rg,rv):
  for a,b in road:
    rg[a].append(b)
    rg[b].append(a)
  cnt = 0
  for i in range(1,n+1):
    if rv[i] == 0:
      cnt += 1
      stack = [i]
      while stack:
        x = stack.pop()
        rv[x] = cnt
        for y in rg[x]:
          if rv[y] == 0:
            stack.append(y)
            rv[y] = cnt
connect(road,rg,rv)
connect(train,tg,tv)
condc = defaultdict(list)
for i in range(1,n+1):
  cr = rv[i]
  ct = tv[i]
  condc[(cr,ct)].append(i)
ans = []
for i in range(1,n+1):
  cr = rv[i]
  ct = tv[i]
  ans.append(len(condc[(cr,ct)]))
print(*ans)

Solution (Python):
from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

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

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

        if x == y:
            return False
        else:
            if self.d[x] > self.d[y]:
                x, y = y, x
            self.d[x] += self.d[y]
            self.d[y] = x
            return True

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


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


n, k, l = map(int, input().split())
uf1 = UnionFind(n)
for i in range(k):
    p, q = map(int, input().split())
    p -= 1
    q -= 1
    uf1.unite(p, q)
uf2 = UnionFind(n)
for i in range(l):
    r, s = map(int, input().split())
    r -= 1
    s -= 1
    uf2.unite(r, s)
dic = {}
for i in range(n):
    val = (uf1.find(i), uf2.find(i))
    if val in dic:
        dic[val] += 1
    else:
        dic[val] = 1

for i in range(n):
    print(dic[(uf1.find(i), uf2.find(i))])

Solution (Python):
from collections import defaultdict

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


def unite(x, y, parent):
    x = find(x, parent)
    y = find(y, parent)
    if x == y: return

    parent[y] = x

def solve():
    N, K, L = map(int, input().split())
    
    street = [i for i in range(N)]
    train = [i for i in range(N)]

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

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

    d = defaultdict(int)
    for i in range(N):
        a = find(street[i], street)
        b = find(train[i], train)
        d[(a, b)] += 1

    ans = []
    for i in range(N):
        a = find(street[i], street)
        b = find(train[i], train)
        ans.append(str(d[(a, b)]))

    print(' '.join(ans))

solve()