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 = [int(_) for _ in input().split()]


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

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

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

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


Road = UFT()
for _ in range(K):
    p, q = [int(_) for _ in input().split()]
    Road.unite(p, q)
Railway = UFT()
for _ in range(L):
    r, s = [int(_) for _ in input().split()]
    Railway.unite(r, s)
memo = {}
for i in range(1, N + 1):
    memo[Road.find(i) + N * Railway.find(i)] = memo.get(
        (Road.find(i) + N * Railway.find(i)), 0) + 1
print(' '.join(str(memo[Road.find(i) + N * Railway.find(i)])
               for i in range(1, N + 1)))

Solution (Python):
N, K, L = [int(_) for _ in input().split()]


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

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

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

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


Road = UFT()
for _ in range(K):
    p, q = [int(_) for _ in input().split()]
    Road.unite(p, q)
Railway = UFT()
for _ in range(L):
    r, s = [int(_) for _ in input().split()]
    Railway.unite(r, s)
memo = {}
for i in range(1, N + 1):
    memo[Road.find(i), Railway.find(i)] = memo.get(
        (Road.find(i), Railway.find(i)), 0) + 1
print(' '.join(str(memo[Road.find(i), Railway.find(i)])
               for i in range(1, N + 1)))

Solution (Python):
N, K, L = [int(_) for _ in input().split()]


class UFT():
    def __init__(self):
        self.par = {}
        self.rank = {}
        for i in range(1, N + 1):
            self.par[i] = i
            self.rank[i] = 0

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

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


Road = UFT()
for _ in range(K):
    p, q = [int(_) for _ in input().split()]
    Road.unite(p, q)
Railway = UFT()
for _ in range(L):
    r, s = [int(_) for _ in input().split()]
    Railway.unite(r, s)
memo = {}
for i in range(1, N + 1):
    memo[Road.find(i), Railway.find(i)] = memo.get(
        (Road.find(i), Railway.find(i)), 0) + 1
print(' '.join(str(memo[Road.find(i), Railway.find(i)])
               for i in range(1, N + 1)))

Solution (Python):
class UFT():
    def __init__(self):
        self.par = {}
        self.rank = {}

    def find(self, x):
        if self.par.get(x, x) == 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

        self.rank[x] = self.rank.get(x, 0)
        self.rank[y] = self.rank.get(y, 0)

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

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

N, K, L = [int(_) for _ in input().split()]

Road = UFT()
for _ in range(K):
    p, q = [int(_) for _ in input().split()]
    Road.unite(p, q)
Railway = UFT()
for _ in range(L):
    r, s = [int(_) for _ in input().split()]
    Railway.unite(r, s)
memo = {}
for i in range(1, N + 1):
    memo[Road.find(i), Railway.find(i)] = memo.get((Road.find(i), Railway.find(i)), 0) + 1
print(' '.join(str(memo[Road.find(i), Railway.find(i)]) for i in range(1, N + 1)))

Solution (Python):
from collections import defaultdict
class Unionfind:
  def __init__(self,n):
    self.Tree=[i for i in range(n)]
    self.rank=[0]*n

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

  def unite(self,x,y):
    s1=self.find(x)
    s2=self.find(y)
    if s1==s2:
      pass
    else:
      if self.rank[s1]>self.rank[s2]:
        self.Tree[s2]=s1
      elif self.rank[s1]<self.rank[s2]:
        self.Tree[s1]=s2
      else:
        self.Tree[s2]=s1
        self.rank[s1]+=1
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.unite(p-1,q-1)
for j in range(L):
  r,s=map(int,input().split())
  uf2.unite(r-1,s-1)
d=defaultdict(int)
ans=[0]*N
for i in range(N):
  d[(uf1.find(i),uf2.find(i))]+=1
for i in range(N):
  ans[i]=d[(uf1.find(i),uf2.find(i))]
print(" ".join(map(str,ans)))

