Problem:
 Score : 400 points    Problem Statement There are N cities. There are also K roads and L railways, extending between the cities.
The i -th road bidirectionally connects the p_i -th and q_i -th cities, and the i -th railway bidirectionally connects the r_i -th and s_i -th cities.
No two roads connect the same pair of cities. Similarly, no two railways connect the same pair of cities.  We will say city A and B are connected by roads if city B is reachable from city A by traversing some number of roads. Here, any city is considered to be connected to itself by roads.
We will also define connectivity by railways similarly.  For each city, find the number of the cities connected to that city by both roads and railways.      Constraints  2 ≦ N ≦ 2*10^5  1 ≦ K, L≦ 10^5  1 ≦ p_i, q_i, r_i, s_i ≦ N  p_i < q_i  r_i < s_i  When i ≠ j , (p_i, q_i) ≠ (p_j, q_j)  When i ≠ j , (r_i, s_i) ≠ (r_j, s_j)         Input The input is given from Standard Input in the following format:  N  K  L  p_1  q_1 : p_K  q_K  r_1  s_1 : r_L  s_L       Output Print N integers. The i -th of them should represent the number of the cities connected to the i -th city by both roads and railways.        Sample Input 1 4 3 1
1 2
2 3
3 4
2 3      Sample Output 1 1 2 2 1  All the four cities are connected to each other by roads.  By railways, only the second and third cities are connected. Thus, the answers for the cities are 1, 2, 2 and 1 , respectively.       Sample Input 2 4 2 2
1 2
2 3
1 4
2 3      Sample Output 2 1 2 2 1       Sample Input 3 7 4 4
1 2
2 3
2 5
6 7
3 5
4 5
3 4
6 7      Sample Output 3 1 1 2 1 2 2 2

Solution (Python):
from collections import defaultdict

class UnionFind :
    def __init__(self, size) :
        """
        Parameters
        ---
        size : int
            頂点数
        """
        self.parent = list(range(size))
        self.height = [0] * size
        self.size = [1] * size
        self.component = size

    def root(self, index) :
        """
        親のインデックスの取得

        Parameters
        ---
        index : int
            取得する頂点のインデックス

        Returns
        ---
        rootIndex : int
            指定した頂点の根のインデックス
        """
        if self.parent[index] == index :  
            return index
        rootIndex = self.root(self.parent[index])  
        self.parent[index] = rootIndex  
        return rootIndex

    def union(self, index1, index2) :  
        """
        木の結合

        Parameters
        ---
        index1 : int
        index2 : int
            結合する頂点のインデックス
        """
        root1 = self.root(index1)
        root2 = self.root(index2)

        if root1 == root2 :  
            return

        self.component -= 1  

        if self.height[root1] < self.height[root2] :
            self.parent[root1] = root2  
            self.size[root2] += self.size[root1]
        else :
            self.parent[root2] = root1  
            self.size[root1] += self.size[root2]
            if self.height[root1] == self.height[root2] :
                self.height[root1] += 1
        return

    def isSameRoot(self, index1, index2) :
        """
        同じ木に属するかを判定する

        Parameters
        ---
        index1 : int
        index2 : int

        Returns
        ---
        boolean
        """
        return self.root(index1) == self.root(index2)

    def sizeOfSameRoot(self, index) :
        """
        指定した頂点の属する木の大きさを取得する
        """
        return self.size[self.root(index)]

    def getComponent(self) :
        """
        連結成分数を取得する
        """
        return self.component

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

train = UnionFind(N)
road = UnionFind(N)

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

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

cnt = defaultdict(int)

for i in range(N):
    cnt[(road.root(i), train.root(i))] += 1

ans = []
for i in range(N):
    ans.append(cnt[(road.root(i), train.root(i))])

print(*ans)

