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


class UnionFind(object):
    __slots__ = ["nodes"]

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

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

    def has_same_root(self, x, y) -> bool:
        return self.find(x) == self.find(y)
    
    def size(self, x) -> int:
        return -self.nodes[self.find(x)]

    def unite(self, x: int, y: int) -> None:
        if self.has_same_root(x, y):
            return

        root_x, root_y = self.find(x), self.find(y)
        if self.nodes[root_x] < self.nodes[root_y]:
            bigroot, smallroot = (root_x, root_y)
        else: 
            bigroot, smallroot = (root_y, root_x)
        self.nodes[bigroot] += self.nodes[smallroot]
        self.nodes[smallroot] = bigroot


def solve(N: int, K: int, L: int, p: "List[int]", q: "List[int]", r: "List[int]", s: "List[int]"):
    con_road = UnionFind(N)
    con_rail = UnionFind(N)
    for i in range(K):
        con_road.unite(p[i], q[i])
    for i in range(L):
        con_rail.unite(r[i], s[i])
    
    count = {}
    for i in range(N):
        key = (con_road.find(i), con_rail.find(i))
        count[key] = count.get(key, 0) + 1
    
    print(' '.join(str(count[(con_road.find(i), con_rail.find(i))]) for i in range(N)))
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    K = int(next(tokens))  
    L = int(next(tokens))  
    p = [int()] * (K)  
    q = [int()] * (K)  
    for i in range(K):
        p[i] = int(next(tokens))-1
        q[i] = int(next(tokens))-1
    r = [int()] * (L)  
    s = [int()] * (L)  
    for i in range(L):
        r[i] = int(next(tokens))-1
        s[i] = int(next(tokens))-1
    solve(N, K, L, p, q, r, s)

if __name__ == '__main__':
    main()

Solution (Python):
N,K,L=map(int,input().split())
Road_P=[i for i in range(N+1)]
Road_size=[1 for i in range(N+1)]

def find_road(a):
    if a==Road_P[a]:
        return a
    else:
        return find_road(Road_P[a])
        
def union_road(b,c):
    B=find_road(b)
    C=find_road(c)
    if Road_size[B]>=Road_size[C]:
        Road_P[C]=Road_P[B]
        Road_size[B]+=Road_size[C]
    else:
        Road_P[B]=Road_P[C]
        Road_size[C]+=Road_size[B]

for i in range(K):
    p,q=map(int,input().split())
    if find_road(p)!=find_road(q):
        union_road(p,q)


Rail_P=[i for i in range(N+1)]
Rail_size=[1 for i in range(N+1)]

def find_rail(a):
    if a==Rail_P[a]:
        return a
    else:
        return find_rail(Rail_P[a])
        
def union_rail(b,c):
    B=find_rail(b)
    C=find_rail(c)
    if Rail_size[B]>=Rail_size[C]:
        Rail_P[C]=Rail_P[B]
        Rail_size[B]+=Rail_size[C]
    else:
        Rail_P[B]=Rail_P[C]
        Rail_size[C]+=Rail_size[B]

for i in range(L):
    p,q=map(int,input().split())
    if find_rail(p)!=find_rail(q):
        union_rail(p,q)



comb={}
for i in range(1,N+1):
    if (find_road(i),find_rail(i)) in comb:
        comb[(find_road(i),find_rail(i))]+=1
    else:
        comb[(find_road(i),find_rail(i))]=1



for i in range(1,N+1):
    print(comb[(find_road(i),find_rail(i))])

