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):
class UnionFindTree():
    def __init__(self, values=[]):
        self.__parent_of = {}
        self.__rank_of = {}
        for value in values:
            self.add(value)

    def add(self, value):
        if value in self.__parent_of:
            raise RuntimeError("Dupulicated Value Added")
        self.__parent_of[value] = None
        self.__rank_of[value] = 0

    def root(self, value):
        if self.__parent_of[value] is None:
            return value
        else:
            self.__parent_of[value] = self.root(self.__parent_of[value])
            return self.__parent_of[value]

    def unite(self, a, b):
        r1 = self.root(a)
        r2 = self.root(b)
        if r1 != r2:
            if self.__rank_of[r1] < self.__rank_of[r2]:
                self.__parent_of[r1] = r2
            else:
                self.__parent_of[r2] = r1
                if self.__rank_of[r1] == self.__rank_of[r2]:
                    self.__rank_of[r1] += 1


def main():
    N, K, L = map(int, input().split())
    uft = UnionFindTree(range(N))
    for _ in range(K):
        p, q = map(int, input().split())
        uft.unite(p-1, q-1)
    uft2 = UnionFindTree(range(N))
    for _ in range(L):
        r, s = map(int, input().split())
        uft2.unite(r-1, s-1)
    pair = [(0, 0)] * N
    cnt = {}
    for i in range(N):
        p = (uft.root(i), uft2.root(i))
        if p not in cnt:
            cnt[p] = 0
        cnt[p] += 1
        pair[i] = p
    ans = [0] * N
    for i in range(N):
        ans[i] = cnt[pair[i]]
    print(" ".join(map(str, ans)))


if __name__ == "__main__":
    main()

Solution (Python):
def root(x,d):
    if d[x]!=x:
        d[x]=root(d[x],d)
    return d[x]
def unite(x,y,h):
    x=root(x,h)
    y=root(y,h)
    if x!=y:
        h[x]=min(x,y)
        h[y]=h[x]
from collections import defaultdict
n,k,l=map(int,input().split())
a=[i for i in range(n+1)]
b=[i for i in range(n+1)]
for i in range(k):
    s,t=map(int,input().split())
    unite(s,t,a)
for i in range(l):
    s,t=map(int,input().split())
    unite(s,t,b)
d=defaultdict(int)
l=""
for i in range(1,n+1):
    d[(root(a[i],a),root(b[i],b))]+=1
for i in range(1,n+1):
    l+=str(d[(root(a[i],a),root(b[i],b))])+" "
print(l[:-1])

Solution (Python):
class UnionFind(object):
    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.find(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)
uf2 = UnionFind(n)

for i in range(k):
  x, y = map(int, input().split())
  uf1.union(x-1, y-1)
for i in range(l):
  x, y = map(int, input().split())
  uf2.union(x-1, y-1)

pair = [(uf1.find(i), uf2.find(i)) for i in range(n)]
import collections
c = collections.Counter(pair)
ans = [c[pair[i]] for i in range(n)]

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

Solution (Python):
from collections import Counter

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

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

        return self.p[x]

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

    def unite(self, x, y):
        u = self.find_root(x)
        v = self.find_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 get_size(self, x):
        return self.size[self.find_root(x)]


n, K, L = map(int, input().split())
pq = [tuple(int(x)-1 for x in input().split()) for _ in range(K)]
rs = [tuple(int(x)-1 for x in input().split()) for _ in range(L)]

uk = UnionFind(n)
for p, q in pq:
    uk.unite(p, q)

ul = UnionFind(n)
for p, q in rs:
    ul.unite(p, q)

res = [uk.find_root(i) * 1000000 +  ul.find_root(i) for i in range(n)]
c = Counter(res)
ans = [0] * n

for i in range(n):
    ans[i] = c[res[i]]

print(*ans, sep=' ')

Solution (Python):
from collections import defaultdict


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)


D = defaultdict(int)
n,k,l =  map(int, input().split())
uf = UnionFind(n)
tf = UnionFind(n)

dp =[1]*n
for i in range(k):
    x,y =map(int, input().split())
    uf.union(x-1, y-1)  
