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

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

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

city_road_train=set()

city_roadgroup_dict={}
roadgroup_city_dict={}

city_traingroup_dict={}
traingroup_city_dict={}

for ch_pq in pq:

  if not ch_pq[0] in city_roadgroup_dict:
    if not ch_pq[1] in city_roadgroup_dict:
      new_group_num=ch_pq[0]
      city_roadgroup_dict[ch_pq[0]]=new_group_num
      city_roadgroup_dict[ch_pq[1]]=new_group_num
      roadgroup_city_dict[new_group_num]=set([ch_pq[0],ch_pq[1]])
    else:
      group_num=city_roadgroup_dict[ch_pq[1]]
      city_roadgroup_dict[ch_pq[0]]=group_num
      roadgroup_city_dict[group_num].add(ch_pq[0])
  else:
    if not ch_pq[1] in city_roadgroup_dict:
      group_num=city_roadgroup_dict[ch_pq[0]]
      city_roadgroup_dict[ch_pq[1]]=group_num
      roadgroup_city_dict[group_num].add(ch_pq[1])
    else:
      group_num_0=city_roadgroup_dict[ch_pq[0]]
      group_num_1=city_roadgroup_dict[ch_pq[1]]
      if group_num_0!=group_num_1:
        group_0=roadgroup_city_dict[group_num_0]
        group_1=roadgroup_city_dict[group_num_1]
        if len(group_0)<len(group_1):
          for city_n in list(group_0):
            city_roadgroup_dict[city_n]=group_num_1
          roadgroup_city_dict[group_num_1]|=group_0
          del roadgroup_city_dict[group_num_0]

        else:
          for city_n in list(group_1):
            city_roadgroup_dict[city_n]=group_num_0
          roadgroup_city_dict[group_num_0]|=group_1
          del roadgroup_city_dict[group_num_1]


for ch_rs in rs:
  for rs_i in range(2): 
    if not ch_rs[rs_i] in city_road_train and ch_rs[rs_i] in city_roadgroup_dict:
      city_road_train.add(ch_rs[rs_i])
  
  if not ch_rs[0] in city_traingroup_dict:
    if not ch_rs[1] in city_traingroup_dict:
      new_group_num=ch_rs[0]
      city_traingroup_dict[ch_rs[0]]=new_group_num
      city_traingroup_dict[ch_rs[1]]=new_group_num
      traingroup_city_dict[new_group_num]=set([ch_rs[0],ch_rs[1]])
    else:
      group_num=city_traingroup_dict[ch_rs[1]]
      city_traingroup_dict[ch_rs[0]]=group_num
      traingroup_city_dict[group_num].add(ch_rs[0])
  else:
    if not ch_rs[1] in city_traingroup_dict:
      group_num=city_traingroup_dict[ch_rs[0]]
      city_traingroup_dict[ch_rs[1]]=group_num
      traingroup_city_dict[group_num].add(ch_rs[1])
    else:
      group_num_0=city_traingroup_dict[ch_rs[0]]
      group_num_1=city_traingroup_dict[ch_rs[1]]
      if group_num_0!=group_num_1:
        group_0=traingroup_city_dict[group_num_0]
        group_1=traingroup_city_dict[group_num_1]
        if len(group_0)<len(group_1):
          for city_n in list(group_0):
            city_traingroup_dict[city_n]=group_num_1
          traingroup_city_dict[group_num_1]|=group_0
          del traingroup_city_dict[group_num_0]

        else:
          for city_n in list(group_1):
            city_traingroup_dict[city_n]=group_num_0
          traingroup_city_dict[group_num_0]|=group_1
          del traingroup_city_dict[group_num_1]
          
city_both_conn_num=['1']*N
ched_city=set()
for ch_city in list(city_road_train):
  if not ch_city in ched_city:
    road_group_num=city_roadgroup_dict[ch_city]
    train_group_num=city_traingroup_dict[ch_city]
    intersect_group=roadgroup_city_dict[road_group_num] & traingroup_city_dict[train_group_num]
    ched_city|=intersect_group
    
    conn_size=str(len(intersect_group))
    for conn_city in list(intersect_group):
      city_both_conn_num[conn_city-1]=conn_size


print(' '.join(city_both_conn_num))

Solution (Python):
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1]*(n+1)
    self.rank = [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.rank[x] > self.rank[y]:
        self.root[x] += self.root[y]
        self.root[y] = x
    else:
        self.root[y] += self.root[x]
        self.root[x] = y
        if self.rank[x] == self.rank[y]:
          self.rank[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)]