Solution (Python):
from collections import*
class UNION_FIND(object):
    def __init__(self,n):
        
        
        
        self.parent=[-1 for i in range(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 size(self,x):
        
        return -self.parent[self.root(x)]   
        
    def union(self,x,y):
        
        
        
        x=self.root(x)
        y=self.root(y)
        
        if x==y:   
            return False
            
        
        
        if self.size(x)<self.size(y):
            x,y=y,x
        self.parent[x]+=self.parent[y]  
        self.parent[y]=x   
        return True


n,k,l=map(int,input().split())
u1=UNION_FIND(n)
u2=UNION_FIND(n)
d=defaultdict(int)

for i in range(k):
    a,b=map(int,input().split())
    u1.union(a-1,b-1)
for i in range(l):
    a,b=map(int,input().split())
    u2.union(a-1,b-1)

for i in range(n):
    d[(u1.root(i),u2.root(i))]+=1
print(*[d[(u1.root(i),u2.root(i))]for i in range(n)])

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


class UNION_FIND(object):
    def __init__(self,n):
        
        
        
        self.parent=[-1 for i in range(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 size(self,x):
        
        return -self.parent[self.root(x)]   
        
    def union(self,x,y):
        
        
        
        x=self.root(x)
        y=self.root(y)
        
        if x==y:   
            return False
            
        
        
        if self.size(x)<self.size(y):
            x,y=y,x
        self.parent[x]+=self.parent[y]  
        self.parent[y]=x   
        return True
        
n,k,l=map(int,input().split())
u1=UNION_FIND(n)
u2=UNION_FIND(n)
d=defaultdict(int)
for i in range(k):
    p,q=map(int,input().split())
    u1.union(p-1,q-1)
for i in range(l):
    p,q=map(int,input().split())
    u2.union(p-1,q-1)
for i in range(n):
    d[(u1.root(i),u2.root(i))]+=1
print(*[d[(u1.root(i),u2.root(i))]for i in range(n)])

Solution (Python):
from collections import defaultdict

class UnionFind:
    def __init__(self, n):
        
        self.par = [i for i in range(n+1)]
        
        self.rank = [0] * (n+1)
        
        self.count = [1] * (n+1)

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

    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.count[y] += self.count[x]
            self.count[x] = 0
        else:
            self.par[y] = x
            self.count[x] += self.count[y]
            self.count[y] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

    
    def size(self,x):
        q = UnionFind.find(self,x)
        return self.count[q]

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

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

d = defaultdict(int)
a = []
for i in range(n):
    t = (road.find(i),train.find(i))
    d[t] += 1
    a.append(t)

print(*[d[i] for i in a])

Solution (Python):
def init(par, n):
    global rank
    par = [i for i in range(n)]
    rank = [0] * n

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

def unite(par, x, y):
    global rank
    x = find(par, x)
    y = find(par, y)
    if x == y:
        return
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

N, K, L = map(int, input().split())
roads = [i for i in range(N)]
rank = [0] * N
for i in range(K):
    p, q = map(int, input().split())
    unite(roads, p - 1, q - 1)
rails = [i for i in range(N)]
rank = [0] * N
for i in range(L):
    p, q = map(int, input().split())
    unite(rails, p - 1, q - 1)
d = {}
for i in range(N):
    d[find(roads, i), find(rails, i)] = d.get((find(roads, i), find(rails, i)), 0) + 1
for i in range(N):
    print(d[find(roads, i), find(rails, i)], end = " ")
print()

Solution (Python):
def init(par, n):
    global rank
    par = [i for i in range(n)]
    rank = [0] * n

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

def unite(par, x, y):
    global rank
    x = find(par, x)
    y = find(par, y)
    if x == y:
        return
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

N, K, L = map(int, input().split())
roads = [i for i in range(N)]
rank = [0] * N
for i in range(K):
    p, q = map(int, input().split())
    unite(roads, p - 1, q - 1)
rails = [i for i in range(N)]
rank = [0] * N
for i in range(L):
    p, q = map(int, input().split())
    unite(rails, p - 1, q - 1)
d = {}
for i in range(N):
    d[find(roads, i), find(rails, i)] = d.get((find(roads, i), find(rails, i)), 0) + 1
for i in range(N):
    print(d[find(roads, i), find(rails, i)], end = " ")
print()

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

ar = [i for i in range(n)]
ah = [0 for _ in range(n)]
br = [i for i in range(n)]
bh = [0 for _ in range(n)]

def root(l, i):
  if l[i] == i:
    return i
  else:
    l[i] = root(l, l[i])
    return l[i]

def union(l, h, i, j):
  ip = root(l, i)
  jp = root(l, j)
  if ip == jp:
    return
  else:
    if h[ip] < h[jp]:
      l[ip] = jp
    elif h[ip] > h[jp]:
      l[jp] = ip
    else:
      if ip < jp:
        l[jp] = ip
        h[ip] += 1
      else:
        l[ip] = jp
        h[jp] += 1

for _ in range(k):
  p, q = map(int, input().split())
  if p < q:
    union(ar, ah, p-1, q-1)
  else:
    union(ar, ah, q-1, p-1)

for _ in range(l):
  r, s = map(int, input().split())
  if r < s:
    union(br, bh, r-1, s-1)
  else:
    union(br, bh, s-1, r-1)

abd = {}
for a, b in zip(ar, br):
  if (root(ar, a), root(br, b)) in abd:
    abd[(root(ar, a), root(br, b))] += 1
  else:
    abd[(root(ar, a), root(br, b))] = 1

for a, b in zip(ar, br):
  print(abd[(root(ar, a), root(br, b))])

Solution (Python):
from collections import*
class UnionFind():
    def __init__(self,size):
        self.table=[-1]*size
    def root(self,x):
        while self.table[x]>=0:
            x=self.table[x]
        return x
    def unite(self,x,y):
        s1=self.root(x)
        s2=self.root(y)
        if s1!=s2:
            if self.table[s1]>self.table[s2]:
                s1,s2=s2,s1
            self.table[s1]+=self.table[s2]
            self.table[s2]=s1
        return
    def same(self,x,y):
        return self.root(x)==self.root(y)
    def size(self,x):
        return -self.table[self.root(x)]
input=open(0).readline
n,k,l=map(int,input().split())
u=UnionFind(n)
v=UnionFind(n)
for _ in range(k):
    p,q=map(int,input().split())
    u.unite(p-1,q-1)
for _ in range(l):
    r,s=map(int,input().split())
    v.unite(r-1,s-1)
d=defaultdict(int)
a=[]
for i in range(n):
    t=(u.root(i),v.root(i))
    d[t]+=1
    a.append(t)
print(*[d[i]for i in a])

Solution (Python):
from collections import*
class UnionFind():
    def __init__(self,size):
        self.table=[-1]*size
    def root(self,x):
        while self.table[x]>=0:
            x=self.table[x]
        return x
    def unite(self,x,y):
        s1=self.root(x)
        s2=self.root(y)
        if s1!=s2:
            if self.table[s1]>self.table[s2]:
                s1,s2=s2,s1
            self.table[s1]+=self.table[s2]
            self.table[s2]=s1
        return
    def same(self,x,y):
        return self.root(x)==self.root(y)
    def size(self,x):
        return -self.table[self.root(x)]
input=open(0).readline
n,k,l=map(int,input().split())
u=UnionFind(n)
v=UnionFind(n)
for _ in range(k):
    p,q=map(int,input().split())
    u.unite(p-1,q-1)
for _ in range(l):
    r,s=map(int,input().split())
    v.unite(r-1,s-1)
d=defaultdict(int)
a=[]
for i in range(n):
    t=(u.root(i),v.root(i))
    d[t]+=1
    a.append(t)
print(*[d[i]for i in a])

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


class UFT:
    def __init__(self, N):
        self.UFdata = [-1] * (N+1)
        self.rank   = [0]  * (N+1)

    def find(self,x):
        UFdata = self.UFdata
        while UFdata[x] != -1:
            x = UFdata[x]
        return x

    def unite(self,x,y):
        UFdata = self.UFdata
        rank = self.rank 
        find = self.find

        x = find(x)
        y = find(y)
        if x != y:
            if rank[x] < rank[y]:
                x,y = y,x
            if rank[x] == rank[y]:
                rank[x] += 1
            UFdata[y] = x       
            

UF1 = UFT(N)
UF2 = UFT(N)
ans = [1] * (N+1)

import sys
input = sys.stdin.readline



for i in range(K):
    p,q = map(int,input().split())
    UF1.unite(p,q)
for i in range(L):
    p,q = map(int,input().split())
    UF2.unite(p, q)
counter=[]
from collections import defaultdict
cntdic =defaultdict(int)
for i in range(1,N+1):
  counter.append(UF1.find(i)+UF2.find(i)*10**6)
  cntdic[counter[-1]]+=1 

ans = [0]*(N+1)
for i in range(1,N+1):
    ans[i] = cntdic[counter[i-1]]

del ans[0]

print(" ".join( map(lambda x: str(x), ans)))

Solution (Python):
from collections import defaultdict

class UF():
    def __init__(self,n):
        self.l = [-1]*n
    def root(self, a):
        if self.l[a] < 0:
            return a
        else:
            self.l[a] = self.root(self.l[a])
        return self.l[a]
    def unite(self, a, b):
        a, b = self.root(a), self.root(b)
        if a == b:
            return
        if self.l[a] > self.l[b]:
            a, b = b, a
        self.l[a] += self.l[b]
        self.l[b] = a

n,k,l = map(int, input().split())
d = UF(n)
t = UF(n)
for i in range(k):
    r,s = map(int,input().split())
    d.unite(r-1, s-1)
for i in range(l):
    r,s = map(int,input().split())
    t.unite(r-1, s-1)
d_set = defaultdict(set)
t_set = defaultdict(set)
for i in range(n):
    d_set[d.root(i)].add(i)
    t_set[t.root(i)].add(i)

ans = []
cache = {}
for i in range(n):
    rd = d.root(i)
    rt = t.root(i)
    if (rd,rt) in cache:
        ans.append(cache[(rd,rt)])
    else:
        _ = len(d_set[rd] & t_set[rt])
        cache[(rd,rt)] = _
        ans.append(_)
print(*ans)

Solution (Python):

class UnionFind:
    """size(int)を指定
    root(x:int)->int:      根を求める
    unite(x,y:int):        要素をグループにまとめる 
    isSame(x,y:int)->bool: 要素同士が同じグループか判定する
    """
    
    
    def __init__(self, size: int):
        self.par = [-1]*size 
        for i in range(size):
            self.par[i] = i  
    
    def root(self, x: int) -> int:
        """根を求める"""
        if self.par[x] == x: 
            return x
        else:
            self.par[x] = self.root(self.par[x]) 
            return self.par[x]
    
    def isSame(self, x:int, y:int)->bool:
        """x と y が同じ集合に属するか否か"""
        return self.root(x)==self.root(y)
    
    def unite(self, x:int, y:int):
        """x と y の属する集合を併合"""
        x = self.root(x)
        y = self.root(y)
        if x == y: return
        self.par[x] = y
        

N,K,L = map(int, input().split())
uf_k = UnionFind(N)
uf_l = UnionFind(N)
for _ in range(K):
    p,q = map(int, input().split())
    uf_k.unite(p-1, q-1)
for _ in range(L):
    r,s= map(int, input().split())
    uf_l.unite(r-1, s-1)

cnt = dict()
for i in range(N):
    r_k,r_l = uf_k.root(i), uf_l.root(i)
    if (r_k,r_l) in cnt.keys():
        cnt[(r_k,r_l)] += 1
    else:
        cnt[(r_k,r_l)] = 1

ans = []
for i in range(N):
    r_k,r_l = uf_k.root(i), uf_l.root(i)
    ans.append(cnt[(r_k,r_l)])
print(*ans, sep=" ", end="\n")

Solution (Python):

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


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

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

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

    def __str__(self):
        ret = "parents\n"
        ret += " ".join(map(str, self.parent))
        ret += '\n'
        ret += " ".join(map(str, self.rank))
        return ret


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


def solve1():
    root = UnionFind(N)
    train = UnionFind(N)

    for _ in range(K):
        a, b = map(lambda x: int(x)-1, input().split())
        root.union(a, b)

    for _ in range(L):
        a, b = map(lambda x: int(x)-1, input().split())
        train.union(a, b)
    ans = [1]*N
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            else:
                if root.same(i, j) and train.same(i, j):
                    ans[i] += 1
    print(" ".join(map(str, ans)))


def solve2():
    ans = [0]*N
    root = UnionFind(N)
    train = UnionFind(N)
    for _ in range(K):
        a, b = map(lambda x: int(x)-1, input().split())
        root.union(a, b)

    for _ in range(L):
        a, b = map(lambda x: int(x)-1, input().split())
        train.union(a, b)

    d = 10**6
    nums = dict()
    for i in range(N):
        n = root.find(i)+train.find(i)*d
        if n in nums.keys():
            nums[n] = nums[n]+1
        else:
            nums[n] = 1

    for i in range(N):
        ans[i] = nums[root.find(i)+train.find(i)*d]

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


solve2()

Solution (Python):

import sys

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


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)
    
input = sys.stdin.readline
n,k,L = map(int,input().split())
rpar = [] 
tpar = []
rrank = [0]*n
trank= [0]*n


for i in range(n):
    
    rpar.append(i)
    tpar.append(i)


for i in range(k):
    x,y = map(int,input().split())
    unite(x-1,y-1,rpar,rrank)
for i in range(L):
    x,y = map(int,input().split())
    unite(x-1,y-1,tpar,trank)

num = []
d = {}
for i in range(n):
    num.append(find(i,rpar)+find(i,tpar)*10**6)
    if num[-1] in d:
        d[num[-1]] += 1
    else:
        d[num[-1]] = 1
res = ''
for i in range(n):
    if i != 0:
        res += ' '
    
    res += str(d[num[i]])

print(res)

Solution (Python):



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


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 = [] 
tpar = []
rrank = [0]*n
trank= [0]*n


for i in range(n):
    
    rpar.append(i)
    tpar.append(i)


for i in range(k):
    x,y = map(int,input().split())
    unite(x-1,y-1,rpar,rrank)
for i in range(L):
    x,y = map(int,input().split())
    unite(x-1,y-1,tpar,trank)

num = []
d = {}
for i in range(n):
    num.append(find(i,rpar)+find(i,tpar)*10**6)
    if num[-1] in d:
        d[num[-1]] += 1
    else:
        d[num[-1]] = 1
res = ''
for i in range(n):
    if i != 0:
        res += ' '
    
    res += str(d[num[i]])

print(res)

Solution (Python):
import array
import collections


class UnionFind(object):
    def __init__(self, number_of_nodes):
        
        self.par = array.array("L", range(number_of_nodes))
        self.rank = array.array("L", (0 for _ in range(number_of_nodes)))

    def root(self, node):
        if self.par[node] == node:
            return node
        else:
            r = self.root(self.par[node])
            self.par[node] = r
            return r

    def in_the_same_set(self, node1, node2):
        return self.root(node1) == self.root(node2)

    def unite(self, node1, node2):
        x = self.root(node1)
        y = self.root(node2)
        if x == y:
            pass
        elif 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

n, k, l = map(int, input().split())
roads = [map(int, input().split()) for _ in range(k)]
trains = [map(int, input().split()) for _ in range(l)]

uf1 = UnionFind(n+1)
for p, q in roads:
  uf1.unite(p, q)

uf2 = UnionFind(n+1)
for r, s in trains:
  uf2.unite(r, s)

count = collections.Counter([(uf1.root(i), uf2.root(i)) for i in range(1,n+1)])

print(' '.join([str(count[(uf1.root(i), uf2.root(i))]) for i in range(1,n+1)]))

Solution (Python):
import sys
from collections import deque, Counter
sys.setrecursionlimit(1000000)
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)]

G_r = [[] for _ in range(N+1)]
for elem in pq:
    G_r[elem[0]].append(elem[1])
    G_r[elem[1]].append(elem[0])
G_t = [[] for _ in range(N+1)]
for elem in rs:
    G_t[elem[0]].append(elem[1])
    G_t[elem[1]].append(elem[0])


field_r = [None]*(N+1)


def dfs_r(i, idx):
    q = deque()
    q.append(i)
    field_r[i] = idx
    while q:
        tmp = q.pop()
        for pos in G_r[tmp]:
            if field_r[pos] is None:
                field_r[pos] = idx
                q.append(pos)
            else:
                continue
idx = 0
for i in range(1, N+1):
    if field_r[i] is None:
        dfs_r(i, idx)
        idx += 1


field_t = [None]*(N+1)


def dfs_t(i, idx):
    q = deque()
    q.append(i)
    field_t[i] = idx
    while q:
        tmp = q.pop()
        for pos in G_t[tmp]:
            if field_t[pos] is None:
                field_t[pos] = idx
                q.append(pos)
            else:
                continue
idx = 0
for i in range(1, N+1):
    if field_t[i] is None:
        dfs_t(i, idx)
        idx += 1

m = list(zip(field_r[1:], field_t[1:]))
cnt = Counter(m)
ans = []
for elem in list(m):
    ans.append(cnt[elem])
print(' '.join(map(str, ans)))

Solution (Python):
import sys
from collections import deque, Counter
sys.setrecursionlimit(1000000)
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)]