for i in range(l):
    x,y =map(int, input().split())
    tf.union(x-1, y-1)  
tf.all_find()
uf.all_find()
D = defaultdict(int)
for r, t in zip(uf.par, tf.par):
    D[(r, t)] += 1
 
ans = [D[(r, t)] for r, t in zip(uf.par, tf.par)]
print(*ans, sep=' ')

Solution (Python):
from collections import Counter
N, K, L = [int(i) for i in input().split()]
par = [i for i in range(N)]
rank = [1 for i in range(N)]

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

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        pass
    else:
        if rank[x] > rank[y]:
            par[y] = x
            rank[x] += rank[y]
        else:
            par[x] = par[y]
            rank[y] += rank[x]


def find_2(x):
    if par_2[x] == x:
        return x
    else:
        return find_2(par_2[x])

def unite_2(x, y, is_incre=True):
    x = find_2(x)
    y = find_2(y)
    if x == y:
        pass
    else:
        if rank_2[x] > rank_2[y]:
            par_2[y] = x
            if is_incre:
                rank_2[x] += rank_2[y]
        else:
            par_2[x] = par_2[y]
            if is_incre:
                rank_2[y] += rank_2[x]

def is_same(x, y):
    if find(x) == find(y):
        return True
    else:
        return False

def is_same_2(x, y):
    if find_2(x) == find_2(y):
        return True
    else:
        return False

for i in range(K):
    p, q = [int(i)-1 for i in input().split()]
    if is_same(p, q):
        continue
    else:
        unite(p, q)

rank_2 = [1 for i in range(N)]
par_2 = [i for i in range(N)]
for l in range(L):
    r, s = [int(i)-1 for i in input().split()]
    if is_same_2(r, s):
        pass
    else:
        unite_2(r, s)

par_ls = list()
for i in range(N):
    ar = find(i)
    br = find_2(i)
    par_ls.append((ar, br))
ct = Counter(par_ls)

for i in range(N):
    print(ct[par_ls[i]])

Solution (Python):
import sys
input=sys.stdin.readline
N,K,L=map(int,input().split())
road=[tuple(map(int,input().split())) for _ in range(K)]
metro=[tuple(map(int,input().split())) for _ in range(L)]
inf=float('inf')
def Find(root,x):
    if root[x]<0:
        return x
    if root[x]>=0:
        root[x]=Find(root,root[x])
        return root[x]

def UnionFind(N,branch):
    root=[-1]*(N+1)
    for a,b in branch:
        aroot=Find(root,a)
        broot=Find(root,b)
        if aroot==broot:continue
        elif root[aroot]<=root[broot]:
            root[aroot]+=root[broot]
            root[broot]=aroot
        elif root[aroot]>root[broot]:
            root[broot]+=root[aroot]
            root[aroot]=broot
    return root
r_root=UnionFind(N,road)
m_root=UnionFind(N,metro)
from collections import defaultdict
data=[]
cnt=defaultdict(int)
for i in range(1,N+1):
    ri=Find(r_root,i)
    mi=Find(m_root,i)
    data.append((ri,mi))
    cnt[(ri,mi)]+=1
ans=''
for d in data:
    ans+=str(cnt[d])+' '
print(ans[:-1])

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

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

N,K,L = map(int,input().split())
uf_road = UnionFind(N)
uf_rail = UnionFind(N)
for k in range(K):
    p,q = map(int,input().split())
    uf_road.unite(p-1,q-1)
for l in range(L):
    r,s = map(int,input().split())
    uf_rail.unite(r-1,s-1)

d = {}
for i in range(N):
    k = (uf_road.find(i),uf_rail.find(i))
    if k in d.keys():
        d[k] += 1
    else:
        d[k] = 1

ans = []
for i in range(N):
    k = (uf_road.find(i),uf_rail.find(i))
    ans.append(d[k])
print(*ans)

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

from collections import Counter

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

for i in range(k):
    x,y=map(int,input().split())
    uf1.union(x-1,y-1)

for i in range(l):
    x,y=map(int,input().split())
    uf2.union(x-1,y-1)





