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

Solution (Python):
from collections import defaultdict

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


def unite(x, y, parent):
    x = find(x, parent)
    y = find(y, parent)
    if x == y: return

    parent[y] = x

def solve():
    N, K, L = map(int, input().split())
    
    street = [i for i in range(N)]
    train = [i for i in range(N)]

    for _ in range(K):
        a, b = map(int, input().split())
        unite(a-1, b-1, street)

    for _ in range(L):
        a, b = map(int, input().split())
        unite(a-1, b-1, train)

    d = defaultdict(int)
    for i in range(N):
        a = find(street[i], street)
        b = find(train[i], train)
        d[(a, b)] += 1

    ans = []
    for i in range(N):
        a = find(street[i], street)
        b = find(train[i], train)
        ans.append(str(d[a, b]))

    print(' '.join(ans))

solve()

Solution (Python):
maxn = 2 * (10**5)

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

par = [[0] * (n+1) for _ in range(2)]
rank = [[0] * (n+1) for _ in range(2)]


for i in range(n+1):
    par[0][i] = i
    rank[0][i] = 0
    par[1][i] = i
    rank[1][i] = 0


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

def unite(num , x , y):
    rx = find(num,x)
    ry = find(num,y)
    
    if rx == ry:
        return
    
    if rank[num][rx] < rank[num][ry]:
        par[num][rx] = ry
    elif rank[num][rx] > rank[num][ry]:
        par[num][ry] = rx
    else:
        par[num][ry] = x
        rank[num][rx] += 1
        

for i in range(k):
    p,q = map(int, input().split())
    unite(0,p,q)
        
for i in range(l):
    r,s = map(int, input().split())
    unite(1,r,s)
    
pairs = [(find(0,i),find(1,i)) for i in range(1,n+1)]
from collections import Counter
pairc = Counter(pairs)
ans = [pairc[pair] for pair in pairs]

print(*ans)

Solution (Python):

class UnionFind():
    def __init__(self, n):
        self.n=n
        self.parents=[-1]*n 

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

    def union(self,x,y): 
        x=self.find(x)
        y=self.find(y)

        if x==y:
            return

        if self.parents[x]>self.parents[y]:
            x,y=y,x

        self.parents[x]+=self.parents[y]
        self.parents[y]=x

    def size(self,x): 
        return -self.parents[self.find(x)]

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

    def members(self,x): 
        root=self.find(x)
        return [i for i in range(self.n) if self.find(i)==root]

    def roots(self): 
        return [i for i, x in enumerate(self.parents) if x<0]

    def group_count(self): 
        return len(self.roots())

    def all_group_members(self): 
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())



def main():
    n,k,l=map(int,input().split())
    ufr=UnionFind(n)
    uft=UnionFind(n)
    for i in range(k):
        x,y=map(int,input().split())
        ufr.union(x-1,y-1)
    for i in range(l):
        x,y=map(int,input().split())
        uft.union(x-1,y-1)
    
    pairs = [(ufr.find(i), uft.find(i)) for i in range(n)]
    from collections import Counter
    pairs_counter = Counter(pairs)
    ans = [pairs_counter[pair] for pair in pairs]
    print(*ans)

if __name__=="__main__" :
    main()

Solution (Python):
from collections import defaultdict


class UnionFind:
    def __init__(self, n: int):
        self.n = n
        self.parents = [-1] * n
    
    def find(self, x: int):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x: int, y: int):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        if self.parents[y] < self.parents[x]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x: int):
        return -self.parents[self.find(x)]
    
    def same(self, x: int, y: int):
        return self.find(x) == self.find(y)
    
    def members(self, x: int):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    
    def group_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def solve():
    N, K, L = map(int, input().split())
    connect_road, connect_rail = UnionFind(N), UnionFind(N)
    for _ in range(K):
        p, q = map(lambda x: int(x) - 1, input().split())
        connect_road.union(p, q)
    for _ in range(L):
        r, s = map(lambda x: int(x) - 1, input().split())
        connect_rail.union(r, s)
    
    root = defaultdict(int)
    for i in range(N):
        root[(connect_road.find(i), connect_rail.find(i))] += 1
    for i in range(N):
        print(root[(connect_road.find(i), connect_rail.find(i))])


