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 Counter


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

def root(x):
    while p[x] >= 0:
        x = p[x]
    return x

def unite(x, y):
    x, y = root(x), root(y)
    if x == y:
        return
    if x > y:
        x, y = y, x
    p[x] += p[y]
    p[y] = x

def g(x):
    global p
    p = [-1]*n
    for _ in range(x):
        a, b = map(int, input().split())
        unite(a-1, b-1)
    return [root(i) for i in range(n)]

z = [*zip(g(k), g(l))]
count = Counter(z)
print(*[count[t] for t in z])

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
N,K,L=map(int,input().split())
sys.setrecursionlimit(300000)
class uf:
    def __init__(self,n):
        self.n=n
        self.l=[-1]*n
    def ro(self,n):         
        if self.l[n]<0:
            return n
        r=self.ro(self.l[n])
        self.l[n]=r
        return r
    def me(self,a,b):       
        ra=self.ro(a-1)
        rb=self.ro(b-1)
        if self.l[ra]>self.l[rb]:
            ra,rb=rb,ra
        if ra!=rb:
            self.l[ra]+=self.l[rb]
            self.l[rb]=ra
    def size(self,n):
        return -self.l[self.ro(n)]
    def sa(self,a,b):       
        return self.ro(a)==self.ro(b)
    def rl(self):           
        return [i for i,v in enumerate(self.l) if v<0]
    
    def len(self):          
        return len(self.rl())
    def ul(self):
        d={n:i for i,n in enumerate(self.rl())}
        m=[[]for i in range(self.len())]
        for i in range(self.n):
            m[d[self.ro(i)]].append(i)
        return m
    def __str__(self):
        return f"{self.ul()}"
    def __setitem__(self,i,v):
        self.l[i]=v
up=uf(N)
for i in range(K):
    up.me(*map(int,input().split()))
ur=uf(N)
for i in range(L):
    ur.me(*map(int,input().split()))
l=[0]*N
from collections import defaultdict
for i in up.ul():
    d = defaultdict(int)
    for j in i:
        d[ur.ro(j)]+=1
    for j in i:
        l[j]=d[ur.ro(j)]
print(*l)

Solution (Python):
from collections import Counter


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

def root(x):
    while p[x] >= 0:
        x = p[x]
    return x

def unite(x, y):
    x, y = root(x), root(y)
    if x == y:
        return
    if x > y:
        x, y = y, x
    p[x] += p[y]
    p[y] = x

def g(x):
    global p
    p = [-1]*n
    for _ in range(x):
        a, b = map(int, input().split())
        unite(a-1, b-1)
    return [root(i) for i in range(n)]

z = [*zip(g(k), g(l))]
count = Counter(z)
print(*[count[t] for t in z])

Solution (Python):
from bisect import bisect_left, bisect_right


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

    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 x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

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

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


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

uf1 = UnionFind(N)
uf2 = UnionFind(N)

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

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

uf_pair = sorted([(uf1.find(i), uf2.find(i)) for i in range(N)])

ans = []
for i in range(N):
    key = (uf1.find(i), uf2.find(i))
    ans.append(bisect_right(uf_pair, key) - bisect_left(uf_pair, key))

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

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

def get_root(par, node):
  if par[node] == node:
    return node
  root = get_root(par, par[node])
  par[node] = root
  return root

def union(par, rank, a, b):
  root_a, root_b = get_root(par, a), get_root(par, b)
  if root_a == root_b:
    return
  rank_a, rank_b = rank[root_a], rank[root_b]
  if rank_a < rank_b:
    par[root_a] = root_b
  else:
    par[root_b] = root_a
    if rank_a == rank_b:
      rank[root_a] += 1

par1 = [i for i in range(N)]
rank1 = [1] * N
for _ in range(K):
    a, b = map(int, input().split())
    union(par1, rank1, a-1, b-1)

par2 = [i for i in range(N)]
rank2 = [1] * N
for _ in range(L):
    a, b = map(int, input().split())
    union(par2, rank2, a-1, b-1)

ct = Counter()
for i in range(N):
    a = get_root(par1, i)
    b = get_root(par2, i)
    ct[(a, b)] += 1

print(' '.join([str(ct[(par1[i], par2[i])]) for i in range(N)]))