ctr=Counter()
for i in range(n):
    r1 = uf1.find(i)
    r2 = uf2.find(i)
    ctr[(r1,r2)]+=1

ans=[]
for i in range(n):
    r1 = uf1.find(i)
    r2 = uf2.find(i)
    ans.append(ctr[(r1,r2)])
print(*ans)

Solution (Python):
import sys

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

def unite(x,y,par,rank): 
    x = find(x,par,rank)
    y = find(y,par,rank)
    if (x != y):
        if rank[x] < rank[y]:
            par[x] = y
        else :
            par[y] = x
            if (rank[x] == rank[y]) : rank[x] += 1

def same(x,y,par,rank):
    return (find(x,par,rank) == find(y,par,rank)) 

n,k,l = map(int, sys.stdin.readline().split())

par1 = [i for i in range(n)]
par2 = [i for i in range(n)]
rank1 = [0 for i in range(n)]
rank2 = [0 for i in range(n)]

for i in range(k):
    pp,qq = map(int, sys.stdin.readline().split())
    unite(pp-1,qq-1,par1,rank1)

for i in range(l):
    rr,ss = map(int, sys.stdin.readline().split())
    unite(rr-1,ss-1,par2,rank2)

dic = {}
parlis = []
for i in range(n):
    p1 = find(i,par1,rank1)
    p2 = find(i,par2,rank2)
    parlis.append((p1,p2))
    if (p1,p2) in dic:
        dic[(p1,p2)] += 1
    else: 
        dic[(p1,p2)] = 1

ans =[]

for i in range(n):
    ans.append(dic[parlis[i]])

print(*ans)

Solution (Python):

from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007






"""
s = input()
while s:
    if s[:11] == "dreameraser":
        s = s[11:]
    elif s[:10] == "dreamerase":
        s = s[10:]
    elif s[:7] == "dreamer":
        s = s[7:]
    elif s[:6] == "eraser":
        s = s[6:]
    elif s[:5] == "dream":
        s = s[5:]
    elif s[:5] == "erase":
        s = s[5:]
    else:
        print("NO")
        quit()
print("YES")
"""


def root(x,par,rank):
    if x == par[x]:
        return x
    par[x] = root(par[x],par,rank)
    return par[x]
def unite(x,y,par,rank):
    x = root(x,par,rank)
    y = root(y,par,rank)
    if x == y:return
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1
n,k,l = LI()
par1 = [i for i in range(n)]
rank1 = [0 for i in range(n)]
par2 = [i for i in range(n)]
rank2 = [0 for i in range(n)]
for i in range(k):
    p,q = LI()
    p -= 1
    q -= 1
    unite(p,q,par1,rank1)
for i in range(l):
    p,q = LI()
    p -= 1
    q -= 1
    unite(p,q,par2,rank2)
d = {}
for i in range(n):
    k = (root(i,par1,rank1),root(i,par2,rank2))
    if k in d:
        d[k] += 1
    else:
        d[k] = 1
ans = []
for i in range(n):
    k = (root(i,par1,rank1),root(i,par2,rank2))
    ans.append(d[k])
print(*ans)

Solution (Python):

from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007






"""
s = input()
while s:
    if s[:11] == "dreameraser":
        s = s[11:]
    elif s[:10] == "dreamerase":
        s = s[10:]
    elif s[:7] == "dreamer":
        s = s[7:]
    elif s[:6] == "eraser":
        s = s[6:]
    elif s[:5] == "dream":
        s = s[5:]
    elif s[:5] == "erase":
        s = s[5:]
    else:
        print("NO")
        quit()
print("YES")
"""


def root(x,par,rank):
    if x == par[x]:
        return x
    par[x] = root(par[x],par,rank)
    return par[x]
def unite(x,y,par,rank):
    x = root(x,par,rank)
    y = root(y,par,rank)
    if x == y:return
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1
n,k,l = LI()
par1 = [i for i in range(n)]
rank1 = [0 for i in range(n)]
par2 = [i for i in range(n)]
rank2 = [0 for i in range(n)]
for i in range(k):
    p,q = LI()
    p -= 1
    q -= 1
    unite(p,q,par1,rank1)