if __name__ == '__main__':
    solve()

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

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

pairs = [(uf1.find(i), uf2.find(i)) for i in range(N)]
from collections import Counter
pairs_counter = Counter(pairs)
ans = [pairs_counter[pair] for pair in pairs]
print(*ans)

Solution (Python):
class UnionFind:
    def __init__(self, n: int):
        self.__n = n
        self.__par = list(range(self.__n))
        self.__size = [1 for _ in range(self.__n)]

    def root(self, x: int) -> int:
        if self.__par[x] == x:
            return x
        self.__par[x] = self.root(self.__par[x])
        return self.__par[x]

    def merge(self, x: int, y: int) -> bool:
        rx, ry = self.root(x), self.root(y)
        if rx == ry: return False

        if self.__size[rx] < self.__size[ry]:
            rx, ry = ry, rx

        self.__size[rx] += self.__size[ry]
        self.__par[ry] = rx
        return True

    def check(self, x: int, y: int) -> bool:
        return self.root(x) == self.root(y)

    def size(self, x: int) -> int:
        return self.__size[self.root(x)]


from collections import defaultdict

N, K, L = map(int, input().split())
rail_uf = UnionFind(N + 1)
road_uf = UnionFind(N + 1)

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

for _ in range(L):
    r, s = map(int, input().split())
    road_uf.merge(r, s)

d = defaultdict(int)
for i in range(1, N + 1):
    tup = (rail_uf.root(i), road_uf.root(i))
    d[tup] += 1

ans = []
for i in range(1, N + 1):
    tup = (rail_uf.root(i), road_uf.root(i))
    ans.append(str(d[tup]))

print(" ".join(ans))

Solution (Python):
import sys
from collections import defaultdict
def input(): return sys.stdin.readline().rstrip()

class UnionFind:
    def __init__(self, n):
        self.parents = [-1] * (n + 1)

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def size(self, x):
        return -self.parents[self.find(x)]

def main():
    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, q)
    
    for _ in range(L):
        r, s = map(int, input().split())
        train.union(r, s)
    
    ans = []
    counter = defaultdict(int)
    for i in range(1, N + 1):
        root = (road.find(i), train.find(i))
        ans.append(root)
        counter[root] += 1
    for i in range(1, N + 1):
        root = (road.find(i), train.find(i))
        print(counter[root])

if __name__ == '__main__':
    main()

Solution (Python):

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

def union(x,y,par,rank):
  x=find(x,par)
  y=find(y,par)

  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):
  return find(x,par)==find(y,par)

n,k,l=map(int, input().split())    
apar=[]
bpar=[]
arank=[0]*n
brank=[0]*n

for i in range(n):
  apar.append(i)
  bpar.append(i)

for i in range(k):
  p,q = map(int, input().split())
  union(p-1,q-1,apar,arank)

for i in range(l):
  p,q = map(int, input().split())
  union(p-1,q-1,bpar,brank)


  
num=[]
d={}
for i in range(n):
  
  num.append(find(i,apar)+find(i,bpar)*10**6)
  
  if num[-1] in d:
    d[num[-1]]+=1
  else:
    d[num[-1]]=1
        
res=''
for i in range(n):
  
  if i!=0:
    res+=' '
  
  res+=str(d[num[i]])
print(res)

Solution (Python):
import sys



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

def union(x,y,par,rank):
    x = find(x,par)
    y = find(y,par)

    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):
    return find(x,par) == find(y,par)

input = sys.stdin.readline
n, k, l = map(int, input().split())    
apar = []
bpar = []
arank = [0]*n
brank = [0]*n

for i in range(n):
    apar.append(i)
    bpar.append(i)


for i in range(k):
    p,q = map(int, input().split())
    union(p-1,q-1,apar,arank)

for i in range(l):
    p,q = map(int, input().split())
    union(p-1,q-1,bpar,brank)

