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):
N, K, L = map(int, input().split())

class UnionFind(object):
    def __init__(self, N):
        self.parent = [i for i in range(N)]

    def root(self, A):
        if self.parent[A] == A:
            return A
        self.parent[A] = self.root(self.parent[A]) 
        return self.parent[A]

    def connect(self, A, B):
        A = self.root(A)
        B = self.root(B)
        self.parent[A] = B
        
uni1 = UnionFind(N)
for _ in range(K):
    p, q = map(int, input().split())
    if uni1.root(p-1) != uni1.root(q-1):
        uni1.connect(p-1,q-1)

uni2 = UnionFind(N)
for _ in range(L):
    r, s = map(int, input().split())
    if uni2.root(r-1) != uni2.root(s-1):
        uni2.connect(r-1,s-1)




ans = dict()
key_list = []
for i in range(N):
    root1 = uni1.root(i)
    root2 = uni2.root(i)
    key = str(root1) + '_' + str(root2)
    key_list += [key]
    if key in ans.keys():
        ans[key] += 1
    else:
        ans[key] = 1
    
for i in range(N):
    print (ans[key_list[i]], end = ' ')
print ()













print ()

Solution (Python):
import sys
input = sys.stdin.readline
from collections import Counter
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

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

P = [None] * K
Q = [None] * K
for i in range(K):
  P[i], Q[i] = map(int,input().split())

R = [None] * L
S = [None] * L
for i in range(L):
  R[i], S[i] = map(int,input().split())


g1 = csr_matrix(([1]*K,(P,Q)),(N+1,N+1))
g2 = csr_matrix(([1]*L,(R,S)),(N+1,N+1))

_,comp1 = connected_components(g1,directed = False,return_labels = True)
_,comp2 = connected_components(g2,directed = False,return_labels = True)

comp_pair = comp1.astype('int64') * (N+1) + comp2
c = Counter(comp_pair)

answer = [c[comp_pair[i]] for i in range(1,N+1)]
print(*answer)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import Counter
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

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

PQ = [[int(x) for x in input().split()] for _ in range(K)]
RS = [[int(x) for x in input().split()] for _ in range(L)]

P,Q = zip(*PQ)
R,S = zip(*RS)

g1 = csr_matrix(([1]*K,(P,Q)),(N+1,N+1))
g2 = csr_matrix(([1]*L,(R,S)),(N+1,N+1))

_,comp1 = connected_components(g1,directed = False,return_labels = True)
_,comp2 = connected_components(g2,directed = False,return_labels = True)

comp_pair = comp1.astype('int64') * (N+1) + comp2
c = Counter(comp_pair)

answer = [c[comp_pair[i]] for i in range(1,N+1)]
print(*answer)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

debug = True


def dprint(*objects):
    if debug == True:
        print(*objects)

class UnionFind:

    def __init__(self, n):
        self.parents = [i for i in range(n)]

    def merge(self, i, j):
        rooti = self.findroot(i)
        rootj = self.findroot(j)
        self.parents[rooti] = rootj

    def issame(self, i, j):
        rooti = self.findroot(i)
        rootj = self.findroot(j)
        return rooti == rootj

    def findroot(self, i, followed_indices=None):

        if i == self.parents[i]:
            return i
        else:
            root = self.findroot(self.parents[i])
            self.parents[i] = root 
            return root
    pass

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

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

    for li in range(l):
        p, q = map(int, input().split())
        uf2.merge(p-1, q-1)

    ans = {}
    key_list = []
    for i in range(n):
        root1 = uf1.findroot(i)
        root2 = uf2.findroot(i)

        key = str(root1) + "_" + str(root2)
        key_list.append(key)

        if key in ans.keys():
            ans[key] += 1
        else:
            ans[key] = 1

    for i in range(n):
        print(ans[key_list[i]], end=' ')

solve()

Solution (Python):
import collections
import sys
input = sys.stdin.readline
n,k,l=map(int,input().split())

parD,parT=[-1]*n,[-1]*n
def findD(x):
  if parD[x]<0:
    return x
  else:
    parD[x]=findD(parD[x])
    return parD[x]