Solution (Python):
from collections import defaultdict
class myUnionFind():
    def __init__(self,size):
        self.table = [-1 for i in range(size)]

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

    def is_same(self,x,y):
        return self.table[x]==self.table[y]

    def union(self,x,y):
        x,y = self.find(x),self.find(y)
        if x != y:
            if self.table[x] > self.table[y]:
                y,x = x,y
            self.table[x] += self.table[y]
            self.table[y] = x
        return x!=y

N,K,L = map(int,input().split())
R,T = myUnionFind(N),myUnionFind(N)
for i in range(K):
    p,q = map(int,input().split())
    R.union(p-1,q-1)
for i in range(L):
    r,s = map(int,input().split())
    T.union(r-1,s-1)
both = defaultdict(int)
for i in range(N):
    both[(R.find(i),T.find(i))] += 1
ans = [both[(R.find(i),T.find(i))] for i in range(N)]
print(*ans)

Solution (Python):
import sys

sys.setrecursionlimit(10**6)
def dps(gr,p,s,num):
    if gr[s]!=-1:
        return
    gr[s]=num
    for x in p[s]:
        dps(gr,p,x,num)

N,K,L=list(map(int,input().split()))
dic={}
road=[[] for _ in range(N)]
rail=[[] for _ in range(N)]

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

for i in range(L):
    r,s=list(map(int,input().split()))
    rail[r-1].append(s-1)
    rail[s-1].append(r-1)


roadG=[-1 for _ in range(N)]
num=0
for i in range(N):
    if roadG[i]==-1:
        dps(roadG,road,i,num)
        num+=1

railG=[-1 for _ in range(N)]
num=0
for i in range(N):
    if railG[i]==-1:
        dps(railG,rail,i,num)
        num+=1
dic={}
arr=[]
for i in range(N):
    key=(roadG[i],railG[i])
    arr.append(key)
    dic[key]=dic.setdefault(key,0)+1
print(' '.join([str(dic[x]) for x in arr]))

Solution (Python):
import sys

sys.setrecursionlimit(10**6)
def bps(gr,p,s,num):
    if gr[s]!=-1:
        return
    gr[s]=num
    for x in p[s]:
        bps(gr,p,x,num)

N,K,L=list(map(int,input().split()))
dic={}
road=[[] for _ in range(N)]
rail=[[] for _ in range(N)]

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

for i in range(L):
    r,s=list(map(int,input().split()))
    rail[r-1].append(s-1)
    rail[s-1].append(r-1)


roadG=[-1 for _ in range(N)]
num=0
for i in range(N):
    if roadG[i]==-1:
        bps(roadG,road,i,num)
        num+=1

railG=[-1 for _ in range(N)]
num=0
for i in range(N):
    if railG[i]==-1:
        bps(railG,rail,i,num)
        num+=1
dic={}
arr=[]
for i in range(N):
    key=roadG[i]*N+railG[i]
    arr.append(key)
    dic[key]=dic.setdefault(key,0)+1
print(dic[arr[0]],end='')
for x in arr[1:]:
    print(' {}'.format(dic[x]),end='')
print('')

Solution (Python):
class UnionFind:
    def __init__(self, size):
        
        
        self.table = [-1 for _ in range(size)]

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

    
    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

N,K,L = map(int,input().split())
road = UnionFind(N)
railway = UnionFind(N)
for i in range(K):
    p,q = map(int,input().split())
    road.union(p-1,q-1)
for i in range(L):
    r,s = map(int,input().split())
    railway.union(r-1,s-1)

from collections import defaultdict
d = defaultdict(lambda:0)

for i in range(N):
    p1,p2 = road.find(i),railway.find(i)
    d[(p1,p2)] += 1

ans = [str(d[(road.find(i),railway.find(i))]) for i in range(N)]
print(' '.join(ans))

Solution (Python):

class UF:
    def __init__(self, n):
        
        
        self.table = [-1] * n
    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            
            self.table[x] = self._root(self.table[x])
            return self.table[x]
    def find(self, x, y):
        return self._root(x) == self._root(y)
    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2
    def show(self):
        print(self.table)
    def data(self):
        res={}
        n=len(self.table)
        for i in range(n):
            res.update({i:[i] if self.table[i]<0 else [self.table[i]]})
        for i in range(n):
            res[res[i][0]]+=[i]
        for i in range(n):
            if len(res[i])==1:
                del res[i]
            else:
                del res[i][0]
        return list(res.values())

