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 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 examD():
    N, K, L = LI()
    ans = []
    ufk = UnionFind(N)
    ufl = UnionFind(N)
    for i in range(K):
        p, q = LI()
        ufk.union(p-1,q-1)
    for i in range(L):
        r, s = LI()
        ufl.union(r-1,s-1)
    d = defaultdict(int)
    for i in range(N):
        
        d[(ufk.find(i), ufl.find(i))] += 1
    for i in range(N):
        print(d[(ufk.find(i), ufl.find(i))])


import sys
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

Solution (Python):
class UnionFind:
    MAX_N = 0
    PAR  = [] 
    RANK = []

    def __init__(self,n):
        self.MAX_N = 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 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(self,x,y):
        return self.find(x) == self.find(y)

N,K,L = map(int,input().split())
path = UnionFind(N+1)
for _ in range(K):
    p,q = map(int,input().split())
    path.union(p,q)
rail = UnionFind(N+1)
for _ in range(L):
    p,q = map(int,input().split())
    rail.union(p,q)

Data = {}
for i in range(1,N+1):
    p = path.find(i)
    r = rail.find(i)
    k = str(p)+"-"+str(r)
    if k in Data.keys():
        Data[k] += 1
    else:
        Data[k] = 1

for i in range(1,N+1):
    p = path.find(i)
    r = rail.find(i)
    k = str(p)+"-"+str(r)
    print( Data[k], end= ' ')

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

road_par = []
road_rank = []
rail_par = []
rail_rank = []
c1 = []
c2 = []

def init(par, rank, c, n):
    for i in range(n):
        par.append(i)
        rank.append(0)
        c.append(0)


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


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


N, K, L = map(int, input().split())
init(road_par, road_rank, c1, N)
init(rail_par, rail_rank, c2, N)


for i in range(K):
    f, t = map(int, input().split())
    unite(road_par, road_rank, f-1, t-1)

for i in range(L):
    f,t = map(int, input().split())
    unite(rail_par, rail_rank, f-1, t-1)

for i in range(N):
    c1[find(road_par, i)] += 1
    c2[find(rail_par, i)] += 1

ans = [0 for i in range(N)]

"""
for i in range(N):
    for j in range(N):
        if find(road_par, i) == find(road_par, j) and find(rail_par, i) == find(rail_par, j):
            ans[i] += 1
"""
from collections import defaultdict
ans = defaultdict(int)
for i in range(N):
    ans[(find(road_par, i), find(rail_par, i))] += 1

for i in range(N):
    print(ans[(find(road_par, i), find(rail_par, i))], end=' ')
print('')

Solution (Python):
from collections import Counter,defaultdict,deque
import sys,bisect,math,itertools,string,queue
from heapq import heappop, heappush
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

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]


n,k,l = inpl()
ro = UnionFind(n)
tr = UnionFind(n)
for i in range(k):
    a,b = inpl()
    ro.union(a-1,b-1)
for i in range(l):
    a,b = inpl()
    tr.union(a-1,b-1)

d = defaultdict(int)
for i in range(n):
    d[(ro.find(i),tr.find(i))] += 1
for i in range(n):
    print(d[(ro.find(i),tr.find(i))])

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

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 main():
    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)]

    uf_r = UnionFind(n)
    uf_t = UnionFind(n)

    for i in range(k):
        uf_r.union(Road[i][0]-1,Road[i][1]-1)

    for i in range(l):
        uf_t.union(Train[i][0]-1,Train[i][1]-1)

    Roots_dict = defaultdict(int)
    Roots = []
    for i in range(n):
        Roots.append((uf_r.find(i),uf_t.find(i)))
        Roots_dict[Roots[i]] += 1

    ans = [0]*n

    for i in range(n):
        ans[i] = Roots_dict[Roots[i]]

    print(*ans)

if __name__ == '__main__':
    main()

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

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 roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

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

def main():
    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)]

    uf_r = UnionFind(n)
    uf_t = UnionFind(n)

    for i in range(k):
        uf_r.union(Road[i][0]-1,Road[i][1]-1)

    for i in range(l):
        uf_t.union(Train[i][0]-1,Train[i][1]-1)

    Roots_dict = defaultdict(int)
    Roots = []
    for i in range(n):
        Roots.append(str(uf_r.find(i))+' '+str(uf_t.find(i)))
        Roots_dict[Roots[i]] += 1

    ans = [0]*n

    for i in range(n):
        ans[i] = Roots_dict[Roots[i]]

    print(*ans)