def uniteD(x,y):
  x=findD(x)
  y=findD(y)
  if x==y:
    return False
  else:
    if parD[x]>parD[y]:
      x,y=y,x
    parD[x]+=parD[y]
    parD[y]=x
    return True
def sameD(x,y):
  return findD(x)==findD(y)
def sizeD(x):
  return -parD[findD(x)]
def findT(x):
  if parT[x]<0:
    return x
  else:
    parT[x]=findT(parT[x])
    return parT[x]
def uniteT(x,y):
  x=findT(x)
  y=findT(y)
  if x==y:
    return False
  else:
    if parT[x]>parT[y]:
      x,y=y,x
    parT[x]+=parT[y]
    parT[y]=x
    return True
def sameT(x,y):
  return findT(x)==findT(y)
def sizeD(x):
  return -parT[findT(x)]


for i in range(k):
  p,q=map(int,input().split())
  uniteD(p-1,q-1)
for i in range(l):
  r,s=map(int,input().split())
  uniteT(r-1,s-1)
for i in range(n):
  findD(i)
  findT(i)
C=[]
for i in range(n):
  if parD[i]<0:
    parD[i]=i
  if parT[i]<0:
    parT[i]=i
Ans=[]
for i in range(n):
  Ans.append((parD[i],parT[i]))
ANS=collections.Counter(Ans)
for i in range(n):
  print(ANS[Ans[i]])

Solution (Python):
import collections
import sys
input = sys.stdin.readline
n,k,l=map(int,input().split())

parD,parT=[-1]*n,[-1]*n
def findD(x):
  if parD[x]<0:
    return x
  else:
    parD[x]=findD(parD[x])
    return parD[x]
def uniteD(x,y):
  x=findD(x)
  y=findD(y)
  if x==y:
    return False
  else:
    if parD[x]>parD[y]:
      x,y=y,x
    parD[x]+=parD[y]
    parD[y]=x
    return True
def sameD(x,y):
  return findD(x)==findD(y)
def sizeD(x):
  return -parD[findD(x)]
def findT(x):
  if parT[x]<0:
    return x
  else:
    parT[x]=findT(parT[x])
    return parT[x]
def uniteT(x,y):
  x=findT(x)
  y=findT(y)
  if x==y:
    return False
  else:
    if parT[x]>parT[y]:
      x,y=y,x
    parT[x]+=parT[y]
    parT[y]=x
    return True
def sameT(x,y):
  return findT(x)==findT(y)
def sizeD(x):
  return -parT[findT(x)]


for i in range(k):
  p,q=map(int,input().split())
  uniteD(p-1,q-1)
for i in range(l):
  r,s=map(int,input().split())
  uniteT(r-1,s-1)
for i in range(n):
  findD(i)
  findT(i)
C=[]
for i in range(n):
  if parD[i]<0:
    parD[i]=i
  if parT[i]<0:
    parT[i]=i
Ans=[]
for i in range(n):
  Ans.append((parD[i],parT[i]))
ANS=collections.Counter(Ans)
for i in range(n):
  print(ANS[Ans[i]])

Solution (Python):
import copy

class UnionFind:
	def __init__(self, N):
		self._parent = [i for i in range(N)]

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

	def unite(self, a, b):
		ta = self.find(a)
		tb = self.find(b)
		if(ta != tb):
			self._parent[ta] = min(ta,tb)
			self._parent[tb] = self._parent[ta]
		
			
	def check(self, a, b):
		return self.find(a) == self.find(b)
		
if __name__ == '__main__':
	N,K,L = map(int, input().split())
	uf1 = UnionFind(N)
	for _ in range(K):
		p,q = map(int, input().split())
		uf1.unite(p-1,q-1)
	uf2 = UnionFind(N)
	for _ in range(L):
		s,r = map(int, input().split())
		uf2.unite(s-1,r-1)
	from collections import defaultdict
	d = defaultdict(int)
	for i in range(N):
		d[(uf1.find(i), uf2.find(i))] += 1
	ans = []
	for i in range(N):
		ans.append( str(d[(uf1.find(i), uf2.find(i))]) )
	print(' '.join(ans))

