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
sys.setrecursionlimit(4100000)

import math

import logging

logging.basicConfig(level=logging.DEBUG)

logger = logging.getLogger(__name__)

from functools import reduce

from collections import Counter


class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [1 for _ in range(n)]

    def findRoot(self, i):
        if self.parent[i] == i:  
            return i
        else:
            self.parent[i] = self.findRoot(self.parent[i])  
            return self.parent[i]

    def unite(self, i, j):
        i_root = self.findRoot(i)
        j_root = self.findRoot(j)
        if i_root == j_root:
            return

        if self.rank[i_root] > self.rank[j_root]:  
            self.parent[j_root] = i_root
        elif self.rank[i_root] == self.rank[j_root]:
            self.parent[j_root] = i_root
            self.rank[i_root] += 1
        else:
            self.parent[i_root] = j_root

        return i

    def isSame(self, i, j):
        return self.findRoot(i) == self.findRoot(j)

    def setGroup(self, elements):
        reduce(self.unite, elements)


class UnionFindCounter:
    def __init__(self, n):
        self.N = n
        self.parent = list(range(n))
        self.rank = [1 for _ in range(n)]
        self._count = [1 for _ in range(n)]

    def findRoot(self, i):
        if self.parent[i] == i:  
            return i
        else:
            self.parent[i] = self.findRoot(self.parent[i])  
            return self.parent[i]

    def unite(self, i, j):
        i_root = self.findRoot(i)
        j_root = self.findRoot(j)
        if i_root == j_root:
            return

        if self.rank[i_root] > self.rank[j_root]:  
            self.parent[j_root] = i_root
            self._count[i_root] += self._count[j_root]
        elif self.rank[i_root] == self.rank[j_root]:
            self.parent[j_root] = i_root
            self.rank[i_root] += 1
            self._count[i_root] += self._count[j_root]
        else:
            self.parent[i_root] = j_root
            self._count[j_root] += self._count[i_root]

        return i

    def isSame(self, i, j):
        return self.findRoot(i) == self.findRoot(j)

    def setGroup(self, elements):
        reduce(self.unite, elements)

    def getCount(self):
        return [self._count[self.findRoot(i)] for i in range(self.N)]


def resolve():
    
    
    N, K, L = [int(x) for x in sys.stdin.readline().split()]  
    
    grid = [
        tuple([int(x) - 1 for x in sys.stdin.readline().split()])
        for _ in range(K + L)
    ]  

    logger.debug('{}'.format([]))

    p_uf = UnionFind(N)
    r_uf = UnionFind(N)
    both_uf = UnionFindCounter(N)

    for k in range(K):
        p, q = grid[k]
        p_uf.unite(p, q)

    for l in range(K, K + L):
        r, s = grid[l]
        r_uf.unite(r, s)

    
    
    

    pairs = [(p_uf.findRoot(i), r_uf.findRoot(i)) for i in range(N)]

    counts = Counter(pairs)

    print(' '.join([str(counts[pairs[i]]) for i in range(N)]))


if __name__ == "__main__":
    resolve()





import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """4 3 1
1 2
2 3
3 4
2 3"""
        output = """1 2 2 1"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """4 2 2
1 2
2 3
1 4
2 3"""
        output = """1 2 2 1"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """7 4 4
1 2
2 3
2 5
6 7
3 5
4 5
3 4
6 7"""
        output = """1 1 2 1 2 2 2"""
        self.assertIO(input, output)

    def test_入力例_4(self):
        input = """2 1 1
1 2
1 2"""
        output = """2 2"""
        self.assertIO(input, output)

    def test_入力例_5(self):
        input = """4 3 3
1 2
1 4
1 3
1 4
4 3
2 3"""
        output = """4 4 4 4"""
        self.assertIO(input, output)

    def test_入力例_6(self):
        input = """5 3 4