Solution (Python):
from collections import Counter

class Unionfind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * (n+1)
        
    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 = Unionfind(N)
uf1 = Unionfind(N)

for _ in range(K):
    p, q = map(int, input().split())
    uf.union(p-1, q-1)
    
for _ in range(L):
    r, s = map(int, input().split())
    uf1.union(r-1, s-1)
    
pairs = [(uf.find(i), uf1.find(i)) for i in range(N)]

    
c = Counter(pairs)

ans = [c[pairs[i]] for i in range(N)]

print(*ans)

Solution (Python):
n,k,l=map(int,input().split())
class UnionFind:
    
    
    __slots__ = ["_size", "_first_idx", "_parents"]
    def __init__(self, size: int, first_index: int = 0) -> None:
        self._size = size
        self._first_idx = first_index
        self._parents = [-1] * (size + first_index)
    def find(self, x: int) -> int:
        if self._parents[x] < 0:
            return x
        news=[]
        p=self._parents
        y=p[x]
        while y>=0:
            news.append(x);x,y=y,p[y]
        if len(news)!=1:
            for P in news:p[P]=x
        return x

    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)
    def unite(self, x: int, y: int) -> bool:
        x, y = self.find(x), self.find(y)
        if x == y:
            return False
        if self._parents[x] > self._parents[y]:
            x, y = y, x
        self._parents[x] += self._parents[y]
        self._parents[y] = x
        return True
    def size(self, x: int) -> int:
        return -self._parents[self.find(x)]
    def group_count(self) ->int:
        return sum(1 for i in  self._parents if i<0)-self._first_idx
    def connected(self) ->bool:
        return self._parents[self.find(self._first_idx)]==-self._size
road=UnionFind(1,n)
rail=UnionFind(1,n)

for i in range(k):
    road.unite(*map(int,input().split()))
for i in range(l):
    rail.unite(*map(int,input().split()))
from collections import defaultdict
d=defaultdict(int)

for i in range(1,n+1):
    ap,op=rail.find(i),road.find(i)
    d[ap*(n+1)+op]+=1
print(*[d[road.find(i)+rail.find(i)*(n+1)]for i in range(1,n+1)])

Solution (Python):
import sys

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 i in range(K):
    p,q = map(int,input().split())
    p -= 1
    q -= 1
    uf_road.union(p,q)

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

pair_list = []
for i in range(N):
    pair_list.append((uf_road.find(i), uf_train.find(i), i))

pair_list.sort()
ans = [0] * N

pair = (pair_list[0][0], pair_list[0][1])
countup_list = [pair_list[0][2]]
for i in range(1,N):
    if pair == (pair_list[i][0], pair_list[i][1]):
        countup_list.append(pair_list[i][2])
    else:
        for c in countup_list:
            ans[c] += len(countup_list)
        pair = (pair_list[i][0], pair_list[i][1])
        countup_list = [pair_list[i][2]]

for c in countup_list:
    ans[c] += len(countup_list)
    
for i in range(N):
    print(ans[i], end=" ")

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

par = [i for i in range(N)]

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

def unite(x, y, P):
    root_x = find(x, P)
    root_y = find(y, P)
    if root_y > root_x:
        P[root_x] = root_y
    else:
        P[root_y] = root_x

par2 = [i for i in range(N)]

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

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


r=[]
for i in range(N):
    r.append((find(i,par), find(i, par2)))

import collections
count = collections.Counter(r)


for i in range(N):
  ans = count[r[i]]
  if i == N-1:
    print(ans)
  else:
    print(ans, end=' ')

Solution (Python):
from collections import Counter

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

def root(c,x):
  if x==c[x]:
    return x
  else:
    return root(c,c[x])

def union(c,x,y):
  rx=root(c,x)
  ry=root(c,y)
  if rx>ry:
    c[rx]=ry
  else:
    c[ry]=rx

for i in range(k):
  a,b=map(int,input().split())
  union(city1,a-1,b-1)
for i in range(l):
  a,b=map(int,input().split())
  union(city2,a-1,b-1)
r=[]
for i in range(n):
  r.append((root(city1,i),root(city2,i)))
c=Counter(r)
for i in range(n):
  ans=c[r[i]]
  if i==n-1:
    print(ans)
  else:
    print(ans,end=' ')