n,k,l=map(int,input().split())
pq=[list(map(int,input().split())) for _ in range(k)]
rs=[list(map(int,input().split())) for _ in range(l)]
auf=UF(n)
buf=UF(n)
for p,q in pq:
    auf.union(p-1,q-1)
for r,s in rs:
    buf.union(r-1,s-1)
key_list=[]
from collections import defaultdict
count=defaultdict(int)
for i in range(n):
    key=(auf._root(i),buf._root(i))
    key_list.append(key)
    count[key]+=1
ans=[0 for _ in range(n)]
for i,key in enumerate(key_list):
    ans[i]=str(count[key])
print(" ".join(ans))

Solution (Python):


import sys
def 解():
    iN,iK,iL = [int(_) for _ in input().split()]
    aD = [[int(_) for _ in sLine.split()] for sLine in sys.stdin.readlines()]

    def buildTree(a):
        
        aT = list(range(iN+1))
        for p,q in a:
            rp = getRoot(aT,p)
            rq = getRoot(aT,q)
            thisRoot = max(rp,rq,q) 
            aT[p] = thisRoot
            aT[q] = thisRoot
            aT[rp] = thisRoot 
            aT[rq] = thisRoot
        return aT
    def getRoot(a,i): 
        
        
        if a[i] == i :
            return i
    
        else :
            a[i] = getRoot(a,a[i])
            return a[i]
    
    

    aT道 = buildTree(aD[0:iK])
    aT鉄道 = buildTree(aD[iK:])
    aRet = []
    dRet = {}
    for i in range(1,iN+1):
        
        Comb = (getRoot(aT道,i), getRoot(aT鉄道,i))
        aRet.append(Comb)
        if Comb in dRet:
            dRet[Comb] += 1
        else:
            dRet[Comb] = 1
    print(" ".join([str(dRet[_]) for _ in aRet]))

解()

Solution (Python):

import sys
def 解():
    iN,iK,iL = [int(_) for _ in input().split()]
    aD = [[int(_) for _ in sLine.split()] for sLine in sys.stdin.readlines()]

    def buildTree(a):
        
        aT = list(range(iN+1))
        for p,q in a:
            rp = getRoot(aT,p)
            rq = getRoot(aT,q)
            thisRoot = max(rp,rq,q)
            aT[p] = thisRoot
            aT[q] = thisRoot
            aT[rp] = thisRoot 
            aT[rq] = thisRoot
        return aT
    def getRoot(a,i): 
        
        
        if a[i] == i :
            return i
        elif i < a[i] :
            a[i] = getRoot(a,a[i])
            return a[i]
    
    

    aT道 = buildTree(aD[0:iK])
    aT鉄道 = buildTree(aD[iK:])
    aRet = []
    dRet = {}
    for i in range(1,iN+1):
        
        Comb = (getRoot(aT道,i), getRoot(aT鉄道,i))
        aRet.append(Comb)
        if Comb in dRet:
            dRet[Comb] += 1
        else:
            dRet[Comb] = 1
    print(" ".join([str(dRet[_]) for _ in aRet]))

解()

Solution (Python):

import sys
def 解():
    iN,iK,iL = [int(_) for _ in input().split()]
    aD = [[int(_) for _ in sLine.split()] for sLine in sys.stdin.readlines()]

    def buildTree(a):
        aT = [0]*(iN+1)
        for p,q in a:
            rp = getRoot(aT,p)
            rq = getRoot(aT,q)
            thisRoot = max(rp,rq,q)
            aT[p] = thisRoot
            aT[q] = thisRoot
            aT[rp] = thisRoot 
            aT[rq] = thisRoot
        return aT
    def getRoot(a,i): 
        if a[i] == i or a[i] == 0:
            if a[i] == 0 : a[i] = i
            return i
        elif i < a[i] :
            a[i] = getRoot(a,a[i])
            return a[i]
    
    

    aT道 = buildTree(aD[0:iK])
    aT鉄道 = buildTree(aD[iK:])
    aRet = []
    dRet = {}
    for i in range(1,iN+1):
        
        Comb = (getRoot(aT道,i), getRoot(aT鉄道,i))
        aRet.append(Comb)
        if Comb in dRet:
            dRet[Comb] += 1
        else:
            dRet[Comb] = 1
    print(" ".join([str(dRet[_]) for _ in aRet]))