Solution (Python):
N,K,L = map(int,input().split())
PQ = [tuple(map(int,input().split())) for i in range(K)]
RS = [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

roads = UnionFind(N)
rails = UnionFind(N)
for p,q in PQ:
    p,q = p-1,q-1
    roads.unite(p,q)
for r,s in RS:
    r,s = r-1,s-1
    rails.unite(r,s)
for i in range(N):
    roads.root(i)
    rails.root(i)

from collections import Counter
ctr = Counter()
for i in range(N):
    ctr[(roads.parent[i], rails.parent[i])] += 1
ans = []
for i in range(N):
    ans.append(ctr[(roads.parent[i], rails.parent[i])])
print(*ans)

Solution (Python):
from collections import Counter

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

road = [tuple(map(int,input().split())) for i in range(K)]
train = [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


uf_road = UnionFind(N)
for p,q in road:
    p,q = p-1, q-1
    if not uf_road.is_same(p,q):
        uf_road.unite(p,q)

uf_train = UnionFind(N)
for r,s in train:
    r,s = r-1, s-1
    if not uf_train.is_same(r,s):
        uf_train.unite(r,s)

total_union_num = Counter()
for i in range(N):
    r = uf_road.root(i)
    t = uf_train.root(i)
    total_union_num[(r,t)] += 1

ans = []
for i in range(N):
    r = uf_road.root(i)
    t = uf_train.root(i)
    ans.append(total_union_num[(r,t)])

print(*ans)

Solution (Python):
class UnionFind :
    """
    Union Find木
    ---
    頂点のインデックスは0~

    Attributes
    ---
    parent : list<int>
        親のリスト．parent[頂点のインデックス] = 親のインデックス
    height : list<int>
        各木の高さ
    size : list<int>
        各木の頂点数
    component : int
        連結成分の数
    """

    def __init__(self, size) :
        """
        Parameters
        ---
        size : int
            頂点数
        """
        self.parent = list(range(size))
        self.height = [0] * size
        self.size = [1] * size
        self.component = size

    def root(self, index) :
        """
        親のインデックスの取得

        Parameters
        ---
        index : int
            取得する頂点のインデックス

        Returns
        ---
        rootIndex : int
            指定した頂点の根のインデックス
        """
        if self.parent[index] == index :  
            return index
        rootIndex = self.root(self.parent[index])  
        self.parent[index] = rootIndex  
        return rootIndex

    def union(self, index1, index2) :  
        """
        木の結合

        Parameters
        ---
        index1 : int
        index2 : int
            結合する頂点のインデックス
        """
        root1 = self.root(index1)
        root2 = self.root(index2)

        if root1 == root2 :  
            return

        root1, root2 = min(root1, root2), max(root1, root2)
        self.parent[root2] = root1


    def isSameRoot(self, index1, index2) :
        """
        同じ木に属するかを判定する

        Parameters
        ---
        index1 : int
        index2 : int

        Returns
        ---
        boolean
        """
        return self.root(index1) == self.root(index2)

    def sizeOfSameRoot(self, index) :
        """
        指定した頂点の属する木の大きさを取得する
        """
        return self.size[self.root(index)]

    def getComponent(self) :
        """
        連結成分数を取得する
        """
        return self.component

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

train = UnionFind(N)
road = UnionFind(N)

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

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

countList = []
for i in range(N):
    countList.append((train.root(i), road.root(i)))

count = Counter(countList)
ans = [count[(train.root(i), road.root(i))] for i in range(N)]
print(*ans)

Solution (Python):



class UnionFind(object):
    '''Represents a data structure that tracks a set of elements partitioned
       into a number of disjoint (non-overlapping) subsets.
    Landau notation: O(α(n)), where α(n) is the inverse Ackermann function.
    See:
    https://www.youtube.com/watch?v=zV3Ul2pA2Fw
    https://en.wikipedia.org/wiki/Disjoint-set_data_structure
    https://atcoder.jp/contests/abc120/submissions/4444942
    '''

    def __init__(self, number_count: int):
        '''
        Args:
            number_count: The size of elements (greater than 2).
        '''
        self.parent_numbers = [-1 for _ in range(number_count)]

    def find_root(self, number: int) -> int:
        '''Follows the chain of parent pointers from number up the tree until
           it reaches a root element, whose parent is itself.
        Args:
            number: The trees id (0-index).
        Returns:
            The index of a root element.
        '''
        if self.parent_numbers[number] < 0:
            return number

        self.parent_numbers[number] = self.find_root(self.parent_numbers[number])
        return self.parent_numbers[number]

    def get_group_size(self, number: int) -> int:
        '''
        Args:
            number: The trees id (0-index).
        Returns:
            The size of group.
        '''
        return -self.parent_numbers[self.find_root(number)]

    def is_same_group(self, number_x: int, number_y: int) -> bool:
        '''Represents the roots of tree number_x and number_y are in the same
           group.
        Args:
            number_x: The trees x (0-index).
            number_y: The trees y (0-index).
        '''
        return self.find_root(number_x) == self.find_root(number_y)

    def merge_if_needs(self, number_x: int, number_y: int) -> bool:
        '''Uses find_root to determine the roots of the tree number_x and
           number_y belong to. If the roots are distinct, the trees are combined
           by attaching the roots of one to the root of the other.
        Args:
            number_x: The trees x (0-index).
            number_y: The trees y (0-index).
        '''
        x = self.find_root(number_x)
        y = self.find_root(number_y)

        if x == y:
            return False

        if self.get_group_size(x) >= self.get_group_size(y):
            self.parent_numbers[x] += self.parent_numbers[y]
            self.parent_numbers[y] = x
        else:
            self.parent_numbers[y] += self.parent_numbers[x]
            self.parent_numbers[x] = y
        return True


def main():
    from collections import Counter

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

    for _ in range(k):
        pi, qi = map(lambda x: int(x) - 1, input().split())

        if road.is_same_group(pi, qi):
            continue

        road.merge_if_needs(pi, qi)

    for _ in range(l):
        ri, si = map(lambda x: int(x) - 1, input().split())

        if rail.is_same_group(ri, si):
            continue

        rail.merge_if_needs(ri, si)

    
    
    
    
    pairs = Counter()
    ans = [0 for _ in range(n)]

    for i in range(n):
        hwy = road.find_root(i)
        rwy = rail.find_root(i)
        pairs[(hwy, rwy)] += 1

    for i in range(n):
        hwy = road.find_root(i)
        rwy = rail.find_root(i)
        ans[i] = pairs[(hwy, rwy)]

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


if __name__ == '__main__':
    main()

Solution (Python):



class UnionFind(object):
    '''Represents a data structure that tracks a set of elements partitioned
       into a number of disjoint (non-overlapping) subsets.
    Landau notation: O(α(n)), where α(n) is the inverse Ackermann function.
    See:
    https://www.youtube.com/watch?v=zV3Ul2pA2Fw
    https://en.wikipedia.org/wiki/Disjoint-set_data_structure
    https://atcoder.jp/contests/abc120/submissions/4444942
    '''

    def __init__(self, number_count: int):
        '''
        Args:
            number_count: The size of elements (greater than 2).
        '''
        self.parent_numbers = [-1 for _ in range(number_count)]

    def find_root(self, number: int) -> int:
        '''Follows the chain of parent pointers from number up the tree until
           it reaches a root element, whose parent is itself.
        Args:
            number: The trees id (0-index).
        Returns:
            The index of a root element.
        '''
        if self.parent_numbers[number] < 0:
            return number

        self.parent_numbers[number] = self.find_root(self.parent_numbers[number])
        return self.parent_numbers[number]

    def get_group_size(self, number: int) -> int:
        '''
        Args:
            number: The trees id (0-index).
        Returns:
            The size of group.
        '''
        return -self.parent_numbers[self.find_root(number)]

    def is_same_group(self, number_x: int, number_y: int) -> bool:
        '''Represents the roots of tree number_x and number_y are in the same
           group.
        Args:
            number_x: The trees x (0-index).
            number_y: The trees y (0-index).
        '''
        return self.find_root(number_x) == self.find_root(number_y)

    def merge_if_needs(self, number_x: int, number_y: int) -> bool:
        '''Uses find_root to determine the roots of the tree number_x and
           number_y belong to. If the roots are distinct, the trees are combined
           by attaching the roots of one to the root of the other.
        Args:
            number_x: The trees x (0-index).
            number_y: The trees y (0-index).
        '''
        x = self.find_root(number_x)
        y = self.find_root(number_y)

        if x == y:
            return False

        if self.get_group_size(x) >= self.get_group_size(y):
            self.parent_numbers[x] += self.parent_numbers[y]
            self.parent_numbers[y] = x
        else:
            self.parent_numbers[y] += self.parent_numbers[x]
            self.parent_numbers[x] = y
        return True


def main():
    from collections import Counter

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

    for _ in range(k):
        pi, qi = map(lambda x: int(x) - 1, input().split())

        if road.is_same_group(pi, qi):
            continue

        road.merge_if_needs(pi, qi)

    for _ in range(l):
        ri, si = map(lambda x: int(x) - 1, input().split())

        if rail.is_same_group(ri, si):
            continue

        rail.merge_if_needs(ri, si)

    
    
    
    
    pairs = Counter()
    ans = [0 for _ in range(n)]

    for i in range(n):
        hwy = road.find_root(i)
        rwy = rail.find_root(i)
        pairs[(hwy, rwy)] += 1

    for i in range(n):
        hwy = road.find_root(i)
        rwy = rail.find_root(i)
        ans[i] = pairs[(hwy, rwy)]

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import collections






















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


def do():
    sys.setrecursionlimit(100000000)

    N,K,L = list(map(int, input().split(" ")))
    querys1 = [list(map(int, input().split(" "))) for i in range(K)]
    querys2 = [list(map(int, input().split(" "))) for i in range(L)]
    uf1 = UnionFind(N + 1)
    uf2 = UnionFind(N + 1)
    for query in querys1:
        a,b= query
        uf1.merge(a,b)
    for query in querys2:
        a, b = query
        uf2.merge(a, b)
    di = collections.defaultdict(lambda :0)
    for i in range(1,N+1):
        di[ (uf1.root(i),uf2.root(i))] += 1
    anss = []
    for i in range(1,N+1):

        anss.append( str(di[(uf1.root(i),uf2.root(i))]))
    print(" ".join(anss))

if __name__ == "__main__":
    do()

Solution (Python):
N,K,L=map(int,input().split())
pq=[list(map(int,input().split())) for i in range(K)]
rs=[list(map(int,input().split())) for i in range(L)]
class UnionFind:
    def __init__(self,N):
        self.Parent=[-1]*N
    def unite(self,m,n):
        rm=self.root(m)
        rn=self.root(n)
        if rm==rn:
            return False
        else:
            if self.size(rm)<self.size(rn):
                rm,rn=rn,rm
            self.Parent[rm]+=self.Parent[rn]
            self.Parent[rn]=rm
            return True
    def root(self,n):
        if self.Parent[n]<0:
            return n
        else:
            self.Parent[n]=self.root(self.Parent[n])
            return self.Parent[n]
    def size(self,n):
        return -self.Parent[self.root(n)]
u=UnionFind(N)
v=UnionFind(N)
for e in pq:
    u.unite(e[0]-1,e[1]-1)
for e in rs:
    v.unite(e[0]-1,e[1]-1)
from collections import defaultdict
d=defaultdict(int)
for i in range(N):
    d[(u.root(i),v.root(i))]+=1
a=[]
for i in range(N):
    a.append(d[(u.root(i),v.root(i))])
print(*a)

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.size = [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.find(self.par[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.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            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 get_depth(self, x):
        return self.rank[self.find(x)]
    
    
    def get_size(self, x):
        return self.size[self.find(x)]
    
    
    def group_sum(self):
        c = 0
        for i in range(len(self.par)):
            if self.find(i) == i:
                c += 1
        return c

if __name__ == "__main__":
    N,K,L = map(int, input().split())
    uf_r = UnionFind(N)
    uf_t = UnionFind(N)
    d = defaultdict(int)

    for i in range(K):
        p, q = [int(i) for i in input().split()]
        uf_r.unite(p, q)
    
    for i in range(L):
        r, s = [int(i) for i in input().split()]
        uf_t.unite(r, s)
    
    for i in range(1,N+1):
        d[(uf_r.find(i), uf_t.find(i))] += 1
    
    print(*[d[(uf_r.find(i), uf_t.find(i))] for i in range(1,N+1)])

Solution (Python):
class UnionFind():
    n=1
    rnk=[0]
    par=[0]
    sze=[1]
    def __init__(self,N):
        self.n=N
        self.rnk=[0 for i in range(self.n)]
        self.par=[i for i in range(self.n)]
        self.sze=[1 for i in range(self.n)]
    def find(self,x):
        if x==self.par[x]:
            return x
        else:
            self.par[x]=self.find(self.par[x])
            return self.par[x]
    def unite(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if x==y:
            return
        if (self.rnk[x]<self.rnk[y]):
            self.par[x]=y
            self.sze[y]+=self.sze[x]
            self.sze[x]=0
        else:
            self.par[y]=x
            self.sze[x]+=self.sze[y]
            self.sze[y]=0
        if (self.rnk[x]==self.rnk[y]):
            self.rnk[x]+=1
    def same(self,x,y):
        return self.find(x)==self.find(y)
    def size(self,x):
        return self.sze[self.find(x)]

N,K,L=map(int,input().split())
Train=UnionFind(N)
for i in range(K):
    p,q=map(int,input().split())
    Train.unite(p-1,q-1)
Road=UnionFind(N)
for i in range(L):
    r,s=map(int,input().split())
    Road.unite(r-1,s-1)
D=dict()
for i in range(N):
    x=Train.find(i)
    y=Road.find(i)
    if (x,y) in D:
        D[(x,y)]+=1
    else:
        D[(x,y)]=1
ans=[D[(Train.find(i),Road.find(i))] for i in range(N)]
print(" ".join([str(i) for i in ans]))

Solution (Python):
from collections import defaultdict as dd

N, K, L = list(map(int, input().split()))
PQ = [list(map(int, input().split())) for _ in range(K)]
RS = [list(map(int, input().split())) for _ in range(L)]

def uft_root(g, a):
	if g[a] < 0:
		return a
	g[a] = uft_root(g, g[a])
	return g[a]

def uft_size(g, a):
	return -g[uft_root(g, a)]

def uft_merge(g, a, b):
	a, b = uft_root(g, a), uft_root(g, b)
	if a == b:
		return
	size_a, size_b = uft_size(g, a), uft_size(g, b)
	if size_a < size_b:
		a, b = b, a
		size_a, size_b = size_b, size_a
	g[a] -= size_b
	g[b] = a

uft_pq = [-1] * N
uft_rs = [-1] * N

for p, q in PQ:
	p, q = p - 1, q - 1
	uft_merge(uft_pq, p, q)
for r, s in RS:
	r, s = r - 1, s - 1
	uft_merge(uft_rs, r, s)

group = dd(int)
for n in range(N):
	group[(uft_root(uft_pq, n), uft_root(uft_rs, n))] += 1

result = []
for n in range(N):
	result += [group[(uft_root(uft_pq, n), uft_root(uft_rs, n))]]
print(" ".join(map(str, result)))

Solution (Python):


class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n)) 
        self.size = [1]*n 
 
    def root(self, x): 
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x 
 
    def merge(self, x, y): 
        x, y = self.root(x), self.root(y)
        if x == y: return False
        if self.size[x] < self.size[y]: x,y=y,x 
        self.size[x] += self.size[y] 
        self.parent[y] = x 
        return True
 
    def issame(self, x, y): 
        return self.root(x) == self.root(y)
        
    def getsize(self,x): 
        return self.size[self.root(x)]


import sys
input = sys.stdin.readline

n,k,l = [int(i) for i in input().split()]

UF1 = UnionFind(n)
for _ in range(k):
    p,q = [int(i)-1 for i in input().split()]
    UF1.merge(p,q)

UF2 = UnionFind(n)
for _ in range(l):
    p,q = [int(i)-1 for i in input().split()]
    UF2.merge(p,q)

a = dict()
for i in range(n):
    r1,r2 = UF1.root(i), UF2.root(i)
    if (r1,r2) not in a:
        a[(r1,r2)] = 1
    else:
        a[(r1,r2)] += 1

print(*[a[(UF1.root(i), UF2.root(i))] for i in range(n)])

Solution (Python):
from collections import defaultdict as dd
def find(u,x):
    if u[x]<0:
        return x
    u[x] = find(u,u[x])
    return u[x]

def unite(u,a,b):
    a = find(u,a)
    b = find(u,b)
    if a == b:
        return False
    if u[b] < u[a]:
        a,b = b,a
    u[a] += u[b]
    u[b] = a
    return True
n,k,l = map(int, input().split())
ufr = [-1]*(n+1)
uft = [-1]*(n+1)
for _ in range(k):
    a,b = map(int, input().split())
    unite(ufr,a,b)
for _ in range(l):
    a,b = map(int, input().split())
    unite(uft,a,b)
tot = dd(int)
for i in range(1,n+1):
  tot[(find(ufr,i),find(uft,i))] += 1
print(" ".join([str(tot[(find(ufr,i),find(uft,i))]) for i in range(1,n+1)]))

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

sys.setrecursionlimit(10 ** 7)

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

road = [li_() for _ in range(k)]
rail = [li_() for _ in range(l)]

uf_road = UnionFind(n)
uf_rail = UnionFind(n)

for pi, qi in road:
    uf_road.unite(pi, qi)

for ri, si in rail:
    uf_rail.unite(ri, si)

for i in range(n):
    uf_road.find(i)
    uf_rail.find(i)

dic = defaultdict(int)

for road_par, rail_par in zip(uf_road.par, uf_rail.par):
    dic[(road_par, rail_par)] += 1

ans = []
for i in range(n):
    ans.append(dic[(uf_road.par[i], uf_rail.par[i])])

print(*ans)

Solution (Python):
from collections import defaultdict

class UnionFind:
    def __init__(self, N):
        
        
        self.vertices = [-1 for _ in range(N)]
        self.rank = [0] * N
        
    def find(self, v):
        if self.vertices[v] < 0: 
            return v
        else:
            
            self.vertices[v] = self.find(self.vertices[v])
            return self.vertices[v]
        
    def union(self, u, v):
        s1 = self.find(u) 
        s2 = self.find(v) 
        
        if s1 == s2: 
            return False
        
        if self.rank[s1] > self.rank[s2]: 
            self.vertices[s1] += self.vertices[s2] 
            self.vertices[s2] = s1
        else: 
            self.vertices[s2] += self.vertices[s1] 
            self.vertices[s1] = s2
            if self.rank[s1] == self.rank[s2]:
                self.rank[s2] += 1
        return True
        
    def is_connected(self, u, v):
        return self.find(u) == self.find(v)
    
    def size(self, v):
        return -self.vertices[self.find(v)]

N, K, L = map(int, input().split())
road = UnionFind(N)
rail = UnionFind(N)
for _ in range(K):
    p, q = map(int, input().split())
    road.union(p-1, q-1)
for _ in range(L):
    r, s = map(int, input().split())
    rail.union(r-1, s-1)
comp = defaultdict(int)
tpls = []
for i in range(N):
    t = (road.find(i), rail.find(i))
    comp[t] += 1
    tpls.append(t)
print(*[comp[t] for t in tpls])

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

e_list1 = [[] for i in range(N)]
e_list2 = [[] for i in range(N)]

for i in range(K):
    p,q = list(map(int,input().split()))
    e_list1[p-1].append(q-1)
    e_list1[q-1].append(p-1)

for i in range(L):
    p,q = list(map(int,input().split()))
    e_list2[p-1].append(q-1)
    e_list2[q-1].append(p-1)


from collections import deque

def BFS(vi,color,color_list,e_list):
    Q = deque([vi])
    color_list[vi]=color
    while len(Q)>0:
        v = Q.pop()
        for v1 in e_list[v]:
            if color_list[v1]==-1:
                color_list[v1]=color
                Q.appendleft(v1)
    return color_list



color_list = [-1 for i in range(N)]
color = 0
for i in range(N):
    if color_list[i]==-1:
        color_list = BFS(i,color,color_list,e_list1)
        color+=1
color_list2 = [-1 for i in range(N)]
color2 = 0
for i in range(N):
    if color_list2[i]==-1:
        color_list2 = BFS(i,color2,color_list2,e_list2)
        color2+=1
M = 1+max(color_list)
color_list = [color_list[i]+M*color_list2[i] for i in range(N)]

from collections import Counter

counter = Counter(color_list)

ans = []

for i in range(N):
    ans.append(counter[color_list[i]])

print(*ans)

Solution (Python):
class Union():
  def __init__(me,N):
    me.N = N
    me.up = [-1]*N
    me.down = [ [] for i in range(N) ]
  def union(me,a,b):
    ua = me.up[a] if me.up[a]!=-1 else a
    ub = me.up[b] if me.up[b]!=-1 else b
    if (ua == ub):
      return
    if ( len(me.down[ua]) < len(me.down[ub]) ):
      ub,ua = ua,ub
    for v in me.down[ub]:
      me.up[v] = ua
    me.down[ua].extend( me.down[ub] )
    me.down[ub] = []
    me.up[ub] = ua
    me.down[ua].append( ub )

N,K,L = [ int(it) for it in input().split() ]
uk = Union(N)
for a,b in [ [int(it)-1 for it in input().split()] for i in range(K) ]:
  uk.union(a,b)

ul = Union(N)
for a,b in [ [int(it)-1 for it in input().split()] for i in range(L) ]:
  ul.union(a,b)

pr = [0]*N
for i in range(N):
  ua = uk.up[i] if uk.up[i]!=-1 else i
  ub = ul.up[i] if ul.up[i]!=-1 else i
  pr[i] = (ua*N+ub,i)
pr.sort(key = lambda x:x[0])

li = [0]*N
de = pr[0][0]
s = [pr[0][1]]
for i in range(1,N):
  if (de!=pr[i][0]):
    for v in s:
      li[v] = len(s)
    s=[pr[i][1]]
    de = pr[i][0]
  else:
    s.append(pr[i][1])
for v in s:
  li[v] = len(s)

print ( " ".join( [ str(it) for it in li ]) )

Solution (Python):
N,K,L=map(int,input().split())
def search(i,root):
    if root[i]>=0:
        root[i]=search(root[i],root)
        return root[i]
    return i
def UF(N,M):
    root=[-1]*N
    for i in range(M):
        u,v=map(int,input().split())
        u-=1
        v-=1
        ru=search(u,root)
        rv=search(v,root)
        if ru==rv:
            continue
        elif root[ru]<=root[rv]:
            root[rv]+=root[ru]
            root[ru]=rv
        else:
            root[ru]+=root[rv]
            root[rv]=ru
    return [search(i,root) for i in range(N)]
road=UF(N,K)
metro=UF(N,L)
from collections import defaultdict
cnt=defaultdict(int)
ROOT=[(i,j) for i,j in zip(road,metro)]
for r in ROOT:
    cnt[r]+=1
for i in range(N):
    print(cnt[ROOT[i]])