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):
import sys
input = sys.stdin.readline
from collections import *

class Unionfind:
    def __init__(self, n):
        self.par = [-1]*n
        self.rank = [1]*n
    
    def root(self, x):
        r = x
        
        while not self.par[r]<0:
            r = self.par[r]
        
        t = x
        
        while t!=r:
            tmp = t
            t = self.par[t]
            self.par[tmp] = r
        
        return r
    
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        
        if rx==ry:
            return
        
        if self.rank[rx]<=self.rank[ry]:
            self.par[ry] += self.par[rx]
            self.par[rx] = ry
            
            if self.rank[rx]==self.rank[ry]:
                self.rank[ry] += 1
        else:
            self.par[rx] += self.par[ry]
            self.par[ry] = rx
    
    def is_same(self, x, y):
        return self.root(x)==self.root(y)
    
    def count(self, x):
        return -self.par[self.root(x)]

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

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

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

d = defaultdict(int)

for i in range(N):
    a = uf1.root(i)
    b = uf2.root(i)
    d[10**6*a+b] += 1
    
ans = []

for i in range(N):
    a = uf1.root(i)
    b = uf2.root(i)
    ans.append(d[10**6*a+b])

print(*ans)

Solution (Python):
from collections import defaultdict


class UnionFind:

    def __init__(self, n):
        
        self.parents = [i for i in range(n + 1)]
        self.ranks = [0 for _ in range(n + 1)]

    def find_root(self, node):
        parent_node = self.parents[node]
        if parent_node == node:
            return node
        else:
            root_node = self.find_root(parent_node)
            self.parents[node] = root_node  
            return root_node

    def union(self, one, other):
        one_root = self.find_root(one)
        other_root = self.find_root(other)
        if one_root == other_root:
            return
        if self.ranks[one_root] < self.ranks[other_root]:
            self.parents[one_root] = other_root
        else:
            self.parents[other_root] = one_root
            if self.ranks[one_root] == self.ranks[other_root]:
                self.ranks[one_root] += 1

    def is_same_group(self, one, other):
        one_root = self.find_root(one)
        other_root = self.find_root(other)
        return one_root == other_root


def main():
    N, K, L = list(map(int, input().split(' ')))
    road_tree = UnionFind(N)
    for _ in range(K):
        p, q = list(map(int, input().split(' ')))
        road_tree.union(p, q)
    train_tree = UnionFind(N)
    for _ in range(L):
        r, s = list(map(int, input().split(' ')))
        train_tree.union(r, s)
    
    group_count = defaultdict(int)
    group_list = list()
    for node in range(1, N + 1):
        group = (road_tree.find_root(node), train_tree.find_root(node))
        group_count[group] += 1
        group_list.append(group)
    answer = ' '.join(list(map(
        lambda g: str(group_count[g]),
        group_list
    )))
    print(answer)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict
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 = map(int, input().split())

uf = UnionFind(n)

p, q = [0] * k, [0] * k
for i in range(k):
    pp, qq = map(int, input().split())
    p[i] = pp - 1 
    q[i] = qq - 1
    uf.union(pp - 1, qq - 1)

uuff = UnionFind(n)
r, s = [0] * l, [0] * l
for i in range(l):
    rr, ss = map(int, input().split())
    r[i] = rr - 1
    s[i] = ss - 1
    uuff.union(rr - 1, ss - 1)
dic = defaultdict(int)
for i in range(n):
    dic[(uf.find(i), uuff.find(i))] += 1

ans = []
for i in range(n):
    ans.append(dic[uf.find(i), uuff.find(i)])

for i in ans:
    print(i,end=" ")

Solution (Python):
import sys
from collections import defaultdict


def input():
    return sys.stdin.readline().strip()


class UnionFind:
    def __init__(self, n_nodes):
        self.n_nodes = n_nodes
        self.parent = [i for i in range(n_nodes)]
        self.rank = [1] * n_nodes
        self.size = [1] * n_nodes

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

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

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

    def get_parent_list(self):
        return [i for i in range(self.n_nodes) if self.find(i) == i]

    def get_n_groups(self):
        return len(self.get_parent_list())

    def get_members(self, x):
        parent = self.find(x)
        return [i for i in range(self.n_nodes) if self.find(i) == parent]

    def get_members_dict(self):
        return {par: self.get_members(par) for par in self.get_parent_list()}