Solution (Python):
from collections import Counter

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

def root(c,x):
  if x==c[x]:
    return x
  else:
    c[x]=root(c,c[x])
    return c[x]

def union(c,x,y):
  rx=root(c,x)
  ry=root(c,y)
  if rx>ry:
    c[rx]=ry
  else:
    c[ry]=rx

for i in range(k):
  a,b=map(int,input().split())
  union(city1,a-1,b-1)
for i in range(l):
  a,b=map(int,input().split())
  union(city2,a-1,b-1)
r=[]
for i in range(n):
  r.append((root(city1,i),root(city2,i)))
c=Counter(r)
for i in range(n):
  ans=c[r[i]]
  if i==n-1:
    print(ans)
  else:
    print(ans,end=' ')

Solution (Python):

class Uf:
	def __init__(self, N):
		self.p = list(range(N))
		self.rank = [0] * N
		self.size = [1] * N
	
	def root(self, x):
		if self.p[x] != x:
			self.p[x] = self.root(self.p[x])

		return self.p[x]
	
	def same(self, x, y):
		return self.root(x) == self.root(y)
	
	def unite(self, x, y):
		
		u = self.root(x)
		v = self.root(y)

		if u == v: return

		
		if self.rank[u] < self.rank[v]:
			self.p[u] = v
			self.size[v] += self.size[u]
			self.size[u] = 0
		else:
			self.p[v] = u
			self.size[u] += self.size[v]
			self.size[v] = 0
			
			if self.rank[u] == self.rank[v]:
				self.rank[u] += 1
	
	def count(self, x):
		return self.size[self.root(x)]

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

for i in range(K):
	p, q = map(int, input().split())
	p-=1
	q-=1
	uf_load.unite(p, q)
for _ in range(L):
	r, s = map(int, input().split())
	r-=1
	s-=1
	uf_rail.unite(r, s)

