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 Counter

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

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

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

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

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

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 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
                
    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

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

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

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

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

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

    def find(self, x):
        """
        xの属する木の根を返す
        このとき同時に経路圧縮して、探索途中のノードを全て根に繋ぎ直す
        """
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        """
        x, yのそれぞれ属する木Tx, Tyの根同士を繋ぐ
        このとき木の要素数が小さい方を大きい方に繋ぐ（rankではなくsizeを用いる）
        """
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

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

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

    def size(self, x):
        """
        xの属する木の要素数を返す
        根の親を要素数の(-1)倍で定めておいたおかげでO(1)で取得可能
        """
        return -self.parents[self.find(x)]

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

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

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

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

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

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


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

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





if __name__ == "__main__":
    main()

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

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

    def merge(self, x, y):  
        x_root = self.root(x)  
        y_root = self.root(y)  

        if x_root == y_root:  
            return

        if abs(self.parents[x_root]) >= abs(self.parents[y_root]):  
            self.parents[x_root] += self.parents[y_root]
            self.parents[y_root] = x_root
        else:
            self.parents[y_root] += self.parents[x_root]
            self.parents[x_root] = y_root

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

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

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

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


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

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

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

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

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

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


if __name__ == "__main__":
    main()

Solution (Python):
from collections import Counter


class UnionFind:

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

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

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

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

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

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

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

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

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

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

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

Solution (Python):
from collections import Counter
import sys


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

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

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

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1


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

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


if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter
import sys


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

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

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

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1


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

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

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


if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter
from typing import AnyStr


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

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

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

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1


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

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


if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter


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

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

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

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1


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


if __name__ == '__main__':
    main()

Solution (Python):
class UnionFindTree:
    def __init__(self, n):
        self.nodes = [-1] * n 
    def find(self, i):
        if self.nodes[i] < 0: 
            return i
        else:
            self.nodes[i] = self.find(self.nodes[i]) 
            return self.nodes[i]

    def union(self, i, j):
        i = self.find(i)
        j = self.find(j)
        if i == j:
            return
        if self.nodes[i] > self.nodes[j]: 
            i, j = j, i
        self.nodes[i] += self.nodes[j] 
        self.nodes[j] = i 
    
    def size(self, i): 
        i = self.find(i)
        return -self.nodes[i]


n, k, l = map(int, input().split())
roads = UnionFindTree(n)
railways = UnionFindTree(n)
ans = []
for _ in range(k):
    a, b = map(lambda x : int(x) - 1, input().split())
    roads.union(a, b)
    
for _ in range(l):
    a, b = map(lambda x : int(x) - 1, input().split())
    railways.union(a, b)

counter = dict()
for i in range(n):
    p = (roads.find(i), railways.find(i))
    if not p in counter:
        counter[p] = 1
    else:
        counter[p] += 1

ans = [counter[(roads.find(i), railways.find(i))] for i in range(n)]
print(" ".join(map(str, ans)))

Solution (Python):
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict 
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  
  
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright





