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

def unite(node_a, node_b):
    root_a = node_a.root()
    root_b = node_b.root()
    if root_a == root_b:
        return False
    if root_b.depth > root_a.depth:
        root_a, root_b = root_b, root_a
    root_b.is_root = False
    root_b.parent = root_a
    root_a.depth = max(root_a.depth, root_b.depth+1)
    return True

class Node:
    def __init__(self, id):
        self.id = id
        self.is_root = True
        self.parent = None
        self.depth = 1
    
    def root(self):
        if self.is_root:
            return self
        elif self.parent.is_root:
            return self.parent
        else:
            self.parent = self.parent.root()
            return self.parent

def main():
    N, K, L = map(int, input().split())
    
    trains = [Node(i) for i in range(N)]
    streets = [Node(i) for i in range(N)]

    for i in range(K):
        p, q = map(int, input().split())
        p -= 1; q -= 1
        unite(trains[p], trains[q])
    for i in range(L):
        r, s = map(int, input().split())
        r -= 1; s -= 1
        unite(streets[r], streets[s])
    dic = {}
    roots = []
    for i in range(N):
        tmp = (trains[i].root().id, streets[i].root().id)
        roots.append(tmp)
        if tmp in dic:
            dic[tmp] += 1
        else:
            dic[tmp] = 1
    
    for i in range(N-1):
        print(dic[roots[i]], end=" ")
    print(dic[roots[N-1]])

if __name__ == "__main__":
    main()

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[y] = x
        else:
            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)]

def main():
  N, K, L = map(int, input().split())
  U_road = UnionFind(N)
  U_train = UnionFind(N)
  for _ in range(K):
    p, q = map(int, input().split())
    U_road.Unite(p, q)
  for _ in range(L):
    r, s = map(int, input().split())
    U_train.Unite(r, s)
  connect_dict = {}
  for i in range(1, N+1):
    x, y = U_road.Find_Root(i), U_train.Find_Root(i)
    if (x, y) in connect_dict:
      connect_dict[(x, y)] += 1
    else:
      connect_dict[(x, y)] = 1
  ans = []
  for i in range(1, N+1):
    x, y = U_road.Find_Root(i), U_train.Find_Root(i)
    ans.append(connect_dict[(x, y)])
  ans = list(map(str, ans))
  print(' '.join(ans))

  

if __name__ == "__main__":
  main()

Solution (Python):
import sys
from collections import Counter, deque, defaultdict
from math import factorial
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10*5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

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

n, k, l = MAP()
road = [0]*k
train = [0]*l
for i in range(k):
    p, q = MAP()
    road[i] = (p,q)
for i in range(l):
    r, s = MAP()
    train[i] = (r,s)

ans = [0]*n

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

for i in range(k):
    uf_road.Unite(road[i][0]-1, road[i][1]-1)
for i in range(l):
    uf_train.Unite(train[i][0]-1, train[i][1]-1)

roots = [(0,0)]*n
for i in range(n):
    a = uf_road.Find_Root(i)
    b = uf_train.Find_Root(i)
    roots[i] = (a, b)

c = Counter(roots)
for i in range(n):
    ans[i] = c[roots[i]]

for i in range(n):
    print(str(ans[i]) + " ", end = "")

Solution (Python):


from collections import Counter


class UnionFind:
    def __init__(self, n):
        self.ranks = [[0] * n, [0] * n]
        self.pars = [[i for i in range(n)], [i for i in range(n)]]
        self.n = n

    def find_set(self, node, idx):
        if self.pars[idx][node] == node:
            return node
        else:
            self.pars[idx][node] = self.find_set(self.pars[idx][node], idx)
            return self.pars[idx][node]

    def same_set(self, x, y, idx):
        return self.find_set(x, idx) == self.find_set(y, idx)

    def unite(self, x, y, idx):
        x = self.find_set(x, idx)
        y = self.find_set(y, idx)
        if x == y:
            return
        if self.ranks[idx][x] > self.ranks[idx][y]:
            self.pars[idx][y] = x
        else:
            self.pars[idx][x] = y
            if self.ranks[idx][x] == self.ranks[idx][y]:
                self.ranks[idx][y] += 1


def main():
    n, k, l = map(int, input().split())
    uf = UnionFind(n)
    road = 0
    train = 1

    for i in range(k):
        p, q = map(int, input().split())
        uf.unite(p-1, q-1, road)

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

    roots = [(uf.find_set(i, road), uf.find_set(i, train)) for i in range(n)]
    c = Counter(roots)
    ans = []
    for root in roots:
        ans.append(c[root])

    print(*ans)