G_r = [[] for _ in range(N+1)]
for elem in pq:
    G_r[elem[0]].append(elem[1])
    G_r[elem[1]].append(elem[0])
G_t = [[] for _ in range(N+1)]
for elem in rs:
    G_t[elem[0]].append(elem[1])
    G_t[elem[1]].append(elem[0])


field_r = [None]*(N+1)


def dfs_r(i, idx):
    q = deque()
    q.append(i)
    field_r[i] = idx
    while q:
        tmp = q.pop()
        for pos in G_r[tmp]:
            if field_r[pos] is None:
                field_r[pos] = idx
                q.append(pos)
            else:
                continue
idx = 0
for i in range(1, N+1):
    if field_r[i] is None:
        dfs_r(i, idx)
        idx += 1


field_t = [None]*(N+1)


def dfs_t(i, idx):
    q = deque()
    q.append(i)
    field_t[i] = idx
    while q:
        tmp = q.pop()
        for pos in G_t[tmp]:
            if field_t[pos] is None:
                field_t[pos] = idx
                q.append(pos)
            else:
                continue
idx = 0
for i in range(1, N+1):
    if field_t[i] is None:
        dfs_t(i, idx)
        idx += 1

m = list(zip(field_r[1:], field_t[1:]))
cnt = Counter(m)
ans = []
for elem in list(m):
    ans.append(cnt[elem])