n,k,l=map(int,input().split())
douro=UnionFind(n)
tetudou=UnionFind(n)
for i in range(k):
  p,q=map(int,input().split())
  douro.Unite(p-1, q-1)
for i in range(l):
  r,s=map(int,input().split())
  tetudou.Unite(r-1, s-1)

d={}
for i in range(n):
  pair=(douro.Find_Root(i), tetudou.Find_Root(i))
  if pair in d:
    d[pair] += 1
  else:
    d[pair] = 1

print(' '.join([str(d[(douro.Find_Root(i), tetudou.Find_Root(i))]) for i in range(n)]))

Solution (Python):
def root(x,par):
    if x == par[x]:
        return x
    else:
        par[x] = root(par[x],par)
        return par[x]
 
def unite(x,y,par):
    x = root(x,par)
    y = root(y,par)
    if x==y:
        if x==0 and y==1:
            return
    else:
        par[x]=y

n,k,l = map(int,input().split())
road =[i for i in range(n)]
train = [i for i in range(n)]
ans =0
for _ in range(k):
    p,q = map(int,input().split())
    unite(p-1,q-1,road)
for _ in range(l):
    p,q = map(int,input().split())
    unite(p-1,q-1,train)

for i in range(n):
    root(i,train)
for i in range(n):
    root(i,road)

dual = [(i,j) for i,j in zip(road,train)]
ans ={}
for i in dual:
    if i in ans:
        ans[i] +=1
    else:
        ans[i] =1
for i in dual:
    print(ans[i],end=" ")

Solution (Python):
from collections import deque
from sys import stdin

def create_links(n, k):
  links = [[] for _ in range(n)]
  for i in range(k):
    p, q = map(int, stdin.readline().split())
    links[p - 1].append(q - 1)
    links[q - 1].append(p - 1)
  return links

def create_groups(n, links):
  groups = list(range(n))
  for i in range(n):
    if groups[i] != i:
      continue
    d = deque()
    d.append(i)
    while len(d) != 0:
      j = d.popleft()
      for k in links[j]:
        if groups[k] != i:
          groups[k] = i
          d.append(k)
  return groups

n, k, l = map(int, input().split())
road_links = create_links(n, k)
rail_links = create_links(n, l)
road_groups = create_groups(n, road_links)
rail_groups = create_groups(n, rail_links)

d = {}
for i in range(n):
  t = (road_groups[i], rail_groups[i])
  if t in d:
    d[t] += 1
  else:
    d[t] = 1

print(*[d[(road_groups[i], rail_groups[i])] for i in range(n)])

Solution (Python):
from sys import stdin

def create_links(n, k):
  links = [[] for _ in range(n)]
  for i in range(k):
    p, q = map(int, stdin.readline().split())
    links[p - 1].append(q - 1)
    links[q - 1].append(p - 1)
  return links

def create_groups(n, links):
  groups = list(range(n))
  for i in range(n):
    if groups[i] != i:
      continue
    q = [i]
    while q:
      j = q.pop()
      for k in links[j]:
        if groups[k] != i:
          groups[k] = i
          q.append(k)
  return groups

n, k, l = map(int, input().split())
road_links = create_links(n, k)
rail_links = create_links(n, l)
road_groups = create_groups(n, road_links)
rail_groups = create_groups(n, rail_links)

d = {}
for i in range(n):
  t = (road_groups[i], rail_groups[i])
  if t in d:
    d[t] += 1
  else:
    d[t] = 1

print(*[d[(road_groups[i], rail_groups[i])] for i in range(n)])

Solution (Python):
from sys import stdin

def main():
  def find(parent, i):
    t = parent[i]
    if t == -1:
      return i
    t = find(parent, t)
    parent[i] = t
    return t

  def unite(parent, i, j):
    i = find(parent, i)
    j = find(parent, j)
    if i == j:
      return
    parent[i] = j

  from builtins import int, map, range
  readline = stdin.readline

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

  roads = [-1] * n
  rails = [-1] * n

  for i in range(k):
    p, q = map(int, readline().split())
    unite(roads, p - 1, q - 1)

  for i in range(l):
    p, q = map(int, readline().split())
    unite(rails, p - 1, q - 1)

  d = {}
  for i in range(n):
    t = (find(roads, i), find(rails, i))
    if t in d:
      d[t] += 1
    else:
      d[t] = 1

  print(*[d[(find(roads, i), find(rails, i))] for i in range(n)])