if __name__ == "__main__":
    main()

Solution (Python):
n, k, l = map(int,input().split())
P = [list(map(int,input().split())) for i in range(k)]
R = [list(map(int,input().split())) for i in range(l)]

PM = [[] for i in range(n+1)]
RM = [[] for i in range(n+1)]

for i in range(k):
    PM[P[i][0]].append(P[i][1])
    PM[P[i][1]].append(P[i][0])
for i in range(l):
    RM[R[i][0]].append(R[i][1])
    RM[R[i][1]].append(R[i][0])

C = [[0] * 2 for i in range(n+1)]

VP = [0] * (n+1)
clr = 0
for i in range(1, n+1):
    if VP[i] == 0:
        VP[i] = 1
        clr += 1
        Q = [i]
        st = 0
        while st < len(Q):
            j = Q[st]
            C[j][0] = clr
            for item in PM[j]:
                if VP[item] == 0:
                    VP[item] = 1
                    Q.append(item)
            st += 1

VR = [0] * (n+1)
clr = 0
for i in range(1, n+1):
    if VR[i] == 0:
        VR[i] = 1
        clr += 1
        Q = [i]
        st = 0
        while st < len(Q):
            j = Q[st]
            C[j][1] = clr
            for item in RM[j]:
                if VR[item] == 0:
                    VR[item] = 1
                    Q.append(item)
            st += 1



D = {}
for i in range(1, n+1):
    try:
        D[(C[i][0], C[i][1])] += 1
    except:
        D[(C[i][0], C[i][1])] = 1

ANS = []

for i in range(1, n+1):
    ANS.append(str(D[(C[i][0], C[i][1])]))

print(" ".join(ANS))

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

N, K, L = map(int, input().split())
roads = UnionFind(N)
for _ in range(K):
  x, y = map(int, input().split())
  roads.unite(x, y)
rails = UnionFind(N)
for _ in range(L):
  x, y = map(int, input().split())
  rails.unite(x, y)
r_dict = {}
for i in range(1, N+1):
  x, y = roads.find(i), rails.find(i)
  if (x, y) in r_dict:
    r_dict[(x, y)] += 1
  else:
    r_dict[(x, y)] = 1
ans = []
for i in range(1, N+1):
  x, y = roads.find(i), rails.find(i)
  ans.append(r_dict[(x, y)])
print(' '.join(map(str, ans)))

Solution (Python):
from collections import deque
N, K, L = map(int, input().split())
roads = [[] for _ in range(N)]
rails = [[] for _ in range(N)]
group = [[-1, -1, i] for i in range(N)]
for i in range(K):
    p, q = map(int, input().split())
    roads[p-1].append(q-1)
    roads[q-1].append(p-1)
for i in range(L):
    p, q = map(int, input().split())
    rails[p-1].append(q-1)
    rails[q-1].append(p-1)
def BFS(v0, List, i):
    que = deque([v0])
    while que:
        v = que.pop()
        group[v][i] = v0
        for e in List[v]:
            if group[e][i]<0:
                que.append(e)
for v in range(N):
    if group[v][0]<0:
        BFS(v, roads, 0)
    if group[v][1]<0:
        BFS(v, rails, 1)
group.sort()
ans = [0]*N
cnt = 1
start = 0
for i in range(N-1):
    if group[i][:2] == group[i+1][:2]:
        cnt+=1
    else:
        for j in range(start, i+1):
            c = group[j][2]
            ans[c] = cnt
        cnt = 1
        start = i+1
for j in range(start, N):
    c = group[j][2]
    ans[c] = cnt
print(*ans)

Solution (Python):

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




class Union_Find():
	def __init__(self, n):
		self.union = [i for i in range(n)]
		self.level = [0 for i in range(n)]

	def root(self, i, mode=0):
		keiro = [i]
		ans = i
		while ans != self.union[ans]:
			ans = self.union[ans]
			keiro.append(ans)
		if mode == 0:
			return ans
		else:
			return ans, keiro

	def unite(self, i, j):
		root_i, list_i = self.root(i, 1)
		root_j, list_j = self.root(j, 1)
		if root_i != root_j:
			if self.level[root_i] < self.level[root_j]:
				self.level[root_j] = max(self.level[root_i] + 1, self.level[root_j])
				for node in list_i:
					self.union[node] = root_j
			else:
				self.level[root_i] = max(self.level[root_j] + 1, self.level[root_i])
				for node in list_j:
					self.union[node] = root_i

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

