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.n = n
        self.parent = [i for i in range(n)]
        self.rank = [0 for i in range(n)]

    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):
        root_x = self.find(x)
        root_y = self.find(y)
        if (root_x == root_y):
            return
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x

        elif self.rank[root_y] > self.rank[root_x]:
            self.parent[root_x] = root_y

        else:
            self.parent[root_x] = root_y
            self.rank[root_y] += 1

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

    def memsInGroup(self, x):
        """
        O(N)かかります
        """
        root = self.find(x)
        return [i for i in range(N) if root == self.find(i)]

    def sizeOfGroup(self, x):
        return len(self.memsInGroup(x))

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.unite(p-1, q-1)

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

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

c = Counter(pair)

ans = [c[i] for i in pair]

print(*ans)

Solution (Python):
from collections import Counter
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1]*(n+1)
    self.rnk = [0]*(n+1)
  def find(self, x):
    if(self.root[x] < 0):
      return x
    else:
      self.root[x] = self.find(self.root[x])
      return self.root[x]
  def unite(self, x, y):
    x = self.find(x)
    y = self.find(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 same(self, x, y):
    return self.find(x) == self.find(y)
n,k,l=map(int,input().split())
e=[[i]for i in range(n+1)]
ur=UnionFind(n)
ut=UnionFind(n)
for i in range(k):
  a,b=map(int,input().split())
  ur.unite(a,b)
for _ in range(l):
  a,b=map(int,input().split())
  ut.unite(a,b)
pair=[(ur.find(i),ut.find(i)) for i in range(1,n+1)]
c=Counter(pair)
ans=[c[i] for i in pair]
print(*ans)

Solution (Python):
import sys
from collections import Counter


class UnionFindTree:
    def __init__(self, n: int) -> None:
        self.par = list(range(n))
        self.rank = [0] * n

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

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


def resolve(in_, out):
    N, K, L = map(int, next(in_).split())

    k = UnionFindTree(N + 1)
    l = UnionFindTree(N + 1)
    for _ in range(K):
        p, q = map(int, next(in_).split())
        k.unite(p, q)
    for _ in range(L):
        p, q = map(int, next(in_).split())
        l.unite(p, q)
   
    d = Counter((k.find(i), l.find(i)) for i in range(1, N + 1))

    ans = ' '.join(str(d[(k.find(i), l.find(i))]) for i in range(1, N + 1))
    print(ans)


def main():
    resolve(sys.stdin.buffer, sys.stdout)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter
n, k, l = map(int, input().split())
def find(x, par):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x], par)
        return par[x]
def unite(x, y, par):
    p = find(x, par)
    q = find(y, par)
    if p == q:
        return None
    if p > q:
        p, q = q, p
    par[p] += par[q]
    par[q] = p
def same(x, y):
    return find(x) == find(y)
def size(x):
    return -par[find(x)]
road_par = [-1 for i in range(n + 1)]
train_par = [-1 for i in range(n + 1)]
for i in range(k):
    p, q = map(int, input().split())
    unite(p, q, road_par)
for i in range(l):
    r, s = map(int, input().split())
    unite(r, s, train_par)
ans = []
for i in range(n):
    ans.append((find(i + 1, road_par), find(i + 1, train_par)))
c = Counter(ans)
for i in ans:
    print(c[i], end=" ")

Solution (Python):

import sys 
from collections import defaultdict
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines




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

def union(x,y,par):
    x = find(x,par)
    y = find(y,par)
    if x == y:
        return False
    else:
        
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y] 
        par[y] = x 
        return True


def same(x,y,par):
    return find(x) == find(y)


def size(x):
    return -par[find(x)]

N,K,L = map(int,readline().split())
par_road = [-1]*(N+1)
par_rail = [-1]*(N+1)


for i in range(K):
    x,y = map(int,readline().split())
    union(x,y,par_road)
    
for i in range(L):
    x,y = map(int,readline().split())
    union(x,y,par_rail)
    
num = []
d = defaultdict(int)  
for i in range(1,N+1):
    id = find(i,par_road)+find(i,par_rail)*10**6
    num.append(id)
    d[id] += 1

print(' '.join(str(d[n]) for n in num))