main()

Solution (Python):
from sys import stdin

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

def unite(parent, i, j):
  i = find(parent, i)
  j = find(parent, j)
  if i == j:
    return
  parent[i] = j

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

roads = list(range(n))
rails = list(range(n))

for i in range(k):
  p, q = map(int, stdin.readline().split())
  unite(roads, p - 1, q - 1)

for i in range(l):
  p, q = map(int, stdin.readline().split())
  unite(rails, p - 1, q - 1)

d = {}
for i in range(n):
  t = (find(roads, i), find(rails, i))
  if t in d:
    d[t] += 1
  else:
    d[t] = 1

print(*[d[(find(roads, i), find(rails, i))] for i in range(n)])

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

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, rank):
  x = Find(x, par)
  y = Find(y, par)
  
  if x != y:
    
    if rank[x] < rank[y]:
      par[y] += par[x]
      par[x] = y
    else:
      par[x] += par[y]
      par[y] = x
      if rank[x] == rank[y]:
        rank[x] += 1
    
def Same(x, y, par):
  return Find(x, par) == Find(y, par)
 
def Size(x, par):
  return -par[Find(x)]

n, k, l = map(int, input().split())
rpar = [-1]* n
tpar = [-1]* n
rrank = [0]*n
trank = [0]*n

for i in range(k):
  p, q = map(int, input().split())
  p, q =p-1, q-1
  Unite(p,q, rpar, rrank) 

for i_ in range(l):
  p, q = map(int, input().split())
  p, q =p-1, q-1
  Unite(p,q, tpar, trank)

d = {}
IDs = [0]*n
for j in range(n):
  ID = Find(j, rpar)+(Find(j, tpar)+1)*10**8
  IDs[j] = ID
  if ID in d:
    d[ID] += 1
  else:
    d[ID] = 1

for j_ in range(n):
  print(d[IDs[j_]])

Solution (Python):
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, rank):
  x = Find(x, par)
  y = Find(y, par)
  
  if x != y:
    
    if rank[x] < rank[y]:
      par[y] += par[x]
      par[x] = y
    else:
      par[x] += par[y]
      par[y] = x
      if rank[x] == rank[y]:
        rank[x] += 1
    
def Same(x, y, par):
  return Find(x, par) == Find(y, par)
 
def Size(x, par):
  return -par[Find(x)]

n, k, l = map(int, input().split())
rpar = [-1]* n
tpar = [-1]* n
rrank = [0]*n
trank = [0]*n

for i in range(k):
  p, q = map(int, input().split())
  p, q =p-1, q-1
  Unite(p,q, rpar, rrank) 

for i_ in range(l):
  p, q = map(int, input().split())
  p, q =p-1, q-1
  Unite(p,q, tpar, trank)

d = {}
IDs = [0]*n
for j in range(n):
  ID = Find(j, rpar)+(Find(j, tpar)+1)*10**8
  IDs[j] = ID
  if ID in d:
    d[ID] += 1
  else:
    d[ID] = 1

for j_ in range(n):
  print(d[IDs[j_]])

Solution (Python):
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, rank):
  x = Find(x, par)
  y = Find(y, par)
  
  if x != y:
    
    if rank[x] < rank[y]:
      par[y] += par[x]
      par[x] = y
    else:
      par[x] += par[y]
      par[y] = x
      if rank[x] == rank[y]:
        rank[x] += 1
    
def Same(x, y, par):
  return Find(x, par) == Find(y, par)
 
def Size(x, par):
  return -par[Find(x)]

n, k, l = map(int, input().split())
rpar = [-1]* n
tpar = [-1]* n
rrank = [0]*n
trank = [0]*n

for i in range(k):
  p, q = map(int, input().split())
  p, q =p-1, q-1
  Unite(p,q, rpar, rrank) 

for i_ in range(l):
  p, q = map(int, input().split())
  p, q =p-1, q-1
  Unite(p,q, tpar, trank)

d = {}
IDs = [0]*n
for j in range(n):
  ID = Find(j, rpar)+(Find(j, tpar)+1)*10**8
  IDs[j] = ID
  if ID in d:
    d[ID] += 1
  else:
    d[ID] = 1