解()

Solution (Python):
def Parent(i, A = list):
    if i == A[i]:
        return i
    else:
        return Parent(A[i], A)

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


Road = [int(_) for _ in range(N)]
Rail = [int(_) for _ in range(N)]
for i in range(K):
    p, q = map(int, input().split())
    p, q = p-1, q-1
    pP, qP = Parent(p, Road), Parent(q, Road)
    if pP <= qP:
        Road[qP] = pP
    else:
        Road[pP] = qP
for i in range(L):
    r, s = map(int, input().split())
    r, s = r-1, s-1
    rP, sP = Parent(r, Rail), Parent(s, Rail)
    if rP <= sP:
        Rail[sP] = rP
    else:
        Rail[rP] = sP

Parents, Count = [], {}
for i in range(N):
    roadP, railP = Parent(i, Road), Parent(i, Rail)
    Parents.append((roadP, railP))
    if (roadP, railP) in Count:
        Count[(roadP, railP)] += 1
    else:
        Count[(roadP, railP)] = 1

Ans = []
for i in range(N):
    Ans.append(Count[Parents[i]])
print(" ".join(map(str, Ans)))

Solution (Python):
from collections import defaultdict
def find(x, A): 
    p = A[x]
    if p == x:
        return x
    a = find(p, A)
    A[x] = a
    return a

N, K, L = map( int, input().split())
V = [ i for i in range(N)]
W = [ i for i in range(N)]
for _ in range(K):
    p, q = map( int, input().split())
    p, q = p-1, q-1
    bp, bq = find(p,V), find(q,V)
    V[q] = bp
    V[bq] = bp

for _ in range(L):
    r, s = map( int, input().split())
    r, s = r-1, s-1
    br, bs = find(r,W), find(s,W)
    W[s] = br
    W[bs] = br

d = defaultdict(int) 
for i in range(N):
    d[(find(i,V), find(i, W))] += 1
ANS = [0]*N
for i in range(N):
    ANS[i] = d[(find(i,V), find(i, W))]

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

Solution (Python):
from collections import defaultdict
def find(x, A):
    p = A[x]
    if p == x:
        return x
    a = find(p, A)
    A[x] = a
    find(a,A)
    return a

N, K, L = map( int, input().split())
V = [ i for i in range(N)]
W = [ i for i in range(N)]
for _ in range(K):
    p, q = map( int, input().split())
    p, q = p-1, q-1
    bp, bq = find(p,V), find(q,V)
    V[q] = bp
    V[bq] = bp

for _ in range(L):
    r, s = map( int, input().split())
    r, s = r-1, s-1
    br, bs = find(r,W), find(s,W)
    W[s] = br
    W[bs] = br

d = defaultdict(int)
for i in range(N):
    d[(find(i,V), find(i, W))] += 1
ANS = [0]*N
for i in range(N):
    ANS[i] = d[(find(i,V), find(i, W))]

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

Solution (Python):
from collections import Counter

class UnionFind:
    __slots__ = ['id']
    def __init__(self, n):
        self.id = [-1] * n
    def find(self, x):
        if self.id[x] < 0:
            return x
        else:
            self.id[x] = self.find(self.id[x])
            return self.id[x]
    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.id[s1] <= self.id[s2]:
                self.id[s1] += self.id[s2]
                self.id[s2] = s1
            else:
                self.id[s2] += self.id[s1]
                self.id[s1] = s2
            return True
        return False
    def subsetall(self):
        a = []
        for i in range(len(self.id)):
            if self.id[i] < 0:
                a.append((i, -self.id[i]))
        return a