num = []
d = {}
for i in range(n):
    num.append(find(i,apar)+find(i,bpar)*10**6)
    if num[-1] in d:
        d[num[-1]] += 1
    else:
        d[num[-1]] = 1

res = ''
for i in range(n):
    if i != 0:
        res += ' '

    res += str(d[num[i]])

print(res)

Solution (Python):
n,k,l=map(int,input().split())
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
uf1=UnionFind(n)
uf2=UnionFind(n)
d=dict()
a,b=[0]*n,[0]*n
for i in range(k):
  p,q=map(int,input().split())
  uf1.union(p-1,q-1)
ans=[0]*n
for i in range(l):
  r,s=map(int,input().split())
  uf2.union(r-1,s-1)
for i in range(n):
  a[i]=uf1.find(i)
  b[i]=uf2.find(i)
  if (a[i],b[i]) not in d:
    d[(a[i],b[i])]=1
  else:
    d[(a[i],b[i])]+=1
for i in range(n):
  ans[i]=d[(a[i],b[i])]
print(*ans)

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


    def root(self,x):
        if self.roots[x]==x:
            return x
        else:
            self.roots[x]=self.root(self.roots[x])
            return self.roots[x]
    def unite(self,x,y):
        if self.root(x)==self.root(y):
            return
        else:
            if self.root(x)>self.root(y):
                self.roots[self.root(x)]=self.root(y)
            else:
                self.roots[self.root(y)]=self.root(x)
    
    def same(self,x,y):
        return self.root(x)==self.root(y)

N,K,L=list(input().split(" "))
N=int(N)
K=int(K)
L=int(L)
road=Unionfind(N)
train=Unionfind(N)
for i in range(K):
    p,q=map(int,list(input().split(" ")))
    road.unite(p-1,q-1)
for i in range(L):
    r,s=map(int,list(input().split(" ")))
    train.unite(r-1,s-1)



count=defaultdict(lambda:0)
point=[]
for i in range(N):
    a=road.root(i)
    b=train.root(i)
    l=[a,b]
    point.append(l)
    count[str(l)]+=1
for i in point:
    print(count[str(i)],end=" ")

Solution (Python):
class UnionFind(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.size = [1]*size

    def find(self, x):
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.size[x] < self.size[y]:
            self.size[y] += self.size[x]
            self.parent[x] = y
        else:
            self.size[x] += self.size[y]
            self.parent[y] = x
    
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def sizeofset(self, x):
        return self.size[self.find(x)]

if __name__ == "__main__":
    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())
        p -= 1
        q -= 1
        uf_road.unite(p,q)
    for _ in range(L):
        r,s = map(int,input().split())
        r -= 1
        s -= 1
        uf_rail.unite(r,s)
    roots = [None]*N
    for i in range(N):
        roots[i] = (uf_road.find(i), uf_rail.find(i))
    from collections import defaultdict
    d = defaultdict(int)
    for r in roots:
        d[r] += 1
    print(" ".join([str(d[roots[i]]) for i in range(N)]))

Solution (Python):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from functools import *
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def Golf():
    *a,=map(int,open(0))
def S_():
    return input()
def IS():
    return input().split()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'

    mp=[1]*(w+2)
    found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['YES','NO']

mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()

input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

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
    
    def __str__(self):
        rt=[i if j<0 else j for i,j in enumerate(self.table)]
        return str(rt)


show_flg=False
show_flg=True

ans=0

n,k,l=LI()

ufr=UnionFind(n)
ufh=UnionFind(n)

for i in range(k):
    a,b=LI_()
    ufh.union(a,b)

for i in range(l):
    a,b=LI_()
    ufr.union(a,b)

con=[0]*n
cnt=defaultdict(int)
for i in range(n):
    con[i]=ufr._root(i)*10**5+ufh._root(i)
    cnt[con[i]]+=1
for i in range(n):
    print(cnt[con[i]])