print(' '.join(map(str, ans)))

Solution (Python):
def inpl(): return [int(i) for i in input().split()]
class UnionFind():
    def __init__(self, num):
        self.par = [-1 for _ in range(num)]
    
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            x = self.par[x]
            return self.find(x)
    
    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            if self.par[rx] < self.par[ry]:
                self.par[ry] = rx
            if self.par[rx] > self.par[ry]:
                self.par[rx] = ry
            else:
                self.par[rx] -= 1
                self.par[ry] = rx
        return

N, K, L = inpl()
ufk = UnionFind(N)
for i in range(K):
    p, q = inpl()
    ufk.union(p-1, q-1)

ufr = UnionFind(N)
for i in range(L):
    r, s = inpl()
    ufr.union(r-1, s-1)

from collections import defaultdict
ans = defaultdict(lambda: 0)
for i in range(N):
    ans[ufk.find(i),ufr.find(i)] +=1
Ans = [0 for _ in range(N)]
for i in range(N):
    Ans[i] = ans[ufk.find(i),ufr.find(i)]
print(*Ans)

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

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

class UnionFind:
    def __init__(self, node:int) -> None:
        self.n = node
        self.par = [i for i in range(self.n)]
        self.rank = [0 for i in range(self.n)]
        
    def find(self, x:int) -> int:
        if x == self.par[x]:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    def unite(self, x:int, y:int) -> bool:
        if self.isSame(x,y):
            
            return False
        
        rx = self.find(x)
        ry = self.find(y)
        
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = self.par[ry]
        else:
            self.par[ry] = self.par[rx]
            
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1
                
        return True
                
    def isSame(self, x:int, y:int) -> bool:
        return self.find(x) == self.find(y)
    