for j_ in range(n):
  print(d[IDs[j_]])

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

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, rank):
  x = Find(x, par)
  y = Find(y, par)
  
  if x != y:
    
    if rank[x] < rank[y]:
      par[y] += par[x]
      par[x] = y
    else:
      par[x] += par[y]
      par[y] = x
      if rank[x] == rank[y]:
        rank[x] += 1
    
def Same(x, y, par):
  return Find(x, par) == Find(y, par)
 
def Size(x, par):
  return -par[Find(x)]

n, k, l = map(int, input().split())
rpar = [-1]* n
tpar = [-1]* n
rrank = [0]*n
trank = [0]*n

for i in range(k):
  p, q = map(int, input().split())
  p, q =p-1, q-1
  Unite(p,q, rpar, rrank) 

for i_ in range(l):
  p, q = map(int, input().split())
  p, q =p-1, q-1
  Unite(p,q, tpar, trank)

d = {}
IDs = [0]*n
for j in range(n):
  ID = Find(j, rpar)+(Find(j, tpar)+1)*10**8
  IDs[j] = ID
  if ID in d:
    d[ID] += 1
  else:
    d[ID] = 1

ans = ''
for j_ in range(n):
  if j_ != 0:
    ans += ' '
  ans += str(d[IDs[j_]])
print(ans)

Solution (Python):
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, rank):
  x = Find(x, par)
  y = Find(y, par)
  
  if x != y:
    
    if rank[x] < rank[y]:
      par[y] += par[x]
      par[x] = y
    else:
      par[x] += par[y]
      par[y] = x
      if rank[x] == rank[y]:
        rank[x] += 1
    
def Same(x, y, par):
  return Find(x, par) == Find(y, par)
 
def Size(x, par):
  return -par[Find(x)]

n, k, l = map(int, input().split())
rpar = [-1]* n
tpar = [-1]* n
rrank = [0]*n
trank = [0]*n

for i in range(k):
  p, q = map(int, input().split())
  p, q =p-1, q-1
  Unite(p,q, rpar, rrank) 

for i_ in range(l):
  p, q = map(int, input().split())
  p, q =p-1, q-1
  Unite(p,q, tpar, trank)

d = {}
IDs = [0]*n
for j in range(n):
  ID = Find(j, rpar)+(Find(j, tpar)+1)*10**8
  IDs[j] = ID
  if ID in d:
    d[ID] += 1
  else:
    d[ID] = 1

ans = ''
for j_ in range(n):
  if j_ != 0:
    ans += ' '
  ans += str(d[IDs[j_]])
print(ans)

Solution (Python):
import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7




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

table1 = [-1] * n
table2 = [-1] * n
def find(x, table):
    if table[x] < 0:
        return x
    table[x] = find(table[x], table)
    return table[x]


def union(x, y, table):
    r1 = find(x, table)
    r2 = find(y, table)
    if r1 == r2:
        return
    d1 = table[r1]
    d2 = table[r2]
    if d1 <= d2:
        table[r2] = r1
        if d1 == d2:
            table[r1] -= 1
    else:
        table[r1] = r2



for i in range(k):
    u, v = map(int, input().split())
    union(u - 1, v - 1, table1)


for i in range(l):
    u, v = map(int, input().split())
    union(u - 1, v - 1, table2)


f = defaultdict(int)
for i in range(n):
    f[(find(i, table1), find(i, table2))] += 1



print(*[f[(find(j, table1), find(j, table2))] for j in range(n)])

Solution (Python):
N, K, L = map(int, input().split())
E = [[] for i in range(N)]
for i in range(K):
  p, q = map(int, input().split())
  E[p-1].append(q-1)
  E[q-1].append(p-1)
F = [[] for i in range(N)]
for i in range(L):
  r, s = map(int, input().split())
  F[r-1].append(s-1)
  F[s-1].append(r-1)
C = list(range(N))
for n in range(N):
  if C[n] != n:
    continue
  q = [n]
  while q:
    c = q.pop()
    ds = E[c]
    for d in ds:
      if C[d] != n:
        C[d] = n
        q.append(d)
D = list(range(N))
for n in range(N):
  if D[n] != n:
    continue
  q = [n]
  while q:
    c = q.pop()
    ds = F[c]
    for d in ds:
      if D[d] != n:
        D[d] = n
        q.append(d)


Nums = {}
for i in range(N):
  c, d = C[i], D[i]
  if (c, d) in Nums:
    Nums[(c, d)] += 1
  else:
    Nums[(c, d)] = 1