def main():
    N, K, L = map(int, input().split())
    Tree_road = UnionFind(N)
    Tree_train = UnionFind(N)
    for _ in range(K):
        p, q = map(int, input().split())
        Tree_road.unite(p - 1, q - 1)
    for _ in range(L):
        p, q = map(int, input().split())
        Tree_train.unite(p - 1, q - 1)
    DD = defaultdict(int)
    for i in range(N):
        DD[(Tree_road.find(i), Tree_train.find(i))] += 1
    answer = []
    for i in range(N):
        answer.append(DD[(Tree_road.find(i), Tree_train.find(i))])

    print(*answer, sep=" ")


if __name__ == "__main__":
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


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

    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 get_size(self, x):
        return -self.parents[self.find(x)]

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

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

    def get_members(self, x):
        parent = self.find(x)
        return [i for i in range(self.n_nodes) if self.find(i) == parent]

    def get_members_dict(self):
        return {par: self.get_members(par) for par in self.get_parent_list()}


def main():
    N, K, L = map(int, input().split())
    tree_road = UnionFind(N)
    tree_subway = UnionFind(N)

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

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

    d = {}
    for i in range(N):
        p1 = tree_road.find(i)
        p2 = tree_subway.find(i)
        if (p1, p2) not in d:
            d[(p1, p2)] = 1
        else:
            d[(p1, p2)] += 1

    for i in range(N):
        p1 = tree_road.find(i)
        p2 = tree_subway.find(i)
        print(d[(p1, p2)], end=" ")


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

import sys
def input():
    return sys.stdin.readline().strip()

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

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

dic = {}
l = []
for i in range(n):
    tup = (road.find(i), rail.find(i))
    l.append(tup)
    if tup in dic:
        dic[tup] += 1
    else:
        dic[tup] = 1

ans = []
for i in l:
    ans.append(dic[i])

print(' '.join(map(str, ans)))

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

import sys
def input():
    return sys.stdin.readline().strip()

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

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

dic = {}
l = []
for i in range(n):
    tup = (road.find(i), rail.find(i))
    l.append(tup)
    if tup in dic:
        dic[tup] += 1
    else:
        dic[tup] = 1

ans = []
for i in l:
    ans.append(dic[i])

print(' '.join(map(str, ans)))

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

import sys
def input():
    return sys.stdin.readline().strip()

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

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

dic = {}
l = []
for i in range(n):
    tup = (road.find(i), rail.find(i))
    l.append(tup)
    if tup in dic:
        dic[tup] += 1
    else:
        dic[tup] = 1

ans = []
for i in l:
    ans.append(dic[i])

print(' '.join(map(str, ans)))

Solution (Python):
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 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
        elif self.rank[x] > self.rank[y]:
            self.par[y] = x
        else:
            self.par[y] = x
            self.rank[x] += 1

N,K,L = map(int,input().split())
A = [list(map(int,input().split())) for i in range(K)]
B = [list(map(int,input().split())) for i in range(L)]

road = UnionFind(N)
train = UnionFind(N)

for i in range(K):
    road.union(A[i][0],A[i][1])
for i in range(L):
    train.union(B[i][0],B[i][1])

pair = [(road.find(i),train.find(i)) for i in range(1,N+1)]

from collections import Counter



c = Counter(pair)
print(*[c[i] for i in pair])

Solution (Python):
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 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
        elif self.rank[x] > self.rank[y]:
            self.par[y] = x
        else:
            self.par[y] = x
            self.rank[x] += 1

N,K,L = map(int,input().split())
A = [list(map(int,input().split())) for i in range(K)]
B = [list(map(int,input().split())) for i in range(L)]

road = UnionFind(N)
train = UnionFind(N)

for i in range(K):
    road.union(A[i][0],A[i][1])
for i in range(L):
    train.union(B[i][0],B[i][1])

pair = [(road.find(i),train.find(i)) for i in range(1,N+1)]

from collections import Counter



c = Counter(pair)
print(*[c[i] for i in pair])

Solution (Python):
from collections import Counter


class UnionFind:
    def __init__(self, n):
        
        self.n = n
        
        self._root_table = list(range(n))
        
        self._size_table = [1] * n

    def find(self, x):
        """Returns x's root node id."""
        r = self._root_table[x]
        if r != x:
            
            r = self._root_table[x] = self.find(r)
        return r

    def union(self, x, y):
        """Merges two groups."""
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        
        if self._size_table[x] < self._size_table[y]:
            x, y = y, x

        self._size_table[x] += self._size_table[y]
        self._root_table[y] = x

    def size(self, x):
        return self._size_table[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._root_table) if x == i]

    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 = map(int, input().split())