from collections import defaultdict
    
n,k,l = li()
pq = []
rs = []

for _ in range(k):
    pq.append(tuple(li_()))
    
for _ in range(l):
    rs.append(tuple(li_()))

road = UnionFind(n)
rail = UnionFind(n)

for p,q in pq:
    road.unite(p,q)
    
for r,s in rs:
    rail.unite(r,s)
    
for i in range(n):
    road.find(i)
    
for i in range(n):
    rail.find(i)
    
road_dic = {i:set() for i in range(n)}
rail_dic = {i:set() for i in range(n)}

for i in range(n):
    road_dic[road.par[i]].add(i)
    rail_dic[rail.par[i]].add(i)
    
ans_dic = defaultdict(int)
for i in range(n):
    if ans_dic[(road.par[i], rail.par[i])] == 0:
        ans_dic[(road.par[i], rail.par[i])] = len(road_dic[road.par[i]] & rail_dic[rail.par[i]])
    
ans = []
for i in range(n):
    ans.append(ans_dic[(road.par[i], rail.par[i])])
    
print(*ans)

Solution (Python):
from collections import Counter
N,K,L = map(int,input().split())
P = [tuple(map(int,input().split())) for i in range(K)]
R = [tuple(map(int,input().split())) for i in range(L)]

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1