rs = []
for i in range(N):
  c, d = C[i], D[i]
  r = Nums[(c, d)]
  rs.append(r)
print(" ".join(map(str, rs)))

Solution (Python):
from collections import defaultdict
def build_tree(N, edges):
    root_list = [i for i in range(N)]
    for p, q in edges:
        p -= 1
        q -= 1
        root_p = get_root(root_list, p)
        root_q = get_root(root_list, q)
        root_now = min(root_p, root_q, p)
        root_list[p] = root_now
        root_list[q] = root_now
        root_list[root_p] = root_now
        root_list[root_q] = root_now
    return root_list

def get_root(root_list, city):
    if root_list[city] == city:
        return city
    else: 
        root_list[city] = get_root(root_list, root_list[city])
        return root_list[city]

if __name__ == '__main__':
    N, K, L = map(int, input().split())
    roads = [None]*K
    rails = [None]*L
    for k in range(K):
        roads[k] = list(map(int, input().split()))
    for l in range(L):
        rails[l] = list(map(int, input().split()))
    
    
    '''N = 2*10**5
    L = int(N/2)
    K = int(N/2)
    roads = [None]*K
    rails = [None]*L
    for i in range(L):
        roads[i] = [2*i, 2*i+1]
    for i in range(K):
        rails[i] = [2*i, 2*i+1]'''
    
    road_roots = build_tree(N, roads)
    rail_roots = build_tree(N, rails)
    
    railroads = defaultdict(int)
    RR = []
    for n in range(N):
        rr = (get_root(road_roots, n), get_root(rail_roots, n))
        RR.append(rr)
        railroads[rr] += 1
    answer = [railroads[key] for key in RR]
    print(' '.join(map(str, answer)))

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(' '.join((str(c[x(i),y(i)])for i in r(n))))

Solution (Python):
from collections import*;M=lambda:map(int,input().split());n,k,l=M();d=[-1]*n;t=[-1]*n;r=range
def f(l,x):
  if l[x]<0:return x
  l[x]=f(l,l[x]);return l[x]
def u(l,x,y):
  if f(l,x)!=f(l,y):l[f(l,y)]=f(l,x)
for i in r(k+l):a,b=M();u(d if i<k else t,a-1,b-1)
p=[(f(d,i),f(t,i))for i in r(n)];c=Counter(p);print(*[c[p[i]]for i in r(n)])

Solution (Python):
from collections import*;M=lambda:map(int,input().split());n,k,l=M();d=[-1]*n;t=[-1]*n;r=range
def f(l,x):
  if l[x]<0:return x
  else:l[x]=f(l,l[x]);return l[x]
def u(l,x,y):
  if f(l,x)!=f(l,y):l[f(l,y)]=f(l,x)
for i in r(k+l):a,b=M();u(d if i<k else t,a-1,b-1)
p=[(f(d,i),f(t,i))for i in r(n)];c=Counter(p);print(*[c[p[i]]for i in r(n)])

Solution (Python):
from collections import*;M=lambda:map(int,input().split());n,k,l=M();d=[-1]*n;t=[-1]*n;r=range
def f(l,x):
  if l[x]<0:return x
  else:l[x]=f(l,l[x]);return l[x]
def u(l,x,y):
  if f(l,x)!=f(l,y):l[f(l,y)]=f(l,x)
for i in r(k+l):a,b=M();u(d if i<k else t,a-1,b-1)
p=[(f(d,i),f(t,i))for i in r(n)];c=Counter(p);print(*[c[p[i]]for i in r(n)])

Solution (Python):
from collections import*;M=lambda:map(int,input().split());n,k,l=M();d=[-1]*n;t=[-1]*n;r=range(n)
def f(l,x):
  if l[x]<0:return x
  else:l[x]=f(l,l[x]);return l[x]
def u(l,x,y):
  if f(l,x)!=f(l,y):l[f(l,y)]=f(l,x)
for i in range(k+l):a,b=M();u(d if i<k else t,a-1,b-1)
p=[(f(d,i),f(t,i))for i in r];c=Counter(p);print(*[c[p[i]]for i in r])

Solution (Python):
from collections import*;M=lambda:map(int,input().split());n,k,l=M();d=[-1]*n;t=[-1]*n;r=range(n)
def f(l,x):
  if l[x]<0:return x
  else:l[x]=f(l,l[x]);return l[x]