roads = UnionFind(N)
rails = UnionFind(N)
for i in range(K):
    p, q = map(int, input().split())
    roads.union(p - 1, q - 1)
for i in range(L):
    r, s = map(int, input().split())
    rails.union(r - 1, s - 1)
c = Counter()
for i in range(N):
    gid = roads.find(i) * N + rails.find(i)
    c[gid] += 1

print(*[c[roads.find(i) * N + rails.find(i)] for i in range(N)])

Solution (Python):
class UnionFind:
    """素集合を木構造として管理する"""
    def __init__(self, n):
        self.parent = [-1] * n
        self.cnt = n

    def root(self, x):
        """要素xの根を求める"""
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]

    def merge(self, x, y):
        """要素xを含む集合と要素yを含む集合を統合する"""
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.parent[x] > self.parent[y]:
            x, y = y, x
        self.parent[x] += self.parent[y]
        self.parent[y] = x
        self.cnt -= 1

    def is_same(self, x, y):
        """要素x, yが同じ集合に属するかどうかを求める"""
        return self.root(x) == self.root(y)

    def get_size(self, x):
        """要素xを含む集合の要素数を求める"""
        return -self.parent[self.root(x)]


n, k, l = map(int, input().split())
info_k = [list(map(int, input().split())) for i in range(k)]
info_l = [list(map(int, input().split())) for i in range(l)]

ufk = UnionFind(n)
ufl = UnionFind(n)
uf_total = UnionFind(n)

for a, b in info_k:
    a -= 1
    b -= 1
    ufk.merge(a, b)

for a, b in info_l:
    a -= 1
    b -= 1
    ufl.merge(a, b)

pair_cnt = {}
for i in range(n):
    if (ufk.root(i), ufl.root(i)) not in pair_cnt:
        pair_cnt[ufk.root(i), ufl.root(i)] = 1
    else:
        pair_cnt[ufk.root(i), ufl.root(i)] += 1

ans = [pair_cnt[ufk.root(i), ufl.root(i)] for i in range(n)]
print(*ans)

Solution (Python):

import io
import math
import string

def col(n, m):
    X = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        X[a-1].append(b-1)
        X[b-1].append(a-1)
    C = [-1] * n
    c = 0
    for i in range(N):
        if C[i] >= 0: continue
        Q = [i]
        C[i] = c
        while Q:
            x = Q.pop()
            for y in X[x]:
                if C[y] == -1:
                    C[y] = C[x]
                    Q.append(y)
        c += 1
    return C

N, K, L = map(int, input().split())
A = col(N, K)
B = col(N, L)
D = {}
for a, b in zip(A, B):
    t = (a<<18) + b
    if t in D: D[t] += 1
    else: D[t] = 1

print(*[D[(a<<18)+b] for a, b in zip(A, B)])

Solution (Python):
from collections import Counter