union_sets = [(uf_load.root(i), uf_rail.root(i)) for i in range(N)]
counts=Counter(union_sets)
ans = [counts[union_set] for union_set in union_sets]
print(*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 = list(map(int,input().split()))
Network1 = UnionFind(N)  
Network2 = UnionFind(N)  

for i in range(K):
    p,q = list(map(int,input().split()))
    Network1.union(p-1,q-1)  
for i in range(L):
    r,s = list(map(int,input().split()))
    Network2.union(r-1,s-1)  

dam=[0]*N  
D = {}
for i in range(N):   
    X = Network1.find(i)  
    Y = Network2.find(i)  
    dam[i] = str(X) + "_" + str(Y)  
    D[str(X) + "_" + str(Y)] = D.get(str(X) + "_" + str(Y), 0) + 1 
    

out=[]
for i in range(N):
    out.append(D[dam[i]])  

print(*out)

Solution (Python):
from collections import defaultdict

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



root_road = [-1] * N
root_train = [-1] * N


def find_road(x):
    if root_road[x] < 0:
        return x

    root_road[x] = find_road(root_road[x])
    return root_road[x]


def union_road(x, y):
    x = find_road(x)
    y = find_road(y)
    if x == y:
        return

    root_road[x] += root_road[y]
    root_road[y] = x


def same_road(x, y):
    return find_road(x) == find_road(y)


def find_train(x):
    if root_train[x] < 0:
        return x

    root_train[x] = find_train(root_train[x])
    return root_train[x]


def union_train(x, y):
    x = find_train(x)
    y = find_train(y)
    if x == y:
        return

    root_train[x] += root_train[y]
    root_train[y] = x


def same_train(x, y):
    return find_train(x) == find_train(y)


dc = defaultdict(list)
dt = defaultdict(list)
for _ in range(K):
    p, q = map(int, input().split())
    p -= 1
    q -= 1
    dc[p].append(q)
    dc[q].append(p)
    union_road(p, q)

for _ in range(L):
    r, s = map(int, input().split())
    r -= 1
    s -= 1
    dt[r].append(s)
    dt[s].append(r)
    union_train(r, s)


dic = {}
for i in range(N):
    if (find_road(i), find_train(i)) not in dic:
        dic[(find_road(i), find_train(i))] = 1
        continue
    else:
        dic[(find_road(i), find_train(i))] += 1

ans = []
for i in range(N):
    ans.append(dic[(find_road(i), find_train(i))])
print(*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 = list(map(int,input().split()))
Network1 = UnionFind(N)
Network2 = UnionFind(N)

for i in range(K):
    p,q = list(map(int,input().split()))
    Network1.union(p-1,q-1)
for i in range(L):
    r,s = list(map(int,input().split()))
    Network2.union(r-1,s-1)

dam=[0]*N
D = {}
for i in range(N):
    X = Network1.find(i)
    Y = Network2.find(i)
    dam[i] = str(X) + "_" + str(Y)
    D[str(X) + "_" + str(Y)] = D.get(str(X) + "_" + str(Y), 0) + 1 
out=[]
for i in range(N):
    out.append(D[dam[i]])

print(*out)

Solution (Python):
from collections import *;M=lambda:map(int,input().split());r=range;n,k,l=M()
def f(m):
 *a,=r(n)
 def g(i):
  if a[i]==i:return i
  a[i]=g(a[i]);return a[i]
 for _ in r(m):p,q=M();a[g(q-1)]=g(p-1)
 return [g(i) for i in r(n)]
z=[*zip(f(k),f(l))];c=Counter(z);print(*(c[x]for x in z))

Solution (Python):
class UnionFind:
    def __init__(self, N):
        self.N = N

        
        
        self.parent = [-1] * N

    def root(self, i):
        if self.parent[i] < 0:
            return i

        r = self.root(self.parent[i])
        self.parent[i] = r
        return r

    def unite(self, i, j):
        i = self.root(i)
        j = self.root(j)

        if i == j:
            return

        if i > j:
            i, j = j, i

        self.parent[i] += self.parent[j]
        self.parent[j] = i
        

    def same(self, i, j):
        return self.root(i) == self.root(j)

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

    def roots(self):
        return [self.root(i) for i in range(self.N)]

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

road = UnionFind(N)
rail = UnionFind(N)

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

for _ in range(L):
    r, s = map(int, input().split())
    r += -1
    s += -1
    rail.unite(r, s)

pair = {}
for i,j in zip(road.roots(), rail.roots()):
    t = (i, j)

    if t in pair:
        pair[t] += 1
    else:
        pair[t] = 1

ans = ' '.join([str(pair[(i, j)]) for i,j in zip(road.roots(), rail.roots())])
print(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())

def main():
    n, k, l = map(int, input().split())
    p = [list(map(int, input().split())) for _ in range(k)]
    r = [list(map(int, input().split())) for _ in range(l)]
    uf1 = UnionFind(n)
    for a, b in p:
        uf1.union(a-1, b-1)
    uf2 = UnionFind(n)
    for a, b in r:
        uf2.union(a-1, b-1)
    dic = {}
    for i in range(n):
        rt1, rt2 = uf1.find(i), uf2.find(i)
        if (rt1, rt2) in dic:
            dic[(rt1, rt2)] += 1
        else:
            dic[(rt1, rt2)] = 1
    for i in range(n):
        rt1, rt2 = uf1.find(i), uf2.find(i)
        print(dic[(rt1, rt2)], end=" ")

if __name__ == "__main__":
    main()

Solution (Python):
import math
import sys
import os
from operator import mul
from collections import Counter

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")

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 = LI()
pq = [LI() for _ in range(K)]
rs = [LI() for _ in range(L)]

road = UnionFind(N)
for r in pq:
    f = r[0]-1
    t = r[1]-1
    road.union(f,t)

rail = UnionFind(N)
for r in rs:
    f = r[0]-1
    t = r[1]-1
    rail.union(f,t)












union_sets=[(road.find(i),rail.find(i)) for i in range(N)]


counts=Counter(union_sets)

ans=[counts[union_set] for union_set in union_sets]

print(*ans)

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


def grouping(adj):
    "0-indexed の無向グラフを連結成分に分解する。"
    n = len(adj)
    ret = [-1] * n
    g = 0
    for v in range(n):
        if ret[v] == -1:
            ret[v] = g
            stack = [v]
            while stack:
                v = stack.pop()
                for nv in adj[v]:
                    if ret[nv] == -1:
                        ret[nv] = ret[v]
                        stack.append(nv)
            g += 1
    return ret


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

pq_adj = [[] for _ in range(N)]
for _ in range(K):
    p, q = map(int, input().split())
    p -= 1
    q -= 1
    pq_adj[p].append(q)
    pq_adj[q].append(p)

rs_adj = [[] for _ in range(N)]
for _ in range(L):
    r, s = map(int, input().split())
    r -= 1
    s -= 1
    rs_adj[r].append(s)
    rs_adj[s].append(r)


group = [(g1 << 32) + g2 for g1, g2 in zip(grouping(pq_adj), grouping(rs_adj))]
c = Counter(group)
for v in range(N):
    print(c[group[v]])

Solution (Python):
import sys
from collections import defaultdict
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components

input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

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

ps = pq_and_rs[:2*K:2]
qs = pq_and_rs[1:2*K:2]
rs = pq_and_rs[2*K::2]
ss = pq_and_rs[2*K+1::2]

pq_adj = csr_matrix(([1] * (2 * K), (ps + qs, qs + ps)), shape=(N+1, N+1))
rs_adj = csr_matrix(([1] * (2 * L), (rs + ss, ss + rs)), shape=(N+1, N+1))

group = ((connected_components(pq_adj)[1].astype(np.int64) << 32) + connected_components(rs_adj)[1]).tolist()
group_to_elements = defaultdict(list)
for v, g in enumerate(group):
    group_to_elements[g].append(v)

for v in range(1, N+1):
    print(len(group_to_elements[group[v]]))

Solution (Python):
from collections import *
N, K, L = map(int,input().split())

def f(m):
    *a, = range(N)
    def g(i):
        if a[i] == i:
            return i
        a[i] = g(a[i])
        return a[i]
    for _ in range(m):
        p, q = map(int,input().split())
        a[g(q-1)] = g(p-1)
    return g

x, y = f(K), f(L)
c = Counter((x(i),y(i)) for i in range(N))
print(*((c[x(i),y(i)]) for i in range(N)))

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 = list(map(int,input().split()))
Network1 = UnionFind(N)
Network2 = UnionFind(N)

for i in range(K):
    P,Q=list(map(int,input().split()))
    Network1.union(P-1, Q-1)

for i in range(L):
    R,S=list(map(int,input().split()))
    Network2.union(R-1, S-1)

D = {}
memo = [0]*N
for i in range(N):
    X=Network1.find(i)
    Y=Network2.find(i)
    memo[i] = str(X)+"_"+str(Y)
    D[str(X)+"_"+str(Y)] = D.get(str(X)+"_"+str(Y),0)+1
out = []
for i in range(N):
    out.append(D[memo[i]])
print(*out)

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

road = [i for i in range(N)]
rail = [i for i in range(N)]

def fp(x,P): 
    if x == P[x]:
        return x
    else:
        P[x] = fp(P[x],P)
        return P[x]

for i in range(K+L):
    PL = (lambda x:road if x < K else rail)(i)
    p, q = map(lambda x:int(x)-1, input().split())
    p, q = fp(p,PL), fp(q,PL)
    PL[p] = PL[q] = min(p,q)

from collections import defaultdict as dd
Wconnected = dd(lambda:0)
for i in range(N):
    Wconnected[fp(i,road),fp(i,rail)] += 1
print(*[Wconnected[fp(i,road),fp(i,rail)] for i in range(N)])

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
    
    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())
uf_road=UnionFind(N+1)
uf_train=UnionFind(N+1)

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

for _ in range(L):
  s,t=map(int,input().split())
  uf_train.union(s,t)
  
union_sets=[(uf_road.find(i),uf_train.find(i)) for i in range(1,N+1)]
counts=Counter(union_sets)
ans=[counts[union_set] for union_set in union_sets]

print(' '.join(str(a) for a in ans))

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
    
    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())
uf_road=UnionFind(N+1)
uf_train=UnionFind(N+1)

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

for _ in range(L):
  s,t=map(int,input().split())
  uf_train.union(s,t)
  
union_sets=[(uf_road.find(i),uf_train.find(i)) for i in range(1,N+1)]
counts=Counter(union_sets)
ans=[counts[union_set] for union_set in union_sets]

print(' '.join(str(a) for a in ans))