if __name__ == '__main__':
    main()

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


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

    
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    
    
    def Unite(self, x, y):
        
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        
        if(x == y):
            return 
        
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


def main():
    N, K, L = map(int, input().split())
    A = UnionFind(N)
    for _ in range(K):
        p, q = map(int, input().split())
        A.Unite(p, q)
    B = UnionFind(N)
    for _ in range(L):
        s, r = map(int, input().split())
        B.Unite(s, r)
    
    d = defaultdict(int)
    C = []
    for i in range(N):
        a = A.Find_Root(i+1)
        b = B.Find_Root(i+1)
        C.append(str(a)+","+str(b))
        d[C[i]] += 1
    
    

    ans = [str(d[c]) for c in C]
    print(" ".join(ans))


if __name__ == '__main__':
    main()

Solution (Python):

import sys
from collections import defaultdict
input = sys.stdin.readline


def main():
    n, k, l = map(int, input().split())
    p, q = [], []
    for _ in range(k):
        pi, qi = map(int, input().split())
        p.append(pi)
        q.append(qi)
    r, s = [], []
    for _ in range(l):
        ri, si = map(int, input().split())
        r.append(ri)
        s.append(si)

    road_tree = make_union_find(p, q, n)
    rail_tree = make_union_find(r, s, n)

    a, b = [], []
    x = defaultdict(int)
    for i in range(n):
        a.append(root(road_tree, i))
        b.append(root(rail_tree, i))
        key = (a[i], b[i])
        x[key] += 1

    for i in range(n):
        print(x[(a[i], b[i])], end=' ')

    
    
    


def make_union_find(a, b, n):
    union_find_tree = [i for i in range(n)]

    for i in range(len(a)):
        x = root(union_find_tree, a[i] - 1)
        y = root(union_find_tree, b[i] - 1)
        if x != y:
            union_find_tree[x] = min(x, y)
            union_find_tree[y] = union_find_tree[x]

    return union_find_tree












def root(union_find_tree, target):
    if union_find_tree[target] == target:
        return target
    else:
        union_find_tree[target] = root(
            union_find_tree, union_find_tree[target])
        return union_find_tree[target]


if __name__ == '__main__':
    main()

Solution (Python):

import sys
from collections import defaultdict
input = sys.stdin.readline


def main():
    n, k, l = map(int, input().split())
    p, q = [], []
    for _ in range(k):
        pi, qi = map(int, input().split())
        p.append(pi)
        q.append(qi)
    r, s = [], []
    for _ in range(l):
        ri, si = map(int, input().split())
        r.append(ri)
        s.append(si)

    road_tree = make_union_find(p, q, n)
    rail_tree = make_union_find(r, s, n)

    a, b = [], []
    x = defaultdict(int)
    for i in range(n):
        a.append(root(road_tree, i))
        b.append(root(rail_tree, i))
        key = (a[i], b[i])
        x[key] += 1

    for i in range(n):
        print(x[(a[i], b[i])], end=' ')


def make_union_find(a, b, n):
    union_find_tree = [i for i in range(n)]

    for i in range(len(a)):
        x = root(union_find_tree, a[i] - 1)
        y = root(union_find_tree, b[i] - 1)
        if x != y:
            union_find_tree[x] = y

    return union_find_tree


def root(union_find_tree, target):
    if union_find_tree[target] == target:
        return target
    else:
        union_find_tree[target] = root(
            union_find_tree, union_find_tree[target])
        return union_find_tree[target]


if __name__ == '__main__':
    main()

Solution (Python):
def union(parent,size,a,b):
    x=find(parent,a)
    y=find(parent,b)
    if x!=y:
        if size[x]<size[y]:
            parent[x]=y 
            size[y]=size[x]+size[y]
        else:
            parent[y]=x 
            size[x]=size[x]+size[y]
    return parent,size 
def find(parent, a):
    while a != parent[a]:
            parent[a]=parent[parent[a]]
            a=parent[a]
    return a
n,k,l=map(int,input().split())
parent=[i for i in range(n)]
size=[1]*n
for i in range(k): 
    a,b=map(int,input().split())
    a-=1 
    b-=1 
    parent,size=union(parent,size,a,b)