if __name__ == '__main__':
    N, K, L = map(int, input().split())

    uf_K = UnionFind(N)
    uf_L = UnionFind(N)
    for _ in [0] * K:
        p, q = map(int, input().split())
        uf_K.union(p - 1, q - 1)
    for _ in [0] * L:
        r, s = map(int, input().split())
        uf_L.union(r - 1, s - 1)

    keys, d = [], Counter()
    for i in range(N):
        key = uf_K.find(i), uf_L.find(i)
        keys.append(key)
        d[key] += 1

    print(*(d[key] for key in keys))

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

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


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

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

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

d = dict()
for i in range(n):
    f1 = uf1.find(i)
    f2 = uf2.find(i)
    t = (f1, f2)
    d[t] = d.get(t, 0) + 1

ans = []
for i in range(n):
    f1 = uf1.find(i)
    f2 = uf2.find(i)
    t = (f1, f2)
    ans.append(d[t])

print(*ans)

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

class UnionFind(object):
    def __init__(self, N):
        self.__root = list(range(N))
    

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

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


    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if (x == y):
            return
        self.__root[x] = y
        return


N, K, L = [int(elem) for elem in fin().split(' ')]
road_list = tuple([tuple([int(elem)-1 for elem in fin().split(' ')]) for _ in range(K)])
train_list = tuple([tuple([int(elem)-1 for elem in fin().split(' ')]) for _ in range(L)])

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

for p, q in road_list:
    uf_road.unite(p, q)

for r, s in train_list:
    uf_train.unite(r, s)


key_list = []
count = defaultdict(int)
for i in range(N):
    
    key = (uf_road.root(i), uf_train.root(i))
    key_list.append(key)
    count[key] += 1

assert len(key_list) == N
answer_list = [0] * N
for i, key in enumerate(key_list):
    answer_list[i] = str(count[key])
print(' '.join(answer_list))

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

class UnionFind(object):
    def __init__(self, N):
        self.__root = list(range(N))
    

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

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


    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if (x == y):
            return
        self.__root[x] = y
        return


N, K, L = [int(elem) for elem in fin().split(' ')]
road_list = tuple([tuple([int(elem)-1 for elem in fin().split(' ')]) for _ in range(K)])
train_list = tuple([tuple([int(elem)-1 for elem in fin().split(' ')]) for _ in range(L)])

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

for p, q in road_list:
    uf_road.unite(p, q)

for r, s in train_list:
    uf_train.unite(r, s)


key_list = []
count = defaultdict(int)
for i in range(N):
    
    key = (uf_road.root(i), uf_train.root(i))
    key_list.append(key)
    count[key] += 1

assert len(key_list) == N
answer_list = [0] * N
for i, key in enumerate(key_list):
    answer_list[i] = str(count[key])
print(' '.join(answer_list))

Solution (Python):
from itertools import product
from collections import defaultdict as dd

class UFT(object):
  def __init__(self,n):
    self.parent={i:i for i in range(1,n+1)}
    self.height={i:0 for i in range(1,n+1)}
  def find(self,a):
    if self.parent[a]!=a:
      self.parent[a]=self.find(self.parent[a])
    return self.parent[a]
  def unite(self,a,b):
    a=self.find(a)
    b=self.find(b)
    if self.height[a]>self.height[b]:
      self.parent[b]=a
    else:
      if self.height[a]==self.height[b]:
        self.height[b]+=1
      self.parent[a]=b
  def isunited(self,a,b):
    return self.find(a)==self.find(b)


n,k,l=map(int,input().split())
uk=UFT(n)
ul=UFT(n)
dc=dd(int)
du={}

for _ in range(k):
  a,b=map(int,input().split())
  uk.unite(a,b)

for _ in range(l):
  a,b=map(int,input().split())
  ul.unite(a,b)
  
for i in range(1,n+1):
  du[i]=(uk.find(i),ul.find(i))
  dc[du[i]]+=1

print(*(dc[du[i]] for i in range(1,n+1)))