Solution (Python):
class UF():
  def __init__(self, N):
    self._parent=[n for n in range(0, N)]
    self._size=[1] * N

  def find_root(self, 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):
    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 size(self, x):
    return self._size[self.find_root(x)]

  def samegroup(self, x, y):
    return self.find_root(x)==self.find_root(y)

  def groupnum(self):
    N=len(self._parent)
    ans=0
    for i in range(N):
      if self.find_root(i)==i:
        ans+=1
    return ans

from collections import defaultdict
n,k,l=map(int,input().split())
UF1=UF(n)
for i in range(k):
  p,q=map(int,input().split())
  UF1.unite(p-1,q-1)
UF2=UF(n)
for i in range(l):
  r,s=map(int,input().split())
  UF2.unite(r-1,s-1)
d=defaultdict(int)
for i in range(n):
  d[UF1.find_root(i),UF2.find_root(i)]+=1
ans=[]
for i in range(n):
  ans.append(str(d[UF1.find_root(i),UF2.find_root(i)]))
print(' '.join(ans))

Solution (Python):

import sys
N,K,L=map(int,raw_input().split())


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):
        """
        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 と 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):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]

ufR=UnionFind(N+1)
ufT=UnionFind(N+1)
for i in range(K):
    p,q=map(int,sys.stdin.readline().split())
    ufR.union(p,q)
for i in range(L):
    p,q=map(int,sys.stdin.readline().split())
    ufT.union(p,q)    
from collections import defaultdict
R=defaultdict(set)
T=defaultdict(set)
for i in range(1,N+1):
    R[ufR.find(i)].add(i)
    T[ufT.find(i)].add(i)

P=defaultdict(int)
for i in range(1,N+1):
    P[ufR.find(i),ufT.find(i)]+=1

for i in range(1,N+1):
    print(P[ufR.find(i),ufT.find(i)])

Solution (Python):

import sys
N,K,L=map(int,raw_input().split())


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):
        """
        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 と 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):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]

ufR=UnionFind(N+1)
ufT=UnionFind(N+1)
for i in range(K):
    p,q=map(int,sys.stdin.readline().split())
    ufR.union(p,q)
for i in range(L):
    p,q=map(int,sys.stdin.readline().split())
    ufT.union(p,q)    
from collections import defaultdict
R=defaultdict(set)
T=defaultdict(set)
for i in range(1,N+1):
    R[ufR.find(i)].add(i)
    T[ufT.find(i)].add(i)

ans=[0]*(N+1)
for i in range(1,N+1):
    if ans[i]!=0:continue
    r=R[ufR.find(i)]
    t=T[ufT.find(i)]
    if len(r)==0 or len(t)==0: continue
    s=r&t
    for c in s:
        ans[c]=str(len(s))
    r-=s
    t-=s

print(" ".join(ans[1:]))

Solution (Python):

import sys
N,K,L=map(int,raw_input().split())


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):
        """
        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 と 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):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]

ufR=UnionFind(N+1)
ufT=UnionFind(N+1)
for i in range(K):
    p,q=map(int,sys.stdin.readline().split())
    ufR.union(p,q)
for i in range(L):
    p,q=map(int,sys.stdin.readline().split())
    ufT.union(p,q)    
from collections import defaultdict
R=defaultdict(set)
T=defaultdict(set)
for i in range(1,N+1):
    R[ufR.find(i)].add(i)
    T[ufT.find(i)].add(i)

ans=[0]*(N+1)
for i in range(1,N+1):
    if ans[i]!=0:continue
    r=R[ufR.find(i)]
    t=T[ufT.find(i)]
    if len(r)==0 or len(t)==0: continue
    s=r&t
    for c in s:
        ans[c]=str(len(s))
    r-=s
    t-=s

print(" ".join(ans[1:]))

Solution (Python):

"""
D - 連結 / Connectivity
https://atcoder.jp/contests/abc049/tasks/arc065_b