class UnionFind:
  def __init__(self, n):
    self.par = [x for x in range(n)]
    
  def find(self, x):
    if x == self.par[x]:
      return x
    self.par[x] = self.find(self.par[x])
    return self.par[x]
  
  def unite(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x != y:
      self.par[y] = x

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

rails = UnionFind(N + 1)
roads = UnionFind(N + 1)

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

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

counter = Counter([
  (rails.find(p), roads.find(p))
  for p in range(1, N + 1)
])

print(' '.join(
  str(counter[(rails.find(i), roads.find(i))])
  for i in range(1, N + 1)
))

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

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

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

        if x == y:
            return

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

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


def main():
    import sys
    from collections import Counter
    
    readlines = sys.stdin.readlines
    N, K, L = map(int, input().split())
    uf1 = UnionFind(N)
    uf2 = UnionFind(N)

    IN = readlines()
    for i in range(K):
        p, q = map(int, IN[i].split())
        p -= 1; q -= 1
        uf1.union(p, q)
    for j in range(K, K + L):
        r, s = map(int, IN[j].split())
        r -= 1; s -= 1
        
        uf2.union(r, s)
    
    
    
    
    
    path = []
    C = Counter()
    for i in range(N):
        pair = (uf1.find(i), uf2.find(i))
        path.append(pair)
        C[pair] += 1

    ans = []
    for i in range(N):
        ans.append(C[path[i]])
    print(*ans)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import Counter
def find(x):
    if(par[x]==x):
        return x
    else:
        par[x]=find(par[x])
        return par[x]

def union(a,b):
    a=find(a)
    b=find(b)
    if(a==b):
        return 0
    else:
        if rank[a]>rank[b]:
            par[b]=a
            siz[a]+=siz[b]
        else:
            par[a]=b
            siz[b]+=siz[a]
            if rank[a]==rank[b]:
                rank[b]+=1
            
def size(a):
    return siz[find(a)]

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

N,K,L=map(int,input().split())
par=[i for i in range(N)]
siz=[1 for _ in range(N)]
rank=[0 for _ in range(N)]

for i in range(K):
    p,q=map(lambda x:int(x)-1,input().split())
    union(p,q)
    
road=[find(i) for i in range(N)]
par=[i for i in range(N)]
siz=[1 for _ in range(N)]
rank=[0 for _ in range(N)]
for i in range(L):
    r,s=map(lambda x:int(x)-1,input().split())
    union(r,s)
li=[(road[i],find(i)) for i in range(N)]
c=Counter(li)
for i in range(N):
    print(c[li[i]],end=' ')
print()

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

N,K,L=list(map(int,input().split()))
pq=[list(map(int,input().split())) for i in range(K)]
rs=[list(map(int,input().split())) for i in range(L)]

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

for i in range(K):
    uf_road.union(pq[i][0]-1,pq[i][1]-1)
for i in range(L):
    uf_train.union(rs[i][0]-1,rs[i][1]-1)








from collections import Counter
pair = [(uf_road.find(i), uf_train.find(i)) for i in range(N)]
ans = Counter(pair)
print(*[ans[i] for i in pair])

Solution (Python):
from collections import defaultdict

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

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

road = UnionFind(N)
railway = UnionFind(N)

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

for _ in range(L):
    p, q = map(int, input().split())
    railway.union(p-1, q-1)

counter = defaultdict(int)
for i in range(N):
    counter[(road.find(i), railway.find(i))] += 1
ans = []
for i in range(N):
    ans.append(counter[(road.find(i), railway.find(i))])

print(*ans)

Solution (Python):
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
from pprint import pprint

def myinput():
    return map(int,input().split())

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

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 = myinput()
pq = [ list(myinput()) for _ in range(k) ]
rs = [ list(myinput()) for _ in range(l) ]

uf1 = UnionFind(n)
for i in range(k):
    p = pq[i][0]
    q = pq[i][1]
    uf1.union(p-1,q-1)

uf2 = UnionFind(n)
for i in range(l):
    r = rs[i][0]
    s = rs[i][1]
    uf2.union(r-1,s-1)

d = defaultdict(lambda: 0)

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

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

Solution (Python):
from collections import defaultdict


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

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if 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 same(self, x, y):
        return self.find(x) == self.find(y)


def main():
    n, k, l = map(int, input().split())
    
    road = UnionFind(n)
    train = 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())
        train.unite(r-1, s-1)
        
    d = defaultdict(int)
    for i in range(n):
        d[(road.find(i), train.find(i))] += 1
    
    ans = []
    for i in range(n):
        ans.append(d[(road.find(i), train.find(i))])
    
    print(*ans)


if __name__ == "__main__":
    main()

Solution (Python):
"""
in1 = '7 4 4'
in2 = ['1 2', '2 3', '2 5', '6 7', '3 5', '4 5', '3 4', '6 7']
N, K, L = map(int, in1.split())
pqrs = []
for idx1 in range(K + L):
    temp0, temp1 = map(int, in2[idx1].split())
    pqrs.append([temp0, temp1])
"""

def makeTree(a):
    aT = list(range(N + 1))
    for p, q in a:
        rootp     = getRoot(aT, p)
        rootq     = getRoot(aT, q)
        thisRoot  = max(rootp, rootq, q)
        aT[p]     = thisRoot
        aT[q]     = thisRoot
        aT[rootp] = thisRoot
        aT[rootq] = thisRoot
    return aT

def getRoot(a,i):
    if a[i] == i:
        return i
    else:
        a[i] = getRoot(a, a[i])
        return a[i]

N, K, L = map(int, input().split())
pqrs = []
for idx1 in range(K + L):
    temp0, temp1 = map(int, input().split())
    pqrs.append([temp0, temp1])

MTree = makeTree(pqrs[0:K])
TTree = makeTree(pqrs[K:])

aRet = []
dRet = {}
for idx1 in range(1, N + 1):
    Comb = (getRoot(MTree, idx1), getRoot(TTree, idx1))
    aRet.append(Comb)
    if Comb in dRet:
        dRet[Comb] += 1
    else:
        dRet[Comb] = 1

print(" ".join([str(dRet[_]) for _ in aRet]))