class UnionFind():
    def __init__(self,num):
        self.n = num         
        self.parents = [-1 for i in range(self.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):
        xx=self.find(x)  
        yy=self.find(y)  
        if xx==yy:
            return     
        else:
            size_xx=abs(self.parents[xx]) 
            size_yy=abs(self.parents[yy]) 
            if size_xx>size_yy:
                xx,yy=yy,xx  

            self.parents[yy]+=self.parents[xx] 
            self.parents[xx]=yy   

    
    def size(self,x):
        xx=self.find(x)
        return abs(self.parents[xx])

    
    def same(self,x,y):
        return 1 if self.find(x)==self.find(y) else 0

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

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

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

    
    def state_grouping(self):
        return list(self.all_group_members().values())

n,k,l=map(int,input().split())
uf=UnionFind(n)
uf2=UnionFind(n)
for i in range(k):
    p,q=map(int,input().split())
    p-=1;q-=1
    uf.union(p,q)
for i in range(l):
    p,q=map(int,input().split())
    p-=1;q-=1
    if 1:
        uf2.union(p,q)

C= Counter( [ ( uf.find(i),uf2.find(i) ) for i in range(n)] )
ANS=[0]*n 
for i in range(n):
    ANS[i]= C[(uf.find(i),uf2.find(i))]
print(*ANS)

Solution (Python):
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 union(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

N, K, L = map(int, input().split())
Uni_1 = UnionFind(N)
Uni_2 = UnionFind(N)
D = {}
for _ in range(K):
  p,q = map(int, input().split())
  Uni_1.union(p-1, q-1)
for _ in range(L):
  p,q = map(int, input().split())
  Uni_2.union(p-1, q-1)
for i in range(N):
  k = (Uni_1.find(i), Uni_2.find(i))
  if k in D.keys():
    D[k] += 1
  else:
    D[k] = 1
for i in range(N):
  print(D[(Uni_1.find(i), Uni_2.find(i))], end=" ")

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

def fp(x, parentList): 
    if parentList[x] == x:
        return x
    else:
        parentList[x] = fp(parentList[x], parentList)
        return parentList[x]


road = [i for i in range(N)]
rail = [i for i in range(N)]

for _ in range(K):
    p, q = map(int, input().split())
    par_p, par_q = fp(p-1, road), fp(q-1, road) 
    
    if par_p < par_q:
        road[par_q] = par_p
    else:
        road[par_p] = par_q


for _ in range(L):
    s, t = map(int, input().split())
    par_s, par_t = fp(s-1, rail), fp(t-1, rail)
    if par_s < par_t:
        rail[par_t] = par_s
    else:
        rail[par_s] = par_t


cnt = {}
for i in range(N):
    key = (fp(i,road),fp(i,rail))
    if key in cnt:
        cnt[key] += 1
    else:
        cnt[key] = 1

for i in range(N):
    key = (fp(i,road),fp(i,rail))
    ans = cnt[key]
    print(ans, end=" ")

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

def root(x):
  while 0<=p[x]:
    x = p[x]
  return x

def unite(x,y):
  x = root(x)
  y = root(y)
  if x==y:
    return
  if x>y:
    x,y=y,x
  p[x]+=p[y]
  p[y]=x

def g(x):
  global p
  p=N*[-1]
  for _ in range(x):
    a,b = map(int,input().split())
    unite(a-1,b-1)
  return [root(n) for n in range(N)]

z = [*zip(g(K),g(L))]
C = Counter(z)
print(*[C[t] for t in z])

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

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

N, K, L = mapint()
uf_road = UnionFind(N)
for _ in range(K):
    x, y = mapint()
    uf_road.union(x-1, y-1)

uf_rail = UnionFind(N)
for _ in range(L):
    x, y = mapint()
    uf_rail.union(x-1, y-1)
from collections import Counter
lis = []
for i in range(N):
    road = uf_road.find(i)
    rail = uf_rail.find(i)
    lis.append(road*(10**6)+rail)
c = Counter(lis)
ans = []
for i in range(N):
    road = uf_road.find(i)
    rail = uf_rail.find(i)
    ans.append(str(c[(road*(10**6)+rail)]))
print(' '.join(ans))

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

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

N, K, L = mapint()
uf_road = UnionFind(N)
for _ in range(K):
    x, y = mapint()
    uf_road.union(x-1, y-1)

uf_rail = UnionFind(N)
for _ in range(L):
    x, y = mapint()
    uf_rail.union(x-1, y-1)
from collections import Counter
lis = []
for i in range(N):
    road = uf_road.find(i)
    rail = uf_rail.find(i)
    lis.append((road, rail))
c = Counter(lis)

ans = []
for i in range(N):
    road = uf_road.find(i)
    rail = uf_rail.find(i)
    ans.append(str(c[(road, rail)]))
print(' '.join(ans))

Solution (Python):
class UnionFind:
  def __init__(self, N):
    self.par=[i for i in range(N)]
    self.rank=[0 for _ in range(N)]
    self.size=[1 for _ in range(N)]
    
  def unite(self, x, y):
    x=self.getroot(x)
    y=self.getroot(y)
    if x!=y:
      if self.rank[x]<self.rank[y]:
        x, y=y, x
      if self.rank[x]==self.rank[y]:
        self.rank[x]+=1
      self.par[y]=x
      self.size[x]+=self.size[y]
      
  def united(self, x, y):
    return self.getroot(x)==self.getroot(y)
      
  def getroot(self, x):
    if self.par[x]==x:
      return x
    else:
      self.par[x]=self.getroot(self.par[x])
      return self.par[x]

  def getsize(self, x):
    return self.size[self.getroot(x)]
  
from collections import defaultdict

N, K, L=map(int, input().split())
UF1=UnionFind(N+1)
UF2=UnionFind(N+1)
for _ in range(K):
  p, q=map(int, input().split())
  UF1.unite(p, q)
  
for _ in range(L):
  r, s=map(int, input().split())
  UF2.unite(r, s)
  
nums=defaultdict(int)
for i in range(1, N+1):
  nums[str(UF1.getroot(i))+'_'+str(UF2.getroot(i))]+=1
  
for i in range(1, N+1):
  print(nums[str(UF1.getroot(i))+'_'+str(UF2.getroot(i))])

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k,l = list(map(int, input().split()))
from collections import defaultdict
ns0 = defaultdict(list)
ns1 = defaultdict(list)
for i in range(k):
    p,q = map(int, input().split())
    p-=1;q-=1
    ns0[p].append(q)
    ns0[q].append(p)
for i in range(l):
    p,q = map(int, input().split())
    p-=1;q-=1
    ns1[p].append(q)
    ns1[q].append(p)
def sub(ns):
    seen = [None]*n
    num = 1
    for i in range(n):
        if seen[i] is not None:
            continue
        q = [i]
        seen[i] = num
        while q:
            u = q.pop()
            for v in ns[u]:
                if seen[v] is not None:
                    continue
                seen[v] = num
                q.append(v)
        num += 1
    return seen

s1 = sub(ns0)
s2 = sub(ns1)

import gc
del ns0, ns1
gc.collect()

from collections import Counter
c = Counter([(s1[i], s2[i]) for i in range(n)])
ans = [(c[s1[i],s2[i]]) for i in range(n)]
write(" ".join(map(str, ans)))

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k,l = list(map(int, input().split()))
from collections import defaultdict
ns0 = defaultdict(list)
ns1 = defaultdict(list)
for i in range(k):
    p,q = map(int, input().split())
    p-=1;q-=1
    ns0[p].append(q)
    ns0[q].append(p)
for i in range(l):
    p,q = map(int, input().split())
    p-=1;q-=1
    ns1[p].append(q)
    ns1[q].append(p)
def sub(ns):
    seen = [None]*n
    num = 1
    for i in range(n):
        if seen[i] is not None:
            continue
        q = [i]
        seen[i] = num
        while q:
            u = q.pop()
            for v in ns[u]:
                if seen[v] is not None:
                    continue
                seen[v] = num
                q.append(v)
        num += 1
    return seen

s1 = sub(ns0)
s2 = sub(ns1)

import gc
del ns0, ns1
gc.collect()

d1 = [None]*(max(s1)+1)
d2 = [None]*(max(s2)+1)
def update(d,ind,i):
    if d[ind] is None:
        d[ind] = set([i])
    else:
        d[ind].add(i)
for i in range(n):
    update(d1,s1[i],i)
    update(d2,s2[i],i)


d = {}
ans = [None]*n
for i in range(n):
    u,v = s1.pop(), s2.pop()
    if (u,v) not in d:
        d[u,v] = len(d1[u] & d2[v])
    ans[-(i+1)] = d[u,v]
write(" ".join(map(str, ans)))

Solution (Python):
from collections import Counter

class UnionFind:
  def __init__(self, n):
    self.n = 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 unite(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x == y:
      return
    if self.rank[x] < self.rank[y]:
      self.par[x] = y
    else:
      self.par[y] = x
      if self.rank[x] == self.rank[y]:
        self.rank[x] += 1
        
        
  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]
  

n, k, l  = 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_pq = UnionFind(n)
uf_rs = UnionFind(n)

for p in pq:
  x, y = p
  uf_pq.unite(x-1, y-1)
  
for r in rs:
  x, y = r
  uf_rs.unite(x-1, y-1)
  
pairs = []
for i in range(n):
  pairs.append((uf_pq.find(i), uf_rs.find(i)))
  
count = Counter(pairs)

ans = [count[pair] for pair in pairs]
print(*ans)

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import Counter, deque, defaultdict

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

    edge1 = defaultdict(list)

    for _ in range(k):
        p, q = map(int, readline().split())
        edge1[p - 1].append(q - 1)
        edge1[q - 1].append(p - 1)

    a = [-1] * n
    que = deque()

    for i in range(n):
        if a[i] == -1:
            que.append(i)
            a[i] = i
            while que:
                cur = que.popleft()
                for nx in edge1[cur]:
                    if a[nx] == -1:
                        a[nx] = i
                        que.append(nx)

    edge2 = defaultdict(list)

    for _ in range(l):
        r, s = map(int, readline().split())
        edge2[r - 1].append(s - 1)
        edge2[s - 1].append(r - 1)

    b = [-1] * n
    que = deque()

    for i in range(n):
        if b[i] == -1:
            que.append(i)
            b[i] = i
            while que:
                cur = que.popleft()
                for nx in edge2[cur]:
                    if b[nx] == -1:
                        b[nx] = i
                        que.append(nx)

    c = Counter()
    for i in range(n):
        c[(a[i], b[i])] += 1

    res = [0] * n
    for i in range(n):
        res[i] = c[(a[i], b[i])]

    print(*res)


if __name__ == '__main__':
    main()