"""
import sys


class DisjointSet(object):
    def __init__(self, n):
        self.rank = [0] * n
        self.p = list(range(n))
        self.size = [1] * n

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

    def unite(self, x, y):
        self.link(self.findSet(x), self.findSet(y))

    def link(self, x, y):
        if self.rank[x] > self.rank[y]:
            self.size[self.p[x]] += self.size[self.p[y]]
            self.p[y] = self.findSet(x)
        else:
            self.size[self.p[y]] += self.size[self.p[x]]
            self.p[x] = self.findSet(y)
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def findSet(self, x):
        if x != self.p[x]:
            self.p[x] = self.findSet(self.p[x])
        return self.p[x]


from collections import Counter

def solve(N, K, L, PQ, RS):
    r_d = DisjointSet(N+1)
    for p, q in PQ:
        r_d.unite(p, q)
    t_d = DisjointSet(N+1)
    for r, s in RS:
        t_d.unite(r, s)
    for i in range(1, N+1):
        r_d.findSet(i)
        t_d.findSet(i)

    connectivity = Counter()
    for i in range(1, N+1):
        connectivity[(r_d.p[i], t_d.p[i])] += 1
    return [connectivity[(r_d.p[i], t_d.p[i])] for i in range(1, N + 1)]


def main(args):
    N, K, L = map(int, input().split())
    PQ = [[int(i) for i in input().split()] for _ in range(K)]
    RS = [[int(i) for i in input().split()] for _ in range(L)]
    ans = solve(N, K, L, PQ, RS)
    print(*ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):

"""
D - 連結 / Connectivity
https://atcoder.jp/contests/abc049/tasks/arc065_b

"""
import sys


class DisjointSet(object):
    def __init__(self, n):
        self.rank = [0] * n
        self.p = list(range(n))
        self.size = [1] * n

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

    def unite(self, x, y):
        self.link(self.findSet(x), self.findSet(y))

    def link(self, x, y):
        if self.rank[x] > self.rank[y]:
            self.size[self.p[x]] += self.size[self.p[y]]
            self.p[y] = self.findSet(x)
        else:
            self.size[self.p[y]] += self.size[self.p[x]]
            self.p[x] = self.findSet(y)
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def findSet(self, x):
        if x != self.p[x]:
            self.p[x] = self.findSet(self.p[x])
        return self.p[x]


from collections import Counter

def solve(N, K, L, PQ, RS):
    r_d = DisjointSet(N+1)
    for p, q in PQ:
        r_d.unite(p, q)
    t_d = DisjointSet(N+1)
    for r, s in RS:
        t_d.unite(r, s)
    for i in range(1, N+1):
        r_d.findSet(i)
        t_d.findSet(i)

    connectivity = Counter()
    for i in range(1, N+1):
        connectivity[(r_d.p[i], t_d.p[i])] += 1
    return [connectivity[(r_d.p[i], t_d.p[i])] for i in range(1, N + 1)]


def main(args):
    N, K, L = map(int, input().split())
    PQ = [[int(i) for i in input().split()] for _ in range(K)]
    RS = [[int(i) for i in input().split()] for _ in range(L)]
    ans = solve(N, K, L, PQ, RS)
    print(*ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):

"""
D - 連結 / Connectivity
https://atcoder.jp/contests/abc049/tasks/arc065_b