def u(l,x,y):
  if f(l,x)!=f(l,y):l[f(l,y)]=f(l,x)
for _ in[0]*k:a,b=M();u(d,a-1,b-1)
for _ in[0]*l:a,b=M();u(t,a-1,b-1)
p=[(f(d,i),f(t,i))for i in r];c=Counter(p);print(*[c[p[i]]for i in r])

Solution (Python):
from collections import*
n,k,l=map(int,input().split());d=[-1]*n;t=[-1]*n;M=lambda:map(int,input().split());r=range
def f(l,x):
  if l[x]<0:return x
  else:l[x]=f(l,l[x]);return l[x]
def u(l,x,y):
  if f(l,x)!=f(l,y):l[f(l,y)]=f(l,x)
for _ in r(k):a,b=M();u(d,a-1,b-1)
for _ in r(l):a,b=M();u(t,a-1,b-1)
p=[(f(d,i),f(t,i))for i in r(n)];c=Counter(p);print(*[c[p[i]]for i in r(n)])

Solution (Python):
import collections
n,k,l=map(int,input().split());d=[-1]*n;t=[-1]*n
def f(l,x):
  if l[x]<0:return x
  else:l[x]=f(l,l[x]);return l[x]
def u(l,x,y):
  if f(l,x)!=f(l,y):l[f(l,y)]=f(l,x)
for _ in range(k):a,b=map(int,input().split());u(d,a-1,b-1)
for _ in range(l):a,b=map(int,input().split());u(t,a-1,b-1)
p=[(f(d,i),f(t,i))for i in range(n)];c=collections.Counter(p);print(*[c[p[i]]for i in range(n)])

Solution (Python):
from collections import*
n,k,l=map(int,input().split());d=[-1]*n;t=[-1]*n
def f(l,x):
  if l[x]<0:return x
  else:l[x]=f(l,l[x]);return l[x]
def u(l,x,y):
  if f(l,x)!=f(l,y):l[f(l,y)]=f(l,x)
for _ in range(k):a,b=map(int,input().split());u(d,a-1,b-1)
for _ in range(l):a,b=map(int,input().split());u(t,a-1,b-1)
p=[(f(d,i),f(t,i))for i in range(n)];c=Counter(p);print(*[c[p[i]]for i in range(n)])

Solution (Python):
from collections import*
n,k,l=map(int,input().split());d=[-1]*n;t=[-1]*n
def f(l,x):
  if l[x]<0:return x
  else:l[x]=f(l,l[x]);return l[x]
def u(l,x,y):
  x,y=f(l,x),f(l,y)
  if x!=y:l[y]=x
for _ in range(k):a,b=map(int,input().split());u(d,a-1,b-1)
for _ in range(l):a,b=map(int,input().split());u(t,a-1,b-1)
p=[(f(d,i),f(t,i))for i in range(n)];c=Counter(p);print(*[c[p[i]]for i in range(n)])

Solution (Python):
from collections import*
class u():
  def __init__(self,n):self.n,self.r=[-1]*n,[0]*n
  def f(self,x):
    if self.n[x]<0:return x
    else:self.n[x]=self.f(self.n[x]);return self.n[x]
  def u(self,x,y):
    x,y=self.f(x),self.f(y)
    if x==y:return
    elif self.r[x]>self.r[y]:self.n[x]+=self.n[y];self.n[y]=x
    else:self.n[y]+=self.n[x];self.n[x]=y;self.r[y]+=self.r[x]==self.r[y]
n,k,l=map(int,input().split());d=u(n);t=u(n)
for _ in range(k):a,b=map(int,input().split());d.u(a-1,b-1)
for _ in range(l):a,b=map(int,input().split());t.u(a-1,b-1)
p=[(d.f(i),t.f(i))for i in range(n)];c=Counter(p);print(*[c[p[i]]for i in range(n)])

Solution (Python):
from collections import*
class u():
  def __init__(self,n):self.n,self.r=[-1]*n,[0]*n
  def f(self,x):
    if self.n[x]<0:return x
    else:self.n[x]=self.f(self.n[x]);return self.n[x]
  def u(self,x,y):
    x,y=self.f(x),self.f(y)
    if x==y:return
    elif self.r[x]>self.r[y]:self.n[x]+=self.n[y];self.n[y]=x
    else:self.n[y]+=self.n[x];self.n[x]=y;self.r[y]+=self.r[x]==self.r[y]
  def s(self,x,y):return self.f(x)==self.f(y)
  def c(self,x):return -self.n[self.f(x)]