Solution (Python):
from collections import defaultdict
import sys
input = sys.stdin.readline
n,k,l = map(int,input().split())
road = [list(map(int,input().split())) for i in range(k)]
train = [list(map(int,input().split())) for i in range(l)]
rg = [[] for i in range(n+1)]
rv = [0 for i in range(n+1)]
tg = [[] for i in range(n+1)]
tv = [0 for i in range(n+1)]
def connect(road,rg,rv):
  for a,b in road:
    rg[a].append(b)
    rg[b].append(a)
  cnt = 0
  for i in range(1,n+1):
    if rv[i] == 0:
      cnt += 1
      stack = [i]
      while stack:
        x = stack.pop()
        rv[x] = cnt
        for y in rg[x]:
          if rv[y] == 0:
            stack.append(y)
            rv[y] = cnt
connect(road,rg,rv)
connect(train,tg,tv)
condc = defaultdict(list)
for i in range(1,n+1):
  cr = rv[i]
  ct = tv[i]
  condc[(cr,ct)].append(i)
ans = []
for i in range(1,n+1):
  cr = rv[i]
  ct = tv[i]
  ans.append(len(condc[(cr,ct)]))
print(*ans)

Solution (Python):
from collections import defaultdict
n,k,l = map(int,input().split())
road = [list(map(int,input().split())) for i in range(k)]
train = [list(map(int,input().split())) for i in range(l)]
rg = [[] for i in range(n+1)]
rv = [0 for i in range(n+1)]
tg = [[] for i in range(n+1)]
tv = [0 for i in range(n+1)]
def connect(road,rg,rv,):
  for a,b in road:
    rg[a].append(b)
    rg[b].append(a)
  cnt = 0
  for i in range(1,n+1):
    if rv[i] == 0:
      cnt += 1
      stack = [i]
      while stack:
        x = stack.pop()
        rv[x] = cnt
        for y in rg[x]:
          if rv[y] == 0:
            stack.append(y)
            rv[y] = cnt
connect(road,rg,rv)
connect(train,tg,tv)
condc = defaultdict(list)
for i in range(1,n+1):
  cr = rv[i]
  ct = tv[i]
  condc[(cr,ct)].append(i)
ans = []
for i in range(1,n+1):
  cr = rv[i]
  ct = tv[i]
  ans.append(len(condc[(cr,ct)]))
print(*ans)

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

par1=[-1]*(n+1)
par2=[-1]*(n+1)

def find1(x):
    if par1[x]<0:
        return x
    else:
        par1[x]=find1(par1[x])
        return par1[x]
def find2(x):
    if par2[x]<0:
        return x
    else:
        par2[x]=find2(par2[x])
        return par2[x]
def size1(x):
    return -par1[find1(x)]
def size2(x):
    return -par2[find2(x)]
def unite1(x,y):
    if find1(x)==find1(y):
        return False
    else:
        if size1(x)<size1(y):
            x,y=y,x
        X=find1(x)
        Y=find1(y)
        par1[X]-=size1(Y)
        par1[Y]=X
        return True
def unite2(x,y):
    if find2(x)==find2(y):
        return False
    else:
        if size2(x)<size2(y):
            x,y=y,x
        X=find2(x)
        Y=find2(y)
        par2[X]-=size2(Y)
        par2[Y]=X
        return True
def is_same1(x,y):
    return find1(x)==find1(y)
def is_same2(x,y):
    return find2(x)==find2(y)

for _ in range(k):
    p,q=map(int,input().split())
    unite1(p,q)
for _ in range(l):
    r,s=map(int,input().split())
    unite2(r,s)
L=[]
for i in range(1,n+1):
    L.append((find1(i),find2(i)))
kazu=Counter(L)
ans=[0]*(n)
for i in range(n):
    ans[i]=kazu[L[i]]
print(*ans, sep=' ')

Solution (Python):
N, K, L = [int(x) for x in input().split()]
K_lst = [[int(x) for x in input().split()] for i in range(K)]
L_lst = [[int(x) for x in input().split()] for i in range(L)]

ar = [int(i) for i in range(N + 1)]
br = [int(i) for i in range(N + 1)]

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

def union(x, y, array):
    x = find(x, array)
    y = find(y, array)

    if x == y:
        return
    if x > y:
        x, y = y, x
    array[y] = x