parent2=[i for i in range(n)]
size2=[1]*n  
for i in range(l): 
    a,b=map(int,input().split())
    a-=1 
    b-=1 
    parent2,size2=union(parent2,size2,a,b)
from collections import defaultdict 
d=defaultdict(int)
for i in range(n):
    d[(find(parent,i),find(parent2,i))]+=1 
for i in range(n):
    a,b=find(parent,i),find(parent2,i)
    print(d[a,b],end=' ')

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

root_road = list(range(N))
root_rail = list(range(N))
depth_road = [1 for _ in range(N)]
depth_rail = [1 for _ in range(N)]

def find(a,root):
    if root[a] == a:
        return a
    else:
        root[a] = find(root[a],root)
        return root[a]

def unite(a,b,root,depth):
    A = find(a,root)
    B = find(b,root)
    if A == B:
        return
    elif depth[A] > depth[B]:
        root[B] = A
        depth[A] += depth[B]
    else:
        root[A] = B
        depth[B] += depth[A]

for i in range(K):
    p,q = map(int,input().split())
    unite(p-1,q-1,root_road,depth_road)
for i in range(L):
    r,s = map(int,input().split())
    unite(r-1,s-1,root_rail,depth_rail)
d = defaultdict(int)
pairs = []
for i in range(N):
    road = find(i,root_road)
    rail = find(i,root_rail)
    pairs.append((road,rail))
    d[(road,rail)] += 1
for p in pairs:
    print(d[p],end = " ")

Solution (Python):
import sys
import collections as c
sys.setrecursionlimit(10**6)