uf1 = UnionFind(N)
for p,q in P:
    p,q = p-1,q-1
    if uf1.is_same(p,q): continue
    uf1.unite(p,q)

uf2 = UnionFind(N)
for r,s in R:
    r,s = r-1,s-1
    if uf2.is_same(r,s): continue
    uf2.unite(r,s)

pairs = Counter()
for i in range(N):
    a = uf1.root(i)
    b = uf2.root(i)
    pairs[(a,b)] += 1

ans = []
for i in range(N):
    a = uf1.root(i)
    b = uf2.root(i)
    ans.append(pairs[(a,b)])
print(*ans)

Solution (Python):

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.ranks[x] < self.ranks[y]:
            self.pars[x] = y
        else:
            self.pars[y] = x
            if self.ranks[x] == self.ranks[y]:
                self.ranks[x] += 1


N, K, L = map(int, input().split())
pqs = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(K)]
rss = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(L)]


UFRoad = UnionFind(N)
for p, q in pqs:
    UFRoad.union(p, q)


UFRailway = UnionFind(N)
for r, s in rss:
    UFRailway.union(r, s)

Ts = [(UFRoad.find(i), UFRailway.find(i), i) for i in range(N)] + [(N, N, N)]
Ts.sort()

anss = [0] * N
iFr = 0
for i in range(N):
    if Ts[i][0:2] != Ts[i + 1][0:2]:
        for j in range(iFr, i + 1):
            anss[Ts[j][2]] = i - iFr + 1
        iFr = i + 1

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