"""
import sys


class DisjointSet:
    def __init__(self, n):
        self.p = list(range(n))

    def root(self, i):
        if self.p[i] == i:
            return i
        else:
            self.p[i] = self.root(self.p[i])
            return self.p[i]

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

    def unite(self, i, j):
        i = self.root(i)
        j = self.root(j)
        if j >= i:
            self.p[j] = i
        else:
            self.p[i] = j


from collections import Counter

def solve(N, K, L, PQ, RS):
    r_d = DisjointSet(N+1)
    for p, q in PQ:
        r_d.unite(p, q)
    t_d = DisjointSet(N+1)
    for r, s in RS:
        t_d.unite(r, s)
    for i in range(1, N+1):
        r_d.root(i)
        t_d.root(i)

    connectivity = Counter()
    for i in range(1, N+1):
        connectivity[(r_d.p[i], t_d.p[i])] += 1
    return [connectivity[(r_d.p[i], t_d.p[i])] for i in range(1, N + 1)]


def main(args):
    N, K, L = map(int, input().split())
    PQ = [[int(i) for i in input().split()] for _ in range(K)]
    RS = [[int(i) for i in input().split()] for _ in range(L)]
    ans = solve(N, K, L, PQ, RS)
    print(*ans)


if __name__ == '__main__':
    main(sys.argv[1:])

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

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

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

    def unite(self, u, v):
        ru = self.root(u)
        rv = self.root(v)
        if self.rank[ru] < self.rank[rv]:
            self.par[ru] = rv
        else:
            self.par[rv] = ru
            if self.rank[ru] == self.rank[rv]:
                self.rank[ru] += 1

    def same(self, u, v):
        return self.root(u) == self.root(v)


u_road = UnionFind(N)
u_train = UnionFind(N)

for i in range(K):
    p, q = map(int, input().split())
    u_road.unite(p, q)
for i in range(L):
    r, s = map(int, input().split())
    u_train.unite(r, s)

mem = [set() for _ in range(N)]
mem_dict = dict()
for i in range(N):
    a = (u_road.root(i+1), u_train.root(i+1))
    mem[i] = a
    if a in mem_dict:
        mem_dict[a] += 1
    else:
        mem_dict[a] = 1

for i in range(N):
    print(mem_dict[mem[i]], end=' ')

print()

Solution (Python):
import collections
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
 
    def root(self, i):
        if self.parent[i] == i:
            return i
        else:
            self.parent[i] = self.root(self.parent[i])
            return self.parent[i]
    
    def find(self, x, y):
        return self.root(x) == self.root(y)
 
    def union(self, i, j):
        i = self.root(i)
        j = self.root(j)
        if j >= i:
            self.parent[j] = i
        else:
            self.parent[i] = j
N, K, L = map(int, input().split())
road = UnionFind(N)
train = 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())
    train.union(r-1, s-1)
for i in range(N):
    road.root(i)
    train.root(i)
lst = []
for i in range(N):
    lst.append((road.parent[i], train.parent[i]))
c = collections.Counter(lst)
ans = []
for i in range(N):
    ans.append(c[lst[i]])
print(*ans)

Solution (Python):
import collections
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
 
    def root(self, i):
        if self.parent[i] == i:
            return i
        else:
            self.parent[i] = self.root(self.parent[i])
            return self.parent[i]
    
    def find(self, x, y):
        return self.root(x) == self.root(y)
 
    def union(self, i, j):
        i = self.root(i)
        j = self.root(j)
        if j >= i:
            self.parent[j] = i
        else:
            self.parent[i] = j
N, K, L = map(int, input().split())
road = UnionFind(N)
train = 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())
    train.union(r-1, s-1)
for i in range(N):
    road.root(i)
    train.root(i)
lst = []
for i in range(N):
    lst.append((road.parent[i], train.parent[i]))
c = collections.Counter(lst)
ans = []
for i in range(N):
    ans.append(c[lst[i]])
print(*ans)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import Counter
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

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

PQ = [[int(x) for x in input().split()] for _ in range(K)]
RS = [[int(x) for x in input().split()] for _ in range(L)]

P,Q = zip(*PQ)
R,S = zip(*RS)

g1 = csr_matrix(([1]*K,(P,Q)),(N+1,N+1))
g2 = csr_matrix(([1]*L,(R,S)),(N+1,N+1))

_,comp1 = connected_components(g1,directed = False,return_labels = True)
_,comp2 = connected_components(g2,directed = False,return_labels = True)

comp_pair = comp1.astype('int64') * (N+1) + comp2.astype('int64')
c = Counter(comp_pair)

answer = [str(c[comp_pair[i]]) for i in range(1,N+1)]
print(' '.join(answer))

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

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

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

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

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


n, k, l = map(int, input().split())
road = UnionFind(n)
for i in range(k):
    p, q = map(int, input().split())
    road.union(p, q)

rail = UnionFind(n)
for i in range(l):
    r, s = map(int, input().split())
    rail.union(r, s)

r = [(road.find(i + 1), rail.find(i + 1)) for i in range(n)]
c = Counter(r)
ans = []
for i in range(n):
    ans.append(c[r[i]])
print(' '.join(map(str, ans)))

Solution (Python):
import sys
from collections import Counter

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

    def find(self, x):
        if self.par[x] == x:
            return x
        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
        elif self.rank[x] > self.rank[y]:
            self.par[y] = x
        else:
            self.par[y] = x
            self.rank[x] += 1

sys.setrecursionlimit(10 ** 5 + 1)

n, k, l = map(int, input().split())
Ur = UnionFind(n)
for i in range(k):
    p, q = map(int, input().split())
    Ur.union(p, q)

Ut = UnionFind(n)
for i in range(l):
    r, s = map(int, input().split())
    Ut.union(r, s)

x = [(Ur.find(i + 1), Ut.find(i + 1)) for i in range(n)]
c = Counter(x)
ans = []
for i in range(n):
    ans.append(c[x[i]])
print(' '.join([str(a) for a in 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())
uf_road = UnionFind(N)
uf_rail = UnionFind(N)
for _ in range(K):
    p, q = map(int, input().split())
    uf_road.union(p-1, q-1)
for _ in range(L):
    r, s = map(int, input().split())
    uf_rail.union(r-1, s-1)
    
d = defaultdict(int)
comp = [(uf_road.find(i), uf_rail.find(i)) for i in range(N)]
for c in comp:
    d[c] += 1
    
print(*[d[c] for c in comp], sep=' ')

Solution (Python):
import collections as cl

n,m0,m1 = map(int,input().split())

c0 = list(range(n+1))
c1 = c0[:]
a0 = []
a1 = []
for i in range(n+1):
  a0.append([i])
  a1.append([i])

for i in range(m0):
  p,q = map(int,input().split())
  s = c0[p]
  t = c0[q]
  if s == t:
    continue
  if len(a0[s]) < len(a0[t]):
    p,q = q,p
    s,t = t,s
  for x in a0[t]:
    c0[x] = s
  a0[s] += a0[t]
  a0[t] = []
  
for i in range(m1):
  p,q = map(int,input().split())
  s = c1[p]
  t = c1[q]
  if s == t:
    continue
  if len(a1[s]) < len(a1[t]):
    p,q = q,p
    s,t = t,s
  for x in a1[t]:
    c1[x] = s
  a1[s] += a1[t]
  a1[t] = []
  
c = [c0[i]*n+c1[i] for i in range(n+1)]
p = cl.Counter(c)



ans = [str(p[c[i]]) for i in range(1,n+1)]
print(" ".join(ans))

Solution (Python):
from collections import deque, defaultdict

def read_input():
    n, k, l = map(int, input().split())
    roads = []
    for i in range(k):
        p, q = map(int, input().split())
        roads.append((p, q))

    rails = []
    for j in range(l):
        r, s = map(int, input().split())
        rails.append((r, s))

    return n, k, l, roads, rails


def set_ids(nodes, paths):
    edge_table = {n: [] for n in nodes}

    for p in paths:
        edge_table[p[0]].append(p[1])
        edge_table[p[1]].append(p[0])

    ids = [-1] * (len(nodes) + 1)
    q = deque()
    start = 1
    group = 1
    while True:
        
        while ids[start] != -1:
            start += 1
            if start > len(nodes):
                return ids

        q.appendleft(start)
        while len(q) > 0:
            curr = q.popleft()
            ids[curr] = group

            for node in edge_table[curr]:
                if ids[node] == -1:
                    q.appendleft(node)
        group += 1


def submit():
    n, k, l, roads, rails = read_input()
    nodes = list(range(1, n + 1))

    road_ids = set_ids(nodes, roads)
    rail_ids = set_ids(nodes, rails)

    count = defaultdict(int)
    for node in nodes:
        count[(road_ids[node], rail_ids[node])] += 1

    print(' '.join([str(count[(road_ids[node], rail_ids[node])]) for node in nodes]))


if __name__ == '__main__':
    submit()

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


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

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
            self.size[x] = 0
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

    
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)


UF_road = UnionFind(N)
UF_train = UnionFind(N)
for k in range(K):
    p, q = map(int, input().split())
    p, q = p - 1, q - 1
    UF_road.union(p, q)
for l in range(L):
    r, s = map(int, input().split())
    r, s = r - 1, s - 1
    UF_train.union(r, s)
UF_road.all_find()
UF_train.all_find()


Count = Counter([(pr, pt) for pr, pt in zip(UF_road.par, UF_train.par)])
ans = []
for i in range(N):
    ans.append(Count[(UF_road.par[i], UF_train.par[i])])
print(*ans, sep=' ')