Solution (Python):
from collections import Counter
N,K,L = map(int,input().split())
roads = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(K)]
rails = [tuple(map(lambda x:int(x)-1,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 a,b in roads:
    if uf_road.is_same(a,b): continue
    uf_road.unite(a,b)

uf_rail = UnionFind(N)
for a,b in rails:
    if uf_rail.is_same(a,b): continue
    uf_rail.unite(a,b)

for i in range(N):
    uf_road.root(i)
    uf_rail.root(i)

ctr = Counter()
for i in range(N):
    r1 = uf_road.root(i)
    r2 = uf_rail.root(i)
    ctr[(r1,r2)] += 1

ans = []
for i in range(N):
    r1 = uf_road.root(i)
    r2 = uf_rail.root(i)
    ans.append(ctr[(r1,r2)])
print(*ans)

Solution (Python):
import sys
from collections import defaultdict
class UnionFind():
    def __init__(self,size):
        self.table = [-1 for _  in range(size)]
    def find(self,x):
        while self.table[x] >= 0:
            x = self.table[x]
        return x

    def union(self,x,y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] != self.table[s2]:
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                else:
                    self.table[s1] = s2
            else:
                self.table[s1] += -1
                self.table[s2] = s1
        return
n,k,l = map(int, sys.stdin.readline().split())
p = []
for i in range(k):
    p.append(list(map(int, input().split())))
do = [[] for i in range(n+1)]
for pi in p:  
    do[pi[0]].append(pi[1])
p = []
for i in range(l):
    p.append(list(map(int, input().split())))
te = [[] for i in range(n+1)]
for pi in p:  
    te[pi[0]].append(pi[1])
dou = UnionFind(n)
for i in range(n+1):
  a = do[i]
  for j in a:
    dou.union(i-1,j-1)
douro = [-1] * n
for i in range(n):
  douro[i] = dou.find(i)
tet = UnionFind(n)
for i in range(n+1):
  a = te[i]
  for j in a:
    tet.union(i-1,j-1)
tetu = [-1] * n
for i in range(n):
  tetu[i] = tet.find(i)
d = defaultdict(int)
for i in range(n): 
  d[(douro[i],tetu[i])] += 1
ans = []
for i in range(n):
  ans.append(d[(douro[i],tetu[i])])
print(" ".join(map(str,ans)))

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

class UnionFind():
    def __init__(self,size):
        self.table = [-1 for _  in range(size)]

    def find(self,x):
        while self.table[x] >= 0:
            x = self.table[x]
        return x

    def union(self,x,y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] != self.table[s2]:
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                else:
                    self.table[s1] = s2
            else:
                self.table[s1] += -1
                self.table[s2] = s1
        return

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

for i in range(k):
	f,t = map(int,raw_input().split()); f -= 1; t -= 1
	uf_road.union(f, t)

for i in range(l):
	f,t = map(int,raw_input().split()); f -= 1; t -= 1
	uf_rail.union(f, t)
road = [0]*n
rail = [0]*n
for i in range(n):
	road[i] = uf_road.find(i)
	rail[i] = uf_rail.find(i)

ans = {}

for i in range(n):
	key = (road[i],rail[i])
	count = ans.get(key)
	ans[key] = 1 if not count else count + 1

ret = []
for i in range(n):
	key = (road[i],rail[i])
	ret.append(str(ans.get(key)))

print ' '.join(ret)

Solution (Python):
n, k, l = map(int, input().split())
from collections import defaultdict

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

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


uf1 = UnionFind(n)
uf2 = UnionFind(n)

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


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

pair = defaultdict(int)
for i in range(n):
    a = uf1.find(i)
    b = uf2.find(i)
    pair[(a, b)] += 1

ans = []
for i in range(n):
    ans.append(pair[(uf1.find(i), uf2.find(i))])

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

Solution (Python):
n, k, l = map(int, input().split())
from collections import defaultdict

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

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


uf1 = UnionFind(n)
uf2 = UnionFind(n)

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


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

pair = defaultdict(int)
for i in range(n):
    a = uf1.find(i)
    b = uf2.find(i)
    pair[(a, b)] += 1

ans = []
for i in range(n):
    ans.append(pair[(uf1.find(i), uf2.find(i))])

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