for i in K_lst:
    u, v = i
    union(u, v, ar)
for i in L_lst:
    u, v = i
    union(u, v, br)
for i in range(1, N + 1):
    find(i, ar)
    find(i, br)
dict = {}
for i in range(1, N + 1):
    a = ar[i]
    b = br[i]
    if not (a, b) in dict.keys():
        dict[(a, b)] = 1
    else:
        dict[(a, b)] += 1
a_lst = [0] * N
for i in range(N):
    a = ar[i + 1]
    b = br[i + 1]
    a_lst[i] = dict[(a, b)]
print(*a_lst)

Solution (Python):
from collections import*

class UnionFind:
    def __init__(self, n):
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

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

d = defaultdict(int)

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

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):
from collections import deque

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

graphs = [[[] for _ in range(n)], [[] for _ in range(n)]]
cands = [set(), set()]
for _ in range(k):
    x, y = map(int, input().split())
    graphs[0][x - 1].append(y - 1)
    graphs[0][y - 1].append(x - 1)
    cands[0].add(x - 1)
for _ in range(l):
    x, y = map(int, input().split())
    graphs[1][x - 1].append(y - 1)
    graphs[1][y - 1].append(x - 1)
    cands[1].add(x - 1)

groups = [[], []]
groups_inv = [[-1] * n, [-1] * n]
def dfs(start, case, num):
    q = deque()
    q.append(start)
    used = {start}
    groups[case].append(used)
    groups_inv[case][start] = num
    while q:
        node = q.popleft()
        for to in graphs[case][node]:
            if to in used:
                continue
            q.append(to)
            used.add(to)
            groups_inv[case][to] = num

for i in range(2):
    count = 0
    for node in cands[i]:
        if groups_inv[i][node] == -1:
            dfs(node, i, count)
            count += 1

ret = [-1] * n
for i in range(n):
    if groups_inv[0][i] == -1 or groups_inv[1][i] == -1:
        ret[i] = 1
    elif ret[i] == -1:
        cities = groups[0][groups_inv[0][i]] & groups[1][groups_inv[1][i]]
        for city in cities:
            ret[city] = len(cities)
print(*ret)

Solution (Python):
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue


Mod = 1000000007
import sys

sys.setrecursionlimit(100000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)




def main(): 
    n,k,l = map(int,input().split())
    pq = [list(map(int,input().split())) for i in range(k)]
    rs = [list(map(int,input().split())) for i in range(l)]
    un1 = UnionFind(n)
    un2 = UnionFind(n)
    for i in range(k):
        un1.union(pq[i][0]-1,pq[i][1]-1)
    for i in range(l):
        un2.union(rs[i][0]-1,rs[i][1]-1)
    d = defaultdict(int)
    anslist = []
    for i in range(n):
        d[un1.findroot(i),un2.findroot(i)] += 1
    for i in range(n):
        anslist.append(d[un1.findroot(i),un2.findroot(i)])
    print(*anslist,sep = " ")
if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

def unite(par, i, j):
    j = get_par(par, j)
    par[j] = get_par(par, i)

def get_par(par, p):
    while par[p] != p:
        p = par[p]
    return par[p]

n,k,l = map(int, input().split())
pq = []
road = [i for i in range(n+1)]
rail = [i for i in range(n+1)]
for i in range(k):
    p,q = map(int,input().split())
    pq.append((p,q))
    aa = get_par(road, p)
    bb = get_par(road, q)
    if aa == bb:
        continue
    
    if aa < bb:
        road[bb] = aa
    else:
        road[aa] = bb

rs = []
for i in range(l):
    p,q = map(int,input().split())
    rs.append((p,q))
    aa = get_par(rail, p)
    bb = get_par(rail, q)
    if aa == bb:
        continue
    
    if aa < bb:
        rail[bb] = aa
    else:
        rail[aa] = bb

ans = [(road[get_par(road, i)], rail[get_par(rail, i)]) for i in range(1,n+1)]
from collections import Counter
c = Counter(ans)
print(*[c[(road[get_par(road, i)], rail[get_par(rail, i)])] for i in range(1,n+1)])