for i in range(l):
    p,q = LI()
    p -= 1
    q -= 1
    unite(p,q,par2,rank2)
d = {}
for i in range(n):
    k = (root(i,par1,rank1),root(i,par2,rank2))
    if k in d:
        d[k] += 1
    else:
        d[k] = 1
ans = []
for i in range(n):
    k = (root(i,par1,rank1),root(i,par2,rank2))
    ans.append(d[k])
print(*ans)

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

if __name__ == "__main__":
    N,K,L = map(int,input().split())
    pq = []
    rs = []
    for i in range(K):
        pq.append(list(map(int,input().split())))
    for i in range(L):
        rs.append(list(map(int,input().split())))
    
    uf_d = UnionFind(N)
    uf_t = UnionFind(N)

    for i in pq:
        uf_d.union(i[0]-1,i[1]-1)

    for i in rs:
        uf_t.union(i[0]-1,i[1]-1)
    
    dic = {}
    
    for i in range(N):
        tmp = (uf_d._root(i),uf_t._root(i))
        
        if tmp in dic:
            dic[tmp] += 1
        else:
            dic[tmp] = 1
    
    res = []

    for i in range(N):
        tmp = (uf_d._root(i),uf_t._root(i))
        res.append(dic[tmp])
    
    print(*res)

Solution (Python):

class UnionFind(object):

  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())
    
uf_road = UnionFind(n)
uf_rail = UnionFind(n)
for i in range(k):
  tmp1,tmp2 = map(int,input().split())
  uf_road.union(tmp1-1,tmp2-1)
  
for i in range(l):
  tmp1,tmp2 = map(int,input().split())
  uf_rail.union(tmp1-1,tmp2-1)

memo = {}
for i in range(n):
  if str(uf_rail.find(i))+" "+str(uf_road.find(i)) not in memo:
    memo[str(uf_rail.find(i))+" "+str(uf_road.find(i))] = 1
  else:
    memo[str(uf_rail.find(i))+" "+str(uf_road.find(i))] += 1

for i in range(n):
  print(memo[str(uf_rail.find(i))+" "+str(uf_road.find(i))])

Solution (Python):


import sys
from collections import defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


n, k, l = LI()


class UnionFind:
    
    
    def __init__(self, size: int) -> None:
        self.nodes = [-1] * size  

    def find(self, x: int) -> int:
        if self.nodes[x] < 0:
            return x
        else:
            self.nodes[x] = self.find(self.nodes[x])
            return self.nodes[x]

    def unite(self, x: int, y: int) -> None:
        root_x, root_y = self.find(x), self.find(y)
        if root_x != root_y:
            if self.nodes[root_x] != self.nodes[root_y]:  
                
                
                if self.nodes[root_x] < self.nodes[root_y]:
                    self.nodes[root_y] = root_x
                else:
                    self.nodes[root_x] = root_y
            else:
                
                
                self.nodes[root_x] += -1
                self.nodes[root_y] = root_x


ufa = UnionFind(n)
ufb = UnionFind(n)

for _ in range(k):
    a, b = LI_()
    ufa.unite(a, b)
for _ in range(l):
    a, b = LI_()
    ufb.unite(a, b)

cnt = defaultdict(int)
keys = []
for i in range(n):
    key = (ufa.find(i), ufb.find(i))
    cnt[key] += 1
    keys.append(key)

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

Solution (Python):
class UnionFind:
    def __init__(self, n):
        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 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)
    
    
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)]

res = [1 for _ in range(N)]
    
load = UnionFind(N)
train = UnionFind(N)

for i in range(K):
    load.unite(p[i][0]-1, p[i][1]-1)
    
for i in range(L):
    train.unite(r[i][0]-1, r[i][1]-1)
    
    
dic= {}
for i in range(N):
    tmp = (load.find(i), train.find(i))
    if tmp in dic:
        dic[tmp] += 1
    else:
        dic[tmp] = 1

        
for i in range(N):
    tmp = (load.find(i), train.find(i))
    res[i] = dic[tmp]
    
result = ''
for i in range(N):
    result += str(res[i]) + ' '
    