1 2
2 3
3 4
1 5
5 4
4 3
3 2"""
        output = """4 4 4 4 1"""
        self.assertIO(input, output)

Solution (Python):
import sys
input = sys.stdin.readline
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

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

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

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

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

n,k,l=map(int,input().split())
uf1=UnionFind(n)
for _ in range(k):
    p,q=map(int,input().split())
    uf1.union(p-1,q-1)
uf2=UnionFind(n)
for _ in range(l):
    p,q=map(int,input().split())
    uf2.union(p-1,q-1)
from collections import defaultdict
p=defaultdict(int)
for i in range(n):
    a=uf1.find(i)
    b=uf2.find(i)
    p[(a,b)]+=1
ans=[]
for i in range(n):
    ans.append(p[uf1.find(i),uf2.find(i)])
print(*ans)

Solution (Python):
import itertools

class UnionFind:
    def __init__(self, size):
        self.parent = [-1] * (size + 1)  

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

    def merge(self, x, y):  
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.parent[x] > self.parent[y]:  
            x, y = y, x
        self.parent[x] += self.parent[y]  
        self.parent[y] = x  
        return True

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

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

import collections
N,K,L = list(map(int,input().split(" ")))
tree1 = UnionFind(N)
tree2 = UnionFind(N)
anss = collections.defaultdict(lambda :0)
querys = []
for _ in range(K):
    p,q = map(int,input().split(" "))
    tree1.merge(p,q)
for _ in range(L):
    r, s = map(int, input().split(" "))
    tree2.merge(r, s)

for i in range(1,N + 1):
    anss[(tree1.root(i),tree2.root(i))] += 1
temp = [0] * (N + 1)
for i in range(1,N + 1):
    temp[i] =  anss[(tree1.root(i),tree2.root(i))]
print(*temp[1:])

Solution (Python):
import itertools

class UnionFind:
    def __init__(self, size):
        self.parent = [-1] * (size + 1)  

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

    def merge(self, x, y):  
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.parent[x] > self.parent[y]:  
            x, y = y, x
        self.parent[x] += self.parent[y]  
        self.parent[y] = x  
        return True

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

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

import collections
N,K,L = list(map(int,input().split(" ")))
tree1 = UnionFind(N)
tree2 = UnionFind(N)
anss = collections.defaultdict(lambda :0)
querys = []
for _ in range(K):
    p,q = map(int,input().split(" "))
    tree1.merge(p,q)
for _ in range(L):
    r, s = map(int, input().split(" "))
    tree2.merge(r, s)

for i in range(1,N + 1):
    anss[(tree1.root(i),tree2.root(i))] += 1
temp = [0] * (N + 1)
for i in range(1,N + 1):
    temp[i] =  anss[(tree1.root(i),tree2.root(i))]
print(*temp[1:])

Solution (Python):
from collections import defaultdict
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

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

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

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

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

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
      
n, k, l = map(int, input().split())
ufR, ufT = UnionFind(n), UnionFind(n)
for _ in range(k):
  p, q = map(int, input().split())
  p -= 1
  q -= 1
  ufR.union(p, q)
for _ in range(l):
  r, s = map(int, input().split())
  r -= 1
  s -= 1
  ufT.union(r, s)
d = defaultdict(int)
L = []
for i in range(n):
  a = ufR.find(i)
  b = ufT.find(i)
  d[(a, b)] += 1
  L.append((a, b))
print(*(d[L[i]] for i in range(n)))

Solution (Python):











import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N, K, L = MI()
    
    class UnionFind():
        def __init__(self, n):
            self.nodes=[-1] * n  

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

        def unite(self, x, y):
            root_x=self.get_root(x)
            root_y=self.get_root(y)
            
            
            
            if root_x != root_y:
                
                if self.nodes[root_x] < self.nodes[root_y]:
                    big_root=root_x
                    small_root=root_y
                else:
                    small_root=root_x
                    big_root=root_y
                self.nodes[big_root] += self.nodes[small_root]
                self.nodes[small_root]=big_root
            
        def same(self,x,y):
            return self.get_root(x)==self.get_root(y)
    uf1=UnionFind(N)
    uf2 = UnionFind(N)
    uf_both = UnionFind(N)
    for _ in range(K):
        p, q = MI_()
        uf1.unite(p, q)
        
    for _ in range(L):
        r, s = MI_()
        uf2.unite(r, s)

    cnt = defaultdict(int)    
    A = [-1]*N
    B = [-1]*N
    for i in range(N):
        A[i] = uf1.get_root(i)
        B[i] = uf2.get_root(i)
        cnt[A[i],B[i]] += 1
    
    print(*[cnt[A[i],B[i]] for i in range(N)] )


if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter


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

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

    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)

        if rx == ry:
            return

        if self.parents[rx] > self.parents[ry]:
            rx, ry = ry, rx
            x, y = y, x
            w = -w

        self.parents[rx] += self.parents[ry]
        self.parents[ry] = rx
        self.weight[ry] = + self.weight[x] - w - self.weight[y]

    def find_position(self, x):
        if self.parents[x] < 0:
            return 0
        else:
            return -self.weight[x] + self.find_position(self.parents[x])

    def diff(self, x, y):
        if self.find(x) != self.find(y):
            raise Exception('"{}" belongs to a different tree from "{}"'.format(x, y))
        return self.find_position(y) - self.find_position(x)


N, K, L = map(int, input().split())
uf1 = WeightedUnionFind(N)
uf2 = WeightedUnionFind(N)
for _ in range(K):
    p, q = map(int, input().split())
    uf1.union(p - 1, q - 1, 0)

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

path = [None] * N
for i in range(N):
    path[i] = (uf1.find(i), uf2.find(i))

cnt = Counter(path)
for i in range(N - 1):
    print(cnt[path[i]], end=' ')
print(cnt[path[N - 1]])

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

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

   def union(self, x, y):
       x = self.find(x)
       y = self.find(y)

       if x == y:
           return

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

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

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

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

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

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

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

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

   def __str__(self):
       return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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

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

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

from collections import defaultdict
dic = defaultdict(int)
pair = []
for i in range(n):
   pair.append((uf1.find(i), uf2.find(i)))
   dic[(uf1.find(i), uf2.find(i))] += 1

for i in range(n):
   print(dic[pair[i]])

Solution (Python):
from collections import Counter


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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

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

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


N, K, L = map(int, input().split())
uf1 = UnionFind(N)
uf2 = UnionFind(N)
for _ in range(K):
    p, q = map(int, input().split())
    uf1.union(p - 1, q - 1)

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

path = [None] * N
for i in range(N):
    path[i] = (uf1.find(i), uf2.find(i))

cnt = Counter(path)
for i in range(N - 1):
    print(cnt[path[i]], end=' ')
print(cnt[path[N - 1]])

Solution (Python):
import sys
from collections import defaultdict
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

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

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

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

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

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


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

ufl = UnionFind(N)
uft = UnionFind(N)

for _ in range(K):
    p, q = map(int, readline().split())
    ufl.union(p-1, q-1)

for _ in range(L):
    r, s = map(int, readline().split())
    uft.union(r-1, s-1)



grp = [(ufl.find(i), uft.find(i)) for i in range(N)]



dd = defaultdict(int)

for g in grp:
    dd[g] += 1

ans = []

for i in range(N):
    ans.append(dd[grp[i]])

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

'''
cnts = [0] * N

for i in range(N):
    cnts[i] = uft.size(i)

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

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

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

class Union_Find():
    def __init__(self, num):
        self.par = [-1]*(num+1)
        self.siz = [1]*(num+1)

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

    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
                self.siz[rx] += self.siz[ry]
            elif self.par[rx] > self.par[ry]:
                self.par[rx] = ry
                self.siz[ry] += self.siz[rx]
            else:
                self.par[rx] -= 1
                self.par[ry] = rx
                self.siz[rx] += self.siz[ry]
        return

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

road_root = Union_Find(n)
train_root = Union_Find(n)
for i in range(k):
    road_root.union(road[i][0], road[i][1])
for i in range(l):
    train_root.union(train[i][0], train[i][1])

road = []
train = []
for i in range(n):
    road.append(road_root.find(i+1))
    train.append(train_root.find(i+1))

road
train

pair = []
for i in range(n):
    pair.append((road[i], train[i]))

d = dict()
for i in range(n):
    if pair[i] not in d:
        d[pair[i]] = 1
    else:
        d[pair[i]] += 1

ans = []
for i in range(n):
    ans.append(d[pair[i]])

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

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

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

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

u1 = UnionFind(n)
for i in range(k):
    u1.union(pq[i][0], pq[i][1])

u2 = UnionFind(n)
for i in range(l):
    u2.union(rs[i][0], rs[i][1])

for i in range(n):
    a = u1.find(i + 1)
    b = u2.find(i + 1)

from collections import defaultdict
d = defaultdict(list)
for i in range(1, len(u1.par)):
    d[str(u1.par[i]) + ' ' + str(u2.par[i])].append(i)

ans = [0] * n
for k in d.keys():
    for v in d[k]:
        ans[v - 1] = len(d[k])

ans2 = ''
for i in range(len(ans)):
    ans2 += str(ans[i]) + ' '

print(ans2[:-1])

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


N, K, L = map(int, input().split())
U1 = UnionFind(N)
U2 = UnionFind(N)
for _ in range(K):
    a, b = map(int, input().split())
    U1.Unite(a, b)
for _ in range(L):
    a, b = map(int, input().split())
    U2.Unite(a, b)

Roots = [0]
dic = {}
for n in range(1, N+1):
    r1 = U1.Find_Root(n)
    r2 = U2.Find_Root(n)
    r = r1*2*N + r2
    Roots.append(r)
    if not r in dic.keys():
        dic[r] = 1
    else:
        dic[r] += 1
    
ans = []
for n in range(1, N+1):
    ans.append(dic[Roots[n]])

print(" ".join([str(a) for a in ans]))

Solution (Python):

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

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

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

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

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

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())



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

uf_road = UnionFind(N)
uf_train = UnionFind(N)

for _ in range(K):
    a, b = map(int, input().split())
    uf_road.union(a-1, b-1)
    
for _ in range(L):
    a, b = map(int, input().split())
    uf_train.union(a-1, b-1)

from collections import defaultdict

d = defaultdict(int)
for i in range(N):
    d[(uf_road.find(i), uf_train.find(i))]+=1
    
ans = []
for i in range(N):
    ans.append(d[(uf_road.find(i), uf_train.find(i))])

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

Solution (Python):


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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

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

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

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

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


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

uf_road = UnionFind(N)
uf_train = UnionFind(N)

for _ in range(K):
    a, b = map(int, input().split())
    uf_road.union(a-1, b-1)
    
for _ in range(L):
    a, b = map(int, input().split())
    uf_train.union(a-1, b-1)

from collections import defaultdict

d = defaultdict(int)
for i in range(N):
    d[(uf_road.find(i), uf_train.find(i))]+=1
    
ans = []
for i in range(N):
    ans.append(d[(uf_road.find(i), uf_train.find(i))])

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

Solution (Python):
import sys
input = sys.stdin.readline
def col(n, m):
    X = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        X[a-1].append(b-1)
        X[b-1].append(a-1)
    C = [-1] * n
    c = 0
    for i in range(N):
        if C[i] >= 0: continue
        Q = [i]
        C[i] = c
        while Q:
            x = Q.pop()
            for y in X[x]:
                if C[y] == -1:
                    C[y] = C[x]
                    Q.append(y)
        c += 1
    return C

N, K, L = map(int, input().split())
A = col(N, K)
B = col(N, L)
D = {}
for a, b in zip(A, B):
    t = (a<<18) + b
    if t in D: D[t] += 1
    else: D[t] = 1

print(*[D[(a<<18)+b] for a, b in zip(A, B)])

Solution (Python):
def col(n, m):
    X = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        X[a-1].append(b-1)
        X[b-1].append(a-1)
    C = [-1] * n
    c = 0
    for i in range(N):
        if C[i] >= 0: continue
        Q = [i]
        C[i] = c
        while Q:
            x = Q.pop()
            for y in X[x]:
                if C[y] == -1:
                    C[y] = C[x]
                    Q.append(y)
        c += 1
    return C

N, K, L = map(int, input().split())
A = col(N, K)
B = col(N, L)
D = {}
for a, b in zip(A, B):
    t = (a<<18) + b
    if t in D: D[t] += 1
    else: D[t] = 1

print(*[D[(a<<18)+b] for a, b in zip(A, B)])

Solution (Python):
class UnionFindVerSize():
    def __init__(self, N):
        """ N個のノードのUnion-Find木を作成する """
        
        self._parent = [n for n in range(0, N+1)]
        
        self._size = [1] * (N + 1)

    def find_root(self, x):
        """ xの木の根(xがどのグループか)を求める """
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x]) 
        return self._parent[x]

    def unite(self, x, y):
        """ xとyの属するグループを併合する """
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        
        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        """ xが属するグループのサイズ（個数）を返す """
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        """ xとyが同じ集合に属するか否か """
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        """ グループ数を計算して返す """
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans
    
N, K, L = map(int, input().split())
p, q, r, s = [], [], [], []
uf1 = UnionFindVerSize(N)
uf2 = UnionFindVerSize(N)

for _ in range(K):
    tmp = list(map(int, input().split()))
    uf1.unite(tmp[0], tmp[1])
for _ in range(L):
    tmp = list(map(int, input().split()))
    uf2.unite(tmp[0], tmp[1])
    
d = {}
for i in range(1, N+1):
    k = uf1.find_root(i)
    l = uf2.find_root(i)
    d[(k, l)] = d.get((k, l), 0) + 1
    
ans = []
for i in range(1, N+1):
    ans.append(d[(uf1.find_root(i), uf2.find_root(i))])
print(*ans)

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

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


N, K, L = map(int, input().split())
ufk = UnionFind(N)
for _ in range(K):
    p, q = map(int, input().split())
    ufk.union(p, q)
ufl = UnionFind(N)
for _ in range(L):
    r, s = map(int, input().split())
    ufl.union(r, s)

d = {}
for i in range(1, N+1):
    k_par = ufk.find(i)
    l_par = ufl.find(i)
    d[(k_par, l_par)] = d.get((k_par, l_par), 0) + 1

ans = []
for i in range(1, N+1):
    ans.append(d[(ufk.find(i), ufl.find(i))])
print(*ans)