UF_road = Union_Find(N)
UF_train = Union_Find(N)
for i in range(K):
	p, q = list(map(int, input().split()))
	p -= 1
	q -= 1
	UF_road.unite(p,q)
for i in range(L):
	p, q = list(map(int, input().split()))
	p -= 1
	q -= 1
	UF_train.unite(p,q)

group = []
for i in range(N):
	group.append([UF_road.root(i), UF_train.root(i), i])
group.append([100000000,0,0])
group.sort()
X = group[0][0:2]
town = [group[0][2]]
number = [-1 for i in range(N)]
for i in range(1, N + 1):
	if X != group[i][0:2]:
		num = len(town)
		for j in town:
			number[j] = num
		town = [group[i][2]]
	else:
		town.append(group[i][2])
	X = group[i][0:2]


def list_print(A):
	length = len(A)
	for i in range(length - 1):
		print(A[i], end="")
		print(" ", end="")
	print(A[N - 1])

list_print(number)

Solution (Python):

"""
Created on Wed Sep 11 11:26:39 2019
D - 連結 / Connectivity
実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 
400 点
@author: justwah
"""
import sys

input = sys.stdin.readline 

class UnionFind:
    def __init__(self, n):
        self.rank = [0]*n
        self.parent = [-1]*n
        self.n = n
        
    def root(self, x):
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]
        
    def merge(self, a, b):
        a = self.root(a)
        b = self.root(b)
        if a == b:
            return
        if self.rank[a] < self.rank[b]:
            self.parent[a] = b
        else:
            self.parent[b] = a
            if self.rank[a] == self.rank[b]:
                self.rank[a] +=1
                
    def same(self, a, b):
        return self.root(a) == self.roob(b)


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

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

uf_rail = UnionFind(n)
for _ in range(l):
    r, s = map(int, input().split())
    uf_rail.merge(r-1, s-1)
    
d = {}
IDs = [0]*n
for i in range(n):
    ID = (uf_road.root(i), uf_rail.root(i))
    IDs[i] = ID
    if ID in d:
        d[ID] += 1
    else:
        d[ID] = 1

ans = []
for i in range(n):
    ans.append(d[IDs[i]])
print(*ans)

Solution (Python):

"""
Created on Wed Sep 11 11:26:39 2019
D - 連結 / Connectivity
実行時間制限: 2 sec / メモリ制限: 256 MB
 
配点 : 
400 点
@author: justwah
"""
from collections import Counter
import sys

input = sys.stdin.readline
 
class UnionFind:
    def __init__(self, N):
        self.rank = [0]*N
        self.parent = [i for i in range(N)]
        self.n = N
        
    def root(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]
        
    def merge(self, a, b):
        a = self.root(a)
        b = self.root(b)
        if a == b:
            return
        if self.rank[a] < self.rank[b]:
            self.parent[a] = b
        else:
            self.parent[b] = a
            if self.rank[a] == self.rank[b]:
                self.rank[a] +=1
                
    def same(self, a, b):
        return self.root(a) == self.roob(b)
 
 
n, k, l = map(int, input().split())
 
uf_road = UnionFind(n)
for _ in range(k):
    p, q = map(int, input().split())
    uf_road.merge(p-1, q-1)

uf_rail = UnionFind(n)
for _ in range(l):
    r, s = map(int, input().split())
    uf_rail.merge(r-1, s-1)
    
ctr = Counter()
for i in range(n):  
    r1 = uf_road.root(i)
    r2 = uf_rail.root(i)
    ctr[(r1,r2)] += 1

ans = []
for i in range(n): 
    r1 = uf_road.root(i)
    r2 = uf_rail.root(i)
    ans.append(ctr[(r1,r2)])

print(*ans)

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[x] = y
    else:
      par[y] = x
      if rank[x] == rank[y]:
        rank[x] += 1
    
def Same(x, y, par):
  return Find(x, par) == Find(y, par)
 
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):
    ans.append(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[x] = y
    else:
      par[y] = x
      if rank[x] == rank[y]:
        rank[x] += 1
    
def Same(x, y, par):
  return Find(x, par) == Find(y, par)
 
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[x] = y
    else:
      par[y] = x
      if rank[x] == rank[y]:
        rank[x] += 1
    
def Same(x, y, par):
  return Find(x, par) == Find(y, par)
 
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):
    ans.append(d[IDs[j]])
print(*ans)

Solution (Python):

"""
Created on Wed Sep 11 11:26:39 2019
D - 連結 / Connectivity
実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 
400 点
@author: justwah
"""
from collections import Counter