print(result)

Solution (Python):
class UnionFind():
    n=1
    par=[0]
    rnk=[0]
    def __init__(self,size):
        self.n=size
        self.par=[0 for i in range(self.n)]
        self.rnk=[0 for i in range(self.n)]
        for i in range(self.n):
            self.par[i]=i
            self.rnk[i]=0
    def find(self,vertex1):
        if self.par[vertex1]==vertex1:
            return vertex1
        else:
            self.par[vertex1]=self.find(self.par[vertex1])
            return self.par[vertex1]
    def unite(self,vertex1,vertex2):
        vertex1=self.find(vertex1)
        vertex2=self.find(vertex2)
        if vertex1==vertex2:
            return
        if (self.rnk[vertex1]<self.rnk[vertex2]):
            self.par[vertex1]=vertex2
        else:
            self.par[vertex2]=vertex1
            if(self.rnk[vertex1]==self.rnk[vertex2]):
                self.rnk[vertex1]+=1
    def same(self,vetrex1,vertex2):
        return self.find(vetrex1)==self.find(vertex2)
N,K,L=map(int,input().split())
road=UnionFind(N)
train=UnionFind(N)
for i in range(K):
    p,q=map(int,input().split())
    road.unite(p-1,q-1)
for i in range(L):
    r,s=map(int,input().split())
    train.unite(r-1,s-1)
X=[(road.find(i),train.find(i)) for i in range(N)]
D=dict()
for i in range(N):
    if not(X[i] in D):
        D[X[i]]=0
    D[X[i]]+=1
ans=[D[X[i]] for i in range(N)]
print(" ".join([str(i) for i in ans]))

Solution (Python):
class UnionFind():
    n=1
    par=[0]
    rnk=[0]
    def __init__(self,size):
        self.n=size
        self.par=[0 for i in range(self.n)]
        self.rnk=[0 for i in range(self.n)]
        for i in range(self.n):
            self.par[i]=i
            self.rnk[i]=0
    def find(self,vertex1):
        if self.par[vertex1]==vertex1:
            return vertex1
        else:
            self.par[vertex1]=self.find(self.par[vertex1])
            return self.par[vertex1]
    def unite(self,vertex1,vertex2):
        vertex1=self.find(vertex1)
        vertex2=self.find(vertex2)
        if vertex1==vertex2:
            return
        if (self.rnk[vertex1]<self.rnk[vertex2]):
            self.par[vertex1]=vertex2
        else:
            self.par[vertex2]=vertex1
            if(self.rnk[vertex1]==self.rnk[vertex2]):
                self.rnk[vertex1]+=1
    def same(self,vetrex1,vertex2):
        return self.find(vetrex1)==self.find(vertex2)
N,K,L=map(int,input().split())
road=UnionFind(N)
train=UnionFind(N)
for i in range(K):
    p,q=map(int,input().split())
    road.unite(p-1,q-1)
for i in range(L):
    r,s=map(int,input().split())
    train.unite(r-1,s-1)
X=[(road.find(i),train.find(i)) for i in range(N)]
D=dict()
for i in range(N):
    if not(X[i] in D):
        D[X[i]]=0
    D[X[i]]+=1
ans=[D[X[i]] for i in range(N)]
print(" ".join([str(i) for i in ans]))

Solution (Python):
n,k,l=map(int,input().split())
road=[list(map(int,input().split())) for _ in range(k)]
rail=[list(map(int,input().split())) for _ in range(l)]

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

from collections import Counter
uf_road=UnionFind(n)
uf_rail=UnionFind(n)
ans=0
for i,j in road:
    uf_road.union(i-1,j-1)
for i,j in rail:
    uf_rail.union(i-1,j-1)
pairs=[None]*n
for i in range(n):
    pairs[i]=(uf_road.find(i), uf_rail.find(i))
cnt=Counter(pairs)
ans=[]
for i in range(n):
    ans.append(cnt[pairs[i]])
print(' '.join(map(str,ans)))

Solution (Python):
from collections import Counter