import sys
sys.setrecursionlimit(10**7)

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

    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    def Unite(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    def Count(self, x):
        return -self.root[self.Find_Root(x)]

N, K, L = map(int,input().split())
p = []
q = []
l = []
r = []

for _ in range(K):
	p_tmp, q_tmp = map(int ,input().split())
	p.append(p_tmp)
	q.append(q_tmp)

for _ in range(L):
	l_tmp, r_tmp = map(int, input().split())
	l.append(l_tmp)
	r.append(r_tmp)

road = UnionFind(N)
train = UnionFind(N)

for i in range(K):
	road.Unite(p[i], q[i])

for i in range(L):
	train.Unite(l[i], r[i])

ar = []

for i in range(1,N+1):
	a = road.Find_Root(i)
	b = train.Find_Root(i)
	ar.append(str([a,b]))

Car = c.Counter(ar)

for i in range(N):
	print(Car[ar[i]], end = " ")

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

class UnionFind():
  def __init__(self,N):
    self.parents=list(range(N))
    self.size=[1]*N
  def find(self,x):
    if self.parents[x]==x:
      return x
    else:
      self.parents[x]=self.find(self.parents[x])
      return self.parents[x]
  def union(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.parents[x]=y
    else:
      self.size[x]+=self.size[y]
      self.parents[y]=x

uf1=UnionFind(N)
uf2=UnionFind(N)
for i in range(K):
  x,y=map(int,input().split())
  uf1.union(x-1,y-1)
for j in range(L):
  x,y=map(int,input().split())
  uf2.union(x-1,y-1)

keys=[(uf1.find(x),uf2.find(x)) for x in range(N)]
count={}
for key in keys:
  if key in count:
    count[key]+=1
  else:
    count[key]=1
print(*[count[key] for key in keys])

Solution (Python):


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



    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
            self.size[x]+=self.size[y]


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


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

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

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


from collections import defaultdict
c=defaultdict(int)
for i in range(1,n+1):
    c[(uf1.find(i),uf2.find(i))]+=1
    
for i in range(1,n+1):
    print(c[(uf1.find(i),uf2.find(i))])

Solution (Python):
from collections import Counter

n, k, l = map(int, input().split())
ps = [tuple(map(int, input().split())) for _ in range(k)]
rs = [tuple(map(int, input().split())) for _ in range(l)]

def root(n, u):
    if u[n] == n:
        return n
    u[n] = root(u[n], u)
    return u[n]

union1 = {x:x for x in range(1, n+1)}
for p, q in ps:
    union1[root(p, union1)] = root(q, union1)

union2 = {x:x for x in range(1, n+1)}
for r, s in rs:
    union2[root(r, union2)] = root(s, union2)

gs = {x:(root(x, union1), root(x, union2)) for x in range(1, n+1)}
c = Counter(gs.values())
print(' '.join(str(c[gs[x]]) for x in range(1, n+1)))

Solution (Python):
class UF:
    def __init__(self, N):
        self.uf = [-1]*N
        self.n = N

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

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

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x==y: return
        if self.size(x) > self.size(y): x, y = y, x
        self.uf[y] += self.uf[x]
        self.uf[x] = y
        self.n -= 1

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

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

keys = [(uf1.find(x), uf2.find(x)) for x in range(N)]
count = {}
for key in keys:
    if key in count: count[key]+=1
    else: count[key]=1

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

Solution (Python):

def wantp(lis,n):

    q = []
    while lis[n] != n:
        q.append(n)
        n = lis[n]

    for i in q:
        lis[i] = n

    return n


N,K,L = map(int,input().split())
rp = [i for i in range(N)]
rank = [1 for i in range(N)]
pqlis = []

for i in range(K):

    P,Q = map(int,input().split())
    P -= 1
    Q -= 1

    PP = wantp(rp,P)
    QP = wantp(rp,Q)
    pqlis.append([P,Q])

    if PP != QP:

        if rank[PP] < rank[QP]:
            rp[PP] = QP

        elif rank[QP] < rank[PP]:
            rp[QP] = PP

        else:
            rp[QP] = PP
            rank[QP] += 1



tp = [i for i in range(N)]
rank = [1 for i in range(N)]


for i in range(L):

    P,Q = map(int,input().split())
    P-=1
    Q-=1
    pqlis.append([P,Q])

    PP = wantp(tp,P)
    QP = wantp(tp,Q)

    

    if PP != QP:

        if rank[PP] < rank[QP]:
            tp[PP] = QP

        elif rank[QP] < rank[PP]:
            tp[QP] = PP

        else:
            tp[QP] = PP
            rank[QP] += 1

dic = {}

for i in range(N):

    p1 = wantp(rp,i)
    p2 = wantp(tp,i)
    string = str(p1) + "," + str(p2)

    if string not in dic:
        dic[string] = 1
    else:
        dic[string] += 1

for i in range(N):

    p1 = wantp(rp,i)
    p2 = wantp(tp,i)
    string = str(p1) + "," + str(p2)

    print (dic[string])

Solution (Python):

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


def create_groups(N, links):
    groups = list(range(N))
    for i in range(N):
        if groups[i] != i:
            continue
        q = [i]
        while q:
            j = q.pop()
            for k in links[j]:
                if groups[k] != i:
                    groups[k] = i
                    q.append(k)
    return groups


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

road_links = create_links(N, K)
rail_links = create_links(N, L)
road_groups = create_groups(N, road_links)
rail_groups = create_groups(N, rail_links)

d = {}
for i in range(N):
    t = (road_groups[i], rail_groups[i])
    if t in d:
        d[t] += 1
    else:
        d[t] = 1

print(*[d[(road_groups[i], rail_groups[i])] for i in range(N)])

Solution (Python):

def find(parent, i):
    t = parent[i]
    if t < 0:
        return i
    t = find(parent, t)
    parent[i] = t
    return t


def unite(parent, i, j):
    i = find(parent, i)
    j = find(parent, j)
    if i == j:
        return
    parent[j] += parent[i]
    parent[i] = j


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

roads = [-1] * N
rails = [-1] * N

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

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

d = {}
for i in range(N):
    t = (find(roads, i), find(rails, i))
    if t in d:
        d[t] += 1
    else:
        d[t] = 1

print(*[d[(find(roads, i), find(rails, i))] for i in range(N)])

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
        
    def find_root(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]
        
    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1
                
    def isSameGroup(self, x, y):
        return self.find_root(x) == self.find_root(y)
    
    def count(self, x):
        return -self.root[self.find_root(x)]


N,K,L = map(int, input().split())
road_list = []
for i in range(K):
    road_list.append([int(x) for x in input().split()])
train_list = []
for i in range(L):
    train_list.append([int(x) for x in input().split()])
    
road = UnionFind(N)
train = UnionFind(N)

for i in range(K):
    road.unite(road_list[i][0], road_list[i][1])
    
for i in range(L):
    train.unite(train_list[i][0], train_list[i][1])
    
R = [i for i in range(N+1)]
T = [i for i in range(N+1)]

for i in range(1, N+1):
    R[i] = road.find_root(i)
    T[i] = train.find_root(i)
    
pair = [0 for i in range(N+1)]
for i in range(1, N+1):
    pair[i] = (R[i], T[i])
    
dic = {}
for i in range(1, N+1):
    if pair[i] in dic:
        dic[pair[i]] += 1
    else:
        dic[pair[i]] = 1
        
for i in range(1, N+1):
    print(dic[pair[i]])

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

n,k,l=map(int,input().split())
load=UnionFind(n)
train=UnionFind(n)
for i in range(k):
    a,b=map(int,input().split())
    load.union(a,b)
for i in range(l):
    a,b=map(int,input().split())
    train.union(a,b)

ar=[(load.find(i),train.find(i)) for i in range(1,n+1)]
dic=defaultdict(int)

for i in ar:
    dic[i]+=1

ans=[]
for i in range(n):
    ans.append(dic[ar[i]])
print(*ans)

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

def find(list_path, x):
  if list_path[x] != x:
    list_path[x] = find(list_path, list_path[x])
  return list_path[x]

def union(list_path, x, y):
  x = find(list_path, x)
  y = find(list_path, y)
  if x != y:
    list_path[x] = min(x, y)
    list_path[y] = list_path[x]

list_road = [i for i in range(n)]
for _ in range(k):
  p, q = map(int, input().split(" "))
  union(list_road, (p - 1), (q - 1))
list_rail = [i for i in range(n)]
for _ in range(l):
  r, s = map(int, input().split(" "))
  union(list_rail, (r - 1), (s - 1))

dict_num_connect = {}
for i in range(n):
  dict_num_connect[list_road[i], list_rail[i]] = dict_num_connect.get(
      (find(list_road, i), find(list_rail, i)), 0) + 1

print(" ".join(str(dict_num_connect[list_road[i], list_rail[i]]) 
               for i in range(n)))

Solution (Python):
from collections import defaultdict


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

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

    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1

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

    def size(self, x):
        return -self.root[self.find_root(x)]


N, K, L = map(int, input().split())
UFc = UnionFind(N)
UFt = UnionFind(N)
for _ in range(K):
    p, q = map(int, input().split())
    UFc.unite(p, q)
for _ in range(L):
    p, q = map(int, input().split())
    UFt.unite(p, q)

gr = [0] * (N + 1)
cnt = defaultdict(int)
for i in range(1, N + 1):
    gr[i] = UFc.find_root(i) * (N + 1) + UFt.find_root(i)
    cnt[gr[i]] += 1

ans = [0] * N
for i in range(1, N + 1):
    ans[i-1] = cnt[gr[i]]

print(*ans)

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

def unite(node_a, node_b):
    root_a = node_a.root()
    root_b = node_b.root()
    if root_a == root_b:
        return False
    if root_b.depth > root_a.depth:
        root_a, root_b = root_b, root_a
    root_b.is_root = False
    root_b.parent = root_a
    root_a.depth = max(root_a.depth, root_b.depth+1)
    return True

class Node:
    def __init__(self, id):
        self.id = id
        self.is_root = True
        self.parent = None
        self.depth = 1
    
    def root(self):
        
        
        
        
        
        
        
        node = self
        while not node.is_root:
            node = node.parent
        return node

def main():
    N, K, L = map(int, input().split())
    
    trains = [Node(i) for i in range(N)]
    streets = [Node(i) for i in range(N)]

    for i in range(K):
        p, q = map(int, input().split())
        p -= 1; q -= 1
        unite(trains[p], trains[q])
    for i in range(L):
        r, s = map(int, input().split())
        r -= 1; s -= 1
        unite(streets[r], streets[s])
    dic = {}
    roots = []
    for i in range(N):
        tmp = (trains[i].root().id, streets[i].root().id)
        roots.append(tmp)
        if tmp in dic:
            dic[tmp] += 1
        else:
            dic[tmp] = 1
    
    for i in range(N-1):
        print(dic[roots[i]], end=" ")
    print(dic[roots[N-1]])

if __name__ == "__main__":
    main()