class UnionFind:
    def __init__(self, N):
        self.rank = [0]*N
        self.parent = [i for i in range(N)]
        self.n = N
        
    def root(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]
        
    def merge(self, a, b):
        a = self.root(a)
        b = self.root(b)
        if a == b:
            return
        if self.rank[a] < self.rank[b]:
            self.parent[a] = b
        else:
            self.parent[b] = a
            if self.rank[a] == self.rank[b]:
                self.rank[a] +=1
                
    def same(self, a, b):
        return self.root(a) == self.roob(b)


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

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

uf_rail = UnionFind(n)
for _ in range(l):
    r, s = map(int, input().split())
    uf_rail.merge(r-1, s-1)
    
ctr = Counter()
for i in range(n):  
    r1 = uf_road.root(i)
    r2 = uf_rail.root(i)
    ctr[(r1,r2)] += 1

ans = []
for i in range(n): 
    r1 = uf_road.root(i)
    r2 = uf_rail.root(i)
    ans.append(ctr[(r1,r2)])

print(*ans)

Solution (Python):
import sys
from collections import defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(10**8)

class UnionFind():
    def __init__(self, n):
        self.par = [-1 for i in range(n)]

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

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            if self.par[x] > self.par[y]: 
                x, y = y, x
            self.par[x] += self.par[y]
            self.par[y] = x

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

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

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

root_r = defaultdict(set)
root_t = defaultdict(set)
for i in range(n):
    root_r[uf_r.root(i)].add(i)
    root_t[uf_t.root(i)].add(i)

ans = []
memo = defaultdict(int)
for i in range(n):
    memo[(uf_r.root(i), uf_t.root(i))] += 1
for i in range(n):
    ans.append(memo[(uf_r.root(i), uf_t.root(i))])

print(*ans)

Solution (Python):
import sys
from collections import defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(10**8)

class UnionFind():
    def __init__(self, n):
        self.par = [-1 for i in range(n)]

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

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            if self.par[x] > self.par[y]: 
                x, y = y, x
            self.par[x] += self.par[y]
            self.par[y] = x

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

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

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

root_r = defaultdict(set)
root_t = defaultdict(set)
for i in range(n):
    root_r[uf_r.root(i)].add(i)
    root_t[uf_t.root(i)].add(i)

ans = []
memo = dict()
for i in range(n):
    if (uf_r.root(i), uf_t.root(i)) not in memo:
        memo[(uf_r.root(i), uf_t.root(i))] = len(root_r[uf_r.root(i)] & root_t[uf_t.root(i)])
    ans.append(memo[(uf_r.root(i), uf_t.root(i))])

print(*ans)

Solution (Python):
import sys
from collections import defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(10**8)

class UnionFind():
    def __init__(self, n):
        self.par = [-1 for i in range(n)]

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

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            if self.par[x] > self.par[y]: 
                x, y = y, x
            self.par[x] += self.par[y]
            self.par[y] = x

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

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

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

root_r = defaultdict(set)
root_t = defaultdict(set)
for i in range(n):
    root_r[uf_r.root(i)].add(i)
    root_t[uf_t.root(i)].add(i)

ans = []
memo = dict()
for i in range(n):
    if (uf_r.root(i), uf_t.root(i)) not in memo:
        memo[(uf_r.root(i), uf_t.root(i))] = len(root_r[uf_r.root(i)] & root_t[uf_t.root(i)])
    ans.append(str(memo[(uf_r.root(i), uf_t.root(i))]))

print(' '.join(ans))

Solution (Python):

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


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

        if (self.rank[x] < self.rank[y]):
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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



from collections import Counter

N,K,L = map(int,input().split())
roads = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(K)]
rails = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(L)]

uf_road = UnionFind(N)
for a,b in roads:
    uf_road.unite(a,b)

uf_rail = UnionFind(N)
for a,b in rails:
    uf_rail.unite(a,b)

ctr = Counter()
for i in range(N):
    r1 = uf_road.find(i)
    r2 = uf_rail.find(i)
    ctr[(r1,r2)] += 1

ans = []
for i in range(N):
    r1 = uf_road.find(i)
    r2 = uf_rail.find(i)
    ans.append(ctr[(r1,r2)])

print(*ans)

Solution (Python):
from collections import defaultdict as dd
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)]
N, K, L = map(int, input().split())
k = UnionFind(N)
l = UnionFind(N)
checkset = set()
res = [1] * (N + 1)
roots = dd(int)
for _ in range(K):
  x, y = map(int, input().split())
  k.Unite(x, y)
  checkset.add(x)
  checkset.add(y)
for _ in range(L):
  x, y = map(int, input().split())
  l.Unite(x, y)
  checkset.add(x)
  checkset.add(y)