def dfs(r, c, g, color):
    s = [r]
    color[r] = c
    while len(s) != 0:
        u = s.pop()
        for i in range(len(g[u])):
            v = g[u][i]
            if color[v] is None:
                color[v] = c
                s.append(v)


def assignColor(n, g, color):
    color_id = 1
    for u in range(n):
        if color[u] is None:
            dfs(u, color_id, g, color)
            color_id += 1


N, K, L = [int(v) for v in input().split()]
road = [[] for i in range(N)]
train = [[] for i in range(N)]
for i in range(K):
    p, q = [int(v) - 1 for v in input().split()]
    road[p].append(q)
    road[q].append(p)
for i in range(L):
    r, s = [int(v) - 1 for v in input().split()]
    train[r].append(s)
    train[s].append(r)

road_color = [None] * N
train_color = [None] * N
assignColor(N, road, road_color)
assignColor(N, train, train_color)

color_pairs = [(c1, c2) for c1, c2 in zip(road_color, train_color)]
pairs_cnt = Counter(color_pairs)
ans = [str(pairs_cnt[p]) for p in color_pairs]

print(' '.join(ans))

Solution (Python):
from collections import defaultdict as dd

class UnionFind(object):
    def __init__(self,n):
        self.parent={i:i for i in range(1,n+1)}
        self.size={i:1 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 a==b:return
        if self.size[a]>self.size[b]:
            self.size[a]+=self.size[b]
            self.parent[b]=a
        else:
            self.size[b]+=self.size[a]
            self.parent[a]=b
    def isunited(self,a,b):
        return self.find(a)==self.find(b)

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

for _ in range(k):
    p,q=map(int,input().split())
    uft_road.unite(p,q)

for _ in range(l):
    r,s=map(int,input().split())
    uft_train.unite(r,s)

dc=dd(int)
du={}
for i in range(1,n+1):
    du[i]=(uft_road.find(i),uft_train.find(i))
    dc[du[i]]+=1

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

Solution (Python):
import sys
sys.setrecursionlimit(100000)
class UnionFind:
    def __init__(self, n):
        self.p=[i for i in range(n)]
        self.r=[0 for i in range(n)]
    
    def root(self,x):
        if self.p[x]==x:
            return x
        else:
            self.p[x] = self.root(self.p[x])
            return self.p[x]
    
    def uni(self,x,y):
        x=self.root(x)
        y=self.root(y)
        if(x==y):
            return
        if self.r[x]<self.r[y]:
            self.p[x]=y
        else:
            self.p[y]=x
            if self.r[x]==self.r[y]:
                self.r[x]+=1
    
    def same(self,x,y):
        return self.root(x)==self.root(y)

n,k,l=map(int,input().split())
uf_d=UnionFind(n)
uf_m=UnionFind(n)
for i in range(k):
    a,b=map(int,input().split())
    uf_d.uni(a-1,b-1)
for i in range(l):
    a,b=map(int,input().split())
    uf_m.uni(a-1,b-1)

dic={}
d=[]
for i in range(n):
    ky=(uf_d.root(i),uf_m.root(i))
    if ky in dic:
        dic[ky]+=1
    else:
        dic[ky]=1
    d.append(ky)
for i in range(n):
    print(dic[d[i]],end=' 'if i!=n-1 else '\n')

Solution (Python):
from collections import Counter


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

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

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

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


def solve(N, K, L, PQs, RSs):
    road_cities = UnionFind(N)
    train_cities = UnionFind(N)

    for p, q in PQs:
        road_cities.unite(p, q)
    for r, s in RSs:
        train_cities.unite(r, s)

    counts = Counter([
        (road_cities.root(i), train_cities.root(i))
        for i in range(1, N + 1)
    ])

    ans = [
        counts[(road_cities.root(i), train_cities.root(i))]
        for i in range(1, N + 1)
    ]

    return " ".join([str(c) for c in ans])


if __name__ == "__main__":
    N, K, L = map(int, input().split(" "))
    PQs = []
    RSs = []
    for _ in range(K):
        PQs.append(tuple(map(int, input().split(" "))))
    for _ in range(L):
        RSs.append(tuple(map(int, input().split(" "))))
    print(solve(N, K, L, PQs, RSs))