Solution (Python):
from collections import Counter
class UnionFind:
    def __init__(self,N):
        self.par=[i for i in range(N)]
        self.siz=[1 for _ in range(N)]
        self.rank=[0 for _ in range(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 union(self,a,b):
        a=self.find(a)
        b=self.find(b)
        if a==b:
            return 0
        else:
            if self.rank[a]>self.rank[b]:
                self.par[b]=a
                self.siz[a]+=self.siz[b]
            else:
                self.par[a]=b
                self.siz[b]+=self.siz[a]
                if self.rank[a]==self.rank[b]:
                    self.rank[b]+=1
    def size(self,a):
        return self.siz[self.find(a)]
    def same(self,a,b):
        return self.find(a)==self.find(b)

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

for i in range(K):
    p,q=map(lambda x:int(x)-1,input().split())
    road.union(p,q)
for i in range(L):
    r,s=map(lambda x:int(x)-1,input().split())
    train.union(r,s)
li=[(road.find(i),train.find(i)) for i in range(N)]
c=Counter(li)
ans=[c[li[i]] for i in range(N)]
print(*ans)

Solution (Python):
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy


class UnionFind:

    def __init__(self, n: int):
        self._n = n
        self._parents = [i for i in range(n)]
        self._size = [1 for _ in range(n)]

    def unite(self, x: int, y: int) -> None:
        px = self.find(x)
        py = self.find(y)

        
        if px != py:
            self._link(px, py)

    def _link(self, x: int, y: int):
        if self._size[x] < self._size[y]:
            self._parents[x] = y
            self._size[y] += self._size[x]
        else:
            self._parents[y] = x
            self._size[x] += self._size[y]

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

    def find(self, x: int) -> int:
        if self._parents[x] == x:
            return x

        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]

    def size(self, x: int):
        return self._size[self.find(self._parents[x])]

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

road = UnionFind(N + 1)
rail = UnionFind(N + 1)
share = UnionFind(N + 1)

roads = [list(map(int, input().split())) for _ in range(K)]
rails = [list(map(int, input().split())) for _ in range(L)]

for i in range(K):
    p, q = roads[i]
    road.unite(p, q)

for i in range(L):
    r, s = rails[i]
    rail.unite(r, s)

m = {}

for i in range(1, N + 1):
    cnt = m.get((road.find(i), rail.find(i)), 0)
    m[(road.find(i), rail.find(i))] = cnt + 1

ans = [0] * N
for i in range(N):
    ans[i] = m[(road.find(i + 1), rail.find(i + 1))]

print(*ans)

Solution (Python):
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy

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

road = [[] for i in range(n+1)]
rail = [[] for i in range(n+1)]

for i in range(k):
    p, q = list(map(int, input().split()))
    road[p].append(q)
    road[q].append(p)

for i in range(l):
    r, s = list(map(int, input().split()))
    rail[r].append(s)
    rail[s].append(r)

seen = [0 for i in range(n+1)]

def dfs_stack(u, al, al_c, d):
    stack = deque([u])
    seen[u] = 1

    while len(stack) > 0:
        v = stack.pop()
        
        al_c[v] = d
        

        for w in al[v]:
            if seen[w] == 0:
                stack.append(w)
                seen[w] = 1

        if stack == []: break


road_c = [-1 for i in range(n+1)]
rail_c = [-1 for i in range(n+1)]

d = 0
for i in range(1,n+1):
    if seen[i] == 0:
        dfs_stack(i, road, road_c, d)
        d += 1

seen = [0 for i in range(n+1)]

d = 0
for i in range(1,n+1):
    if seen[i] == 0:
        dfs_stack(i, rail, rail_c, d)
        d += 1

dict = {}

for i in range(1, n+1):
    if (road_c[i], rail_c[i]) not in dict:
        dict[(road_c[i], rail_c[i])] = [i]
    else:
        dict[(road_c[i], rail_c[i])].append(i)

ans = [0 for i in range(n+1)]

for dd in dict.items():
    for j in dd[1]:
        ans[j] = str(len(dd[1]))

print(' '.join(ans[1:]))

Solution (Python):
import collections

NO_OF_DIMENSIONS = 2
no_of_edges_by_dim = [None] * NO_OF_DIMENSIONS
n, no_of_edges_by_dim[0], no_of_edges_by_dim[1] = (int(x) for x in input().split())

graph_by_dimension = [[[] for _ in range(n + 1)] for _ in range(NO_OF_DIMENSIONS)]

for dimension, no_of_edges in enumerate(no_of_edges_by_dim):
    graph = graph_by_dimension[dimension]
    for _ in range(no_of_edges):
        p, q = (int(x) for x in input().split())
        graph[p].append(q)
        graph[q].append(p)

components_ids_by_vertex = [[None] * NO_OF_DIMENSIONS for _ in range(n + 1)]

def dfs(dimension_id, vertex_id, colour):
    stack = [vertex_id]
    while len(stack):
        vertex_id = stack.pop()
        components_ids_by_vertex[vertex_id][dimension_id] = colour
        for s in graph_by_dimension[dimension_id][vertex_id]:
            if not components_ids_by_vertex[s][dimension_id]:
                stack.append(s)

for i in range(NO_OF_DIMENSIONS):
    for j in range(1, n + 1):
        if not components_ids_by_vertex[j][i]:
            dfs(i, j, j)

components_ids_by_vertex = [tuple(x) for x in components_ids_by_vertex]

results = collections.Counter(components_ids_by_vertex)

for i in range(1, n + 1):
    print(results[components_ids_by_vertex[i]], end=' ')
print()

Solution (Python):
N, K, L = map(int,input().split())
 
road = [i for i in range(N)]
rail = [i for i in range(N)]
rank = [0 for i in range(N)]
 
def find(a, U):
  if a == U[a]:
    return a
  else:
    par = find(U[a], U)
    U[a] = par
    return par
  
for i in range(K):
  p, q = map(int,input().split())
  p -= 1
  q -= 1  
  a = find(p, road)
  b = find(q, road)
 
  road[a] = b
  
for i in range(L):
  p, q = map(int,input().split())
  p -= 1
  q -= 1  
  a = find(p, rail)
  b = find(q, rail)
 
  rail[a] = b
  
for i in range(N):
  
  road[i] = find(road[i],road)
  rail[i] = find(rail[i],rail)
  
rr = [(road[i], rail[i]) for i in range(N)]
D = {}
for r in rr:
  if not r in D:
    D[r] = 1
  else:
    D[r] += 1


 
for i in range(N):
  print(D[(road[i],rail[i])])

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

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

def unite(x,y):
  x,y=root(x),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=[-1]*N
  for _ in range(x):
    a,b=map(int,input().split())
    unite(a-1,b-1)
  return [root(i) for i in range(N)]

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

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

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

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

    def union_merge(self, x, y):
        x = self.find_root(x)
        y = self.find_root(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 union_size(self, x):
        
        return -self.parents[self.find_root(x)]

    def is_same_union(self, x, y):
        return self.find_root(x) == self.find_root(y)

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

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

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

    def all_unions(self):
        return [self.same_union_members(r) for r in self.roots()]

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

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

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

root_combinations = []
for i in range(N):
    root_combinations.append((road.find_root(i), rail.find_root(i)))

from collections import Counter
same_combinations = Counter(root_combinations)
result = [same_combinations[root_combination] for root_combination in root_combinations]

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

Solution (Python):
import sys
from collections import deque
from collections import defaultdict
from collections import Counter

def conn(n,m,e):
    d=dict(zip(range(1,n+1),range(-1,(-1)*n-1,-1)))
    td=defaultdict(lambda:deque([])) 
    c=1
    for edge in e:
        a=edge[0]
        b=edge[1]
        da=d[a] 
        db=d[b]
        if da<0 and db<0:
            d[a]=c
            d[b]=c
            td[c].append(a)
            td[c].append(b)
            c+=1
        elif da>0 and db<0:
            d[b]=da
            td[d[a]].append(b)
        elif da<0 and db>0:
            d[a]=db
            td[d[b]].append(a)
        elif da>0 and db>0 and da!=db:
            for x in td[db]:
                d[x]=da
                td[da].append(x)

    return list(d.values())




























           
def components(n,k,e):
    ed=defaultdict(lambda:deque())
    for edge in e:
        ed[edge[0]].append(edge[1])
        ed[edge[1]].append(edge[0])
    c=0
    s=[0]*n
    stack=deque()
    for i in range(1,n+1):
        if s[i-1]==0:
            c+=1
            stack.clear()
            stack.append(i)
            while stack:
                w=stack.pop()
                s[w-1]=c
                while ed[w]:
                    wn=ed[w].pop()
                    if s[wn-1]==0:
                        s[wn-1]=c
                        if ed[wn]:
                            stack.append(w)
                            w=wn
    return [s[i] for i in range(n)] 

def components2(n,k,e):
    es=deque(set((edge[0],edge[1])) for edge in e)
    c=0
    s=deque()
    stack=deque()
    while es:
        f=es.pop()
        stack.clear()
        while es:
            l=len(es)
            g=es.pop()
            if g&f:
                f|=g
            else:
                stack.append(g)
            if l==len(stack):
                s.append(f)
                break
            es=stack
    t=[0]*n
    c=0
    while s:
        for x in s.pop():
            t[x-1]=c
        c+=1
    return t
                
                
        
        
def main(n,k,l,e1,e2):
    d1=components(n,k,e1)
    d2=components(n,l,e2)
    p=tuple(zip(iter(d1),iter(d2)))
    d=Counter(p)
    
    print(' '.join([str(d[x]) for x in p])) 

if __name__=='__main__':
    ssr=sys.stdin.readline
    n,k,l=map(int,ssr().strip().split())
    e1=[]
    e2=[]
    for _ in range(k):
        e1.append(tuple(map(int,ssr().strip().split())))
    for _ in range(l):
        e2.append(tuple(map(int,ssr().strip().split())))
    main(n,k,l,e1,e2)

Solution (Python):
import sys
from collections import deque
from collections import defaultdict
from collections import Counter

def conn(n,m,e):
    d=dict(zip(range(1,n+1),range(-1,(-1)*n-1,-1)))
    td=defaultdict(lambda:deque([])) 
    c=1
    for edge in e:
        a=edge[0]
        b=edge[1]
        da=d[a] 
        db=d[b]
        if da<0 and db<0:
            d[a]=c
            d[b]=c
            td[c].append(a)
            td[c].append(b)
            c+=1
        elif da>0 and db<0:
            d[b]=da
            td[d[a]].append(b)
        elif da<0 and db>0:
            d[a]=db
            td[d[b]].append(a)
        elif da>0 and db>0 and da!=db:
            for x in td[db]:
                d[x]=da
                td[da].append(x)

    return list(d.values())

def components(n,k,e):
    ed=defaultdict(lambda:deque())
    for edge in e:
        ed[edge[0]].append(edge[1])
    c=0
    s=[0]*n
    label=[0]*n
    for i in range(1,n+1):
        if s[i-1]==0:
            c+=1
            label[c-1]=c
            stack=deque([i])
            while stack:
                w=stack.pop()
                s[w-1]=c
                while ed[w]:
                    wn=ed[w].pop()
                    if s[wn-1]==0:
                        s[wn-1]=c
                        if ed[wn]:
                            stack.append(w)
                            w=wn
                    elif s[wn-1]<c:
                        label[s[wn-1]-1]=c
    return [label[s[i]-1] for i in range(n)] 
           
def components2(n,k,e):
    ed=defaultdict(lambda:deque())
    for edge in e:
        ed[edge[0]].append(edge[1])
        ed[edge[1]].append(edge[0])
    c=0
    s=[0]*n
    for i in range(1,n+1):
        if s[i-1]==0:
            c+=1
            stack=deque([i])
            while stack:
                w=stack.pop()
                s[w-1]=c
                while ed[w]:
                    wn=ed[w].pop()
                    if s[wn-1]==0:
                        s[wn-1]=c
                        if ed[wn]:
                            stack.append(w)
                            w=wn
    return [s[i] for i in range(n)] 
def main(n,k,l,e1,e2):
    d1=components2(n,k,e1)
    d2=components2(n,l,e2)
    p=tuple(zip(iter(d1),iter(d2)))
    d=Counter(p)
    
    print(' '.join([str(d[x]) for x in p])) 

if __name__=='__main__':
    ssr=sys.stdin.readline
    n,k,l=map(int,ssr().strip().split())
    e1=[]
    e2=[]
    for _ in range(k):
        e1.append(tuple(map(int,ssr().strip().split())))
    for _ in range(l):
        e2.append(tuple(map(int,ssr().strip().split())))
    main(n,k,l,e1,e2)

Solution (Python):

class union_find:
    
    
    
    def __init__(self, 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 False
        else:
            
            if self.par[x] > self.par[y]:
                x,y = y,x
            self.par[x] += self.par[y]
            self.par[y] = x
            return True

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

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

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


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

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

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

cnt = Counter(pairs)
res = [cnt[pair] for pair in pairs]
print(*res)

Solution (Python):
import sys
from collections import deque
from collections import defaultdict
from collections import Counter

def conn(n,m,e):
    d=dict(zip(range(1,n+1),range(-1,(-1)*n-1,-1)))
    td=defaultdict(lambda:deque([])) 
    c=1
    for edge in e:
        a=edge[0]
        b=edge[1]
        da=d[a] 
        db=d[b]
        if da<0 and db<0:
            d[a]=c
            d[b]=c
            td[c].append(a)
            td[c].append(b)
            c+=1
        elif da>0 and db<0:
            d[b]=da
            td[d[a]].append(b)
        elif da<0 and db>0:
            d[a]=db
            td[d[b]].append(a)
        elif da>0 and db>0 and da!=db:
            for x in td[db]:
                d[x]=da
                td[da].append(x)

    return list(d.values())

def components(n,k,e):
    ed=defaultdict(lambda:deque())
    for edge in e:
        ed[edge[0]].append(edge[1])
        ed[edge[1]].append(edge[0])
    c=0
    s=[0]*n
    for i in range(1,n+1):
        if s[i-1]==0:
            c+=1
            stack=deque([i])
            while stack:
                w=stack.pop() 
                s[w-1]=c
                while ed[w]:
                    wn=ed[w].pop()
                    if s[wn-1]==0:
                        s[wn-1]=c
                        if ed[wn]:
                            stack.append(w)
                            w=wn
    return s
           
def main(n,k,l,e1,e2):
    d1=components(n,k,e1)
    d2=components(n,l,e2)
    p=tuple(zip(iter(d1),iter(d2)))
    d=Counter(p)
    
    d[(k,l)]=1
    print(' '.join([str(d[x]) for x in p])) 

if __name__=='__main__':
    ssr=sys.stdin.readline
    n,k,l=map(int,ssr().strip().split())
    e1=[]
    e2=[]
    for _ in range(k):
        e1.append(tuple(map(int,ssr().strip().split())))
    for _ in range(l):
        e2.append(tuple(map(int,ssr().strip().split())))
    main(n,k,l,e1,e2)

Solution (Python):
import sys
from collections import deque
from collections import defaultdict
from collections import Counter

def conn(n,m,e):
    d=dict(zip(range(1,n+1),range(-1,(-1)*n-1,-1)))
    td=defaultdict(lambda:deque([])) 
    c=1
    for edge in e:
        a=edge[0]
        b=edge[1]
        da=d[a] 
        db=d[b]
        if da<0 and db<0:
            d[a]=c
            d[b]=c
            td[c].append(a)
            td[c].append(b)
            c+=1
        elif da>0 and db<0:
            d[b]=da
            td[d[a]].append(b)
        elif da<0 and db>0:
            d[a]=db
            td[d[b]].append(a)
        elif da>0 and db>0 and da!=db:
            for x in td[db]:
                d[x]=da
                td[da].append(x)

    return list(d.values())

def main(n,k,l,e1,e2):
    d1=conn(n,k,e1)
    d2=conn(n,l,e2)
    p=tuple(zip(iter(d1),iter(d2)))
    d=Counter(p)
    
    d[(k,l)]=1
    print(' '.join([str(d[x]) for x in p]))

if __name__=='__main__':
    ssr=sys.stdin.readline
    n,k,l=map(int,ssr().strip().split())
    e1=[]
    e2=[]
    for _ in range(k):
        e1.append(tuple(map(int,ssr().strip().split())))
    for _ in range(l):
        e2.append(tuple(map(int,ssr().strip().split())))
    main(n,k,l,e1,e2)

Solution (Python):

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

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

def find(a, U):
  if a == U[a]:
    return a
  else:
    par = find(U[a], U)
    U[a] = par
    return par
  
for i in range(K):
  p, q = map(int,input().split())
  p -= 1
  q -= 1  
  a = find(p, road)
  b = find(q, road)

  road[a] = b
  
for i in range(L):
  p, q = map(int,input().split())
  p -= 1
  q -= 1  
  a = find(p, rail)
  b = find(q, rail)

  rail[a] = b
  
for i in range(N):
  
  road[i] = find(road[i],road)
  rail[i] = find(rail[i],rail)
  
rr = [(road[i], rail[i]) for i in range(N)]
D = {}
for r in rr:
  if not r in D:
    D[r] = 1
  else:
    D[r] += 1



for i in range(N):
  print(D[(road[i],rail[i])])

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

class UnionFind(object):
    def __init__(self, n):
        self._par = list(range(n))
        self.size = [1] * n
 
    def root(self, v):
        if self._par[v] == v:
            return v
        self._par[v] = self.root(self._par[v])
        return self._par[v]
 
    def unite(self, u, v):
        u, v = self.root(u), self.root(v)
        if u == v:
            return False
        if self.size[u] > self.size[v]:
            u, v = v, u 
        self.size[v] += self.size[u]
        self._par[u] = v
 
    def is_connected(self, u, v):
        return self.root(u) == self.root(v)


rood = UnionFind(n)
train = UnionFind(n)

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

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


from collections import Counter
cnt = Counter()
for i in range(n):
    root_r, root_t = rood.root(i), train.root(i)
    cnt[(root_r, root_t)] += 1

ans = []
for i in range(n):
    root_r, root_t = rood.root(i), train.root(i)
    ans.append(cnt[(root_r, root_t)])

print(*ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque, defaultdict


from collections import Counter

from itertools import accumulate,combinations,permutations

from heapq import heapify,heappop,heappush


from functools import reduce,lru_cache

from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
class unionfind:
    def __init__(self, elements=None):
        if elements is None:
            elements = ()
        self.parents = {}
        self.weights = {}
        for x in elements:
            self.weights[x] = 1
            self.parents[x] = x

    def __getitem__(self, i):
        
        if i not in self.parents:
            self.parents[i] = i
            self.weights[i] = 1
            return i
        path = [i]
        root = self.parents[i]
        while root != path[-1]:
            path.append(root)
            root = self.parents[root]
        for ancestor in path:
            self.parents[ancestor] = root
        return root

    def __iter__(self):
        return iter(self.parents)

    def union(self, *objects):
        roots = [self[x] for x in objects]
        heaviest = max(roots, key=lambda r: self.weights[r])
        for r in roots:
            if r != heaviest:
                self.weights[heaviest] += self.weights[r]
                self.parents[r] = heaviest

    def __len__(self):
        return len(self.parents)

def main():
    mod = 1000000007
    

    
    N, K, L = map(int, input().split())
    
    
     
    train=unionfind(range(N))
    rail=unionfind(range(N))

    for i in range(K):
        a,b = map(int,input().split())
        train.union(a-1,b-1)

    S = tuple(tuple(map(int, input().split())) for i in range(L))
    for a,b in S:
        a-=1
        b-=1
        rail.union(a,b)

    
    c=Counter()

    ans=[0]*N

    for i in range(N):
        c[rail[i]*N+train[i]]+=1
    for i in range(N):
        ans[i]=c[rail[i]*N+train[i]]
    print(*ans)
        
    





if __name__ == "__main__":
    main()

Solution (Python):
f=lambda:map(int,input().split())
n,k,l=f()
def root(x):
  while p[x]>=0: x=p[x]
  return x
def unite(x,y):
  x,y=root(x),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=[-1]*n
  for _ in range(x):
    a,b=f()
    unite(a-1,b-1)
  return [root(i) for i in range(n)]
from collections import *
z=[*zip(g(k),g(l))]
C=Counter(z)
print(*[C[t] for t in z])

Solution (Python):
f=lambda:map(int,input().split())
n,k,l=f()
def root(x):
  while p[x]>=0: x=p[x]
  return x
def unite(x,y):
  x,y=root(x),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=[-1]*n
  for _ in range(x):
    a,b=f()
    unite(a-1,b-1)
  return [root(i) for i in range(n)]
H,R=g(k),g(l)
from collections import *
z=[*zip(H,R)]
C=Counter(z)
print(*[C[t] for t in z])

Solution (Python):
f=lambda:map(int,input().split())
n,k,l=f()
def root(x):
  while p[x]>=0: x=p[x]
  return x
def unite(x,y):
  x,y=root(x),root(y)
  if x==y: return
  if x>y: x,y=y,x
  p[x]+=p[y]
  p[y]=x
def same(x,y):
  return root(x)==root(y)
def size(x):
  return -p[root(x)]
def root_all(x):
  global p
  p=[-1]*n
  for _ in range(x):
    a,b=f()
    unite(a-1,b-1)
  return [root(i) for i in range(n)]
H,R=root_all(k),root_all(l)
from collections import *
z=[*zip(H,R)]
C=Counter(z)
print(*[C[t] for t in z])