for i in list(checkset):
  kr = k.Find_Root(i)
  lr = l.Find_Root(i)
  roots[(kr, lr)] += 1

for i in list(checkset):
  kr = k.Find_Root(i)
  lr = l.Find_Root(i)
  res[i] = roots[(kr, lr)]
  
print(*(res[1: ]))

Solution (Python):
def bfs(n):
    graph = [[] for i in range(N)]

    for i in range(n):
        v, u = map(int, input().split())
        graph[v-1].append(u-1)
        graph[u-1].append(v-1)
    
    root = [i for i in range(N)]
    visited = [False] * N
    
    for i in range(N):
        if not visited[i]:
            q = graph[i]
            visited[i] = True
            
            while q:
                v = q.pop()
                root[v] = i
                visited[v] = True
                for u in graph[v]:
                    if not visited[u]:
                        visited[u] = True
                        q.append(u)
                        root[u] = i
                        
    return root

def main():
    load_root = bfs(K)
    train_root = bfs(L)
    
    count = {}
    
    city = [(i, j) for i, j in zip(load_root, train_root)]
    
    for c in city:
        if c in count:
            count[c] += 1
        else:
            count[c] = 1
            
    for c in city:
        print(count[c], '', end='')

if __name__ == '__main__':
    N, K, L = map(int, input().split())
    main()

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


par=[-1 for i in range(n+1)]
def root(a):
    if par[a]<0:
        return a
    else:
        return root(par[a])
def f(a):
    if road[a]<0:
        return a
    else:
        return f(road[a])
def f2(a):
    if rail[a]<0:
        return a
    else:
        return f2(rail[a])
def size(a):
    return -par[root(a)]
def connect(a,b):
    a=root(a)
    b=root(b)
    if a==b:
        return False
    if size(a)<size(b):
        a,b=b,a
    par[a]+=par[b]
    par[b]=a
    return True

for i in range(k):
    a=[int(j) for j in input().split()]
    if root(a[0])!=root(a[1]):
        connect(a[0],a[1])
import copy
road=copy.deepcopy(par)

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

for i in range(l):
    r,s=[int(j) for j in input().split()]
    if root(r)!=root(s):
        connect(r,s)
import copy
rail=copy.deepcopy(par)
l=[(f(i),f2(i)) for i in range(1,1+n)]
from collections import Counter
c=Counter(l)
print(*(c[i] for i in l))

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


par=[-1 for i in range(n+1)]
def root(a):
    if par[a]<0:
        return a
    else:
        return root(par[a])
def f(a):
    if road[a]<0:
        return a
    else:
        return f(road[a])
def f2(a):
    if rail[a]<0:
        return a
    else:
        return f2(rail[a])
def size(a):
    return -par[root(a)]
def connect(a,b):
    a=root(a)
    b=root(b)
    if a==b:
        return False
    if size(a)<size(b):
        a,b=b,a
    par[a]+=par[b]
    par[b]=a
    return True

for i in range(k):
    a=[int(j) for j in input().split()]
    if root(a[0])!=root(a[1]):
        connect(a[0],a[1])
import copy
road=copy.deepcopy(par)

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

for i in range(l):
    r,s=[int(j) for j in input().split()]
    if root(r)!=root(s):
        connect(r,s)
import copy
rail=copy.deepcopy(par)
l=[(f(i),f2(i)) for i in range(1,1+n)]
from collections import Counter
c=Counter(l)
print(*(c[i] for i in l))

Solution (Python):
class UnionFind:
    def __init__(self, N):
        self.parent = [x for x in range(N+1)]
        self.rank = [1 for x in range(N+1)]

    def find(self, x):
        p = x
        while self.parent[p] != p:
            p = self.parent[p]
        self.parent[x] = p
        return p

    def union(self, r, l):
        x, y = self.find(r), self.find(l)
        if x == y:
            return
        rx, ry = self.rank[x], self.rank[y]
        if rx > ry:
            self.parent[y] = x
        elif rx == ry:
            self.parent[y] = x
            self.rank[x] += 1
        else:
            self.parent[x] = y

def main():
    N, K, L = map(int, input().split())
    
    rails = UnionFind(N)
    for _ in range(K):
        p, q = map(int, input().split())
        rails.union(p, q)

    loads = UnionFind(N)
    for _ in range(L):
        p, q = map(int, input().split())
        loads.union(p,q)
    RL = [(rails.find(u), loads.find(u)) for u in range(1, N+1)]
    from collections import Counter
    c = Counter(RL)

    print(*(c[x] for x in RL))

main()