n,k,l=map(int,input().split())
d=u(n);t=u(n)
for _ in range(k):a,b=map(int,input().split());d.u(a-1,b-1)
for _ in range(l):a,b=map(int,input().split());t.u(a-1,b-1)
p=[(d.f(i),t.f(i))for i in range(n)]
c=Counter(p)
print(*[c[p[i]]for i in range(n)])

Solution (Python):
from collections import Counter


class UnionFind():

    
    def __init__(self, n):
        self.n = n
        self.root = [-1] * n

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

    def Unite(self, x, y):
        x = self.FindRoot(x)
        y = self.FindRoot(y)

        if x == y:
            return False
        if self.Size(x) < self.Size(y):
            x, y = y, x
        self.root[x] += self.root[y]
        self.root[y] = x

        return True

    def isSameGroup(self, x, y):
        return self.FindRoot(x) == self.FindRoot(y)

    def Size(self, x):
        return -self.root[self.FindRoot(x)]

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

Uni1 = UnionFind(N)

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

Uni2 = UnionFind(N)

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

pair = []
for i in range(N):
    pair.append((Uni1.FindRoot(i), Uni2.FindRoot(i)))

c = Counter(pair)
cnt = []
for i in range(N):
    cnt.append(c[pair[i]])

print(*cnt)

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    a = ["a", "i", "u", "e", "o"]
    c = S()
    if c[0] in a:
        print("vowel")
    else:
        print("consonant")
    return


def B():
    _ = II()
    t = LI()
    tsum = sum(t)
    for _ in range(II()):
        p, x = LI()
        print(tsum - t[p - 1] + x)
    return


def C():
    s = input()
    lens = len(s)
    check = ["dream", "dreamer", "erase", "eraser"]
    q = deque()
    q.append(0)
    while q:
        p = q.pop()
        if p == lens:
            print("YES")
            return
        for i in check:
            if s[p:p + len(i)] == i:
                q.appendleft(p + len(i))
    print("NO")
    return


def D():
    class UnionFind():

        def __init__(self, n):
            self.par = [i for i in range(n)]
            self.size = [1] * n
        
        def find(self, a):
            if a == self.par[a]:
                return a
            x = self.find(self.par[a])
            self.par[a] = x
            return x

        def unite(self, a, b):
            a = self.find(a)
            b = self.find(b)
            if a == b: return
            if a > b: a, b = b, a
            self.par[b] = a
            self.size[a] += self.size[b]

    n, k, l = LI()
    rail = UnionFind(n)
    road = UnionFind(n)

    for _ in range(k):
        p, q = LI_()
        rail.unite(p, q)
    for _ in range(l):
        r,s = LI_()
        road.unite(r, s)
    d = defaultdict(int)
    for i in range(n):
        d[(rail.find(i), road.find(i))] += 1
    for i in range(n):
        print(d[(rail.find(i), road.find(i))], end=" ")
    print()
    return


if __name__ == '__main__':
    D()

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 isSameGroup(self, x, y):
        return self.Find_root(x) == self.Find_root(y)
    
    def Count(self, x):
        return - self.root[self.Find_root(x)]

import collections    
    
n, k, l = map(int, input().split())
union = UnionFind(n)
union1 = UnionFind(n)

for _ in range(k):
    p, q = map(int, input().split())
    union.Unite(p, q)
for _ in range(l):
    p, q = map(int, input().split())
    union1.Unite(p, q)

parents = [(union.Find_root(i), union1.Find_root(i)) for i in range(1, n + 1)]
lc = collections.Counter(parents)
ans = []
for i in range(n):
    ans.append(lc[parents[i]])
print(*ans)

Solution (Python):
import collections

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n+1))
        self.rank = [0]*(n+1)

    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 self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


N, K, L = map(int, input().split())
uf1 = UnionFind(N)
for _ in range(K):
    x, y = map(int, input().split())
    uf1.unite(x, y)

uf2 = UnionFind(N)
for _ in range(L):
    x, y = map(int, input().split())
    uf2.unite(x, y)

parents = [(uf1.find(i), uf2.find(i)) for i in range(1, N+1)]
lc = collections.Counter(parents)
ans = []
for i in range(N):
    ans.append(lc[parents[i]])
print(*ans)