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):
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)]
rcnt = [set([i]) for i in range(n+1)]
rail = [i for i in range(n+1)]
acnt = [set([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
        rcnt[aa] |= rcnt[bb]
    else:
        road[aa] = bb
        rcnt[bb] |= rcnt[aa]

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
        acnt[aa] |= acnt[bb]
        
    else:
        rail[aa] = bb
        acnt[bb] |= acnt[aa]

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)])

Solution (Python):
from collections import*
import sys


class UnionFind(object):
    def __init__(self, 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
        return


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

ro_cl = UnionFind(n)
ra_cl = UnionFind(n)
d = defaultdict(int)














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



for i in range(n):
    d[(ro_cl.find(i), ra_cl.find(i))] += 1
print(*[d[(ro_cl.find(i), ra_cl.find(i))]for i in range(n)])

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


class UnionFind(object):
    def __init__(self, n):
        
        
        
        self.parents = [-1 for i in range(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
        return


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

ro_cl = UnionFind(n)
ra_cl = UnionFind(n)
d = defaultdict(int)













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



for i in range(n):
    d[(ro_cl.find(i), ra_cl.find(i))] += 1
print(*[d[(ro_cl.find(i), ra_cl.find(i))]for i in range(n)])

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


class UnionFind(object):
    def __init__(self, n):
        
        
        
        self.parents = [-1 for i in range(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
        return

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

ro_cl = UnionFind(n)
ra_cl = UnionFind(n)
d = defaultdict(int)













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



for i in range(n):
    d[(ro_cl.find(i), ra_cl.find(i))] += 1
print(*[d[(ro_cl.find(i), ra_cl.find(i))]for i in range(n)])

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


class UnionFind(object):
    def __init__(self, n):
        
        
        
        self.parents = [-1 for i in range(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
        return




















n, k, l = map(int, input().split())
ro_cl = UnionFind(n)
ra_cl = UnionFind(n)
d = defaultdict(int)
for i in range(k):
    p, q = map(int, input().split())
    ro_cl.union(p-1, q-1)
for i in range(l):
    p, q = map(int, input().split())
    ra_cl.union(p-1, q-1)
for i in range(n):
    d[(ro_cl.find(i), ra_cl.find(i))] += 1
print(*[d[(ro_cl.find(i), ra_cl.find(i))]for i in range(n)])

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


class UnionFind(object):
    def __init__(self, n):
        
        
        
        self.parents = [-1 for i in range(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
        return

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


n, k, l = map(int, input().split())
ro_cl = UnionFind(n)
ra_cl = UnionFind(n)
d = defaultdict(int)
for i in range(k):
    p, q = map(int, input().split())
    ro_cl.union(p-1, q-1)
for i in range(l):
    p, q = map(int, input().split())
    ra_cl.union(p-1, q-1)
for i in range(n):
    d[(ro_cl.find(i), ra_cl.find(i))] += 1
print(*[d[(ro_cl.find(i), ra_cl.find(i))]for i in range(n)])

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


class UNION_FIND(object):
    def __init__(self,n):
        
        
        
        self.parent=[-1 for i in range(n)]
        
    def root(self,x):
        
        if self.parent[x]<0:
            return x
        else:
            self.parent[x]=self.root(self.parent[x])  
            return self.parent[x]
 
    def size(self,x):
        
        return -self.parent[self.root(x)]   
        
    def union(self,x,y):
        
        
        
        x=self.root(x)
        y=self.root(y)
        
        if x==y:   
            return False
            
        
        
        if self.size(x)<self.size(y):
            x,y=y,x
        self.parent[x]+=self.parent[y]  
        self.parent[y]=x   
        return True
        
n,k,l=map(int,input().split())
u1=UNION_FIND(n)
u2=UNION_FIND(n)
d=defaultdict(int)
for i in range(k):
    p,q=map(int,input().split())
    u1.union(p-1,q-1)
for i in range(l):
    p,q=map(int,input().split())
    u2.union(p-1,q-1)
for i in range(n):
    d[(u1.root(i),u2.root(i))]+=1
print(*[d[(u1.root(i),u2.root(i))]for i in range(n)])

Solution (Python):
import sys




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


def unite(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())
rpar = [] 
tpar = []
rrank = [0]*n
trank= [0]*n


for i in range(n):
    
    rpar.append(i)
    tpar.append(i)


for i in range(k):
    x,y = map(int,input().split())
    unite(x-1,y-1,rpar,rrank)
for i in range(L):
    x,y = map(int,input().split())
    unite(x-1,y-1,tpar,trank)

num = []
d = {}
for i in range(n):
    num.append(find(i,rpar)+find(i,tpar)*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):
def main():
    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)]      
    
    ii = lambda : int(input())
    mi = lambda : map(int,input().split())
    li = lambda : list(map(int,input().split()))
    n,k,l = mi()
    road = UnionFind(n)
    train = UnionFind(n)
    for i in range(k):
        p,q = mi()
        road.Unite(p,q)
    for i in range(l):
        p,q = mi()
        train.Unite(p,q)
    lis = []
    for i in range(1,n+1):
        a = road.Find_Root(i)
        b = train.Find_Root(i)
        lis.append(a + 10 ** 6 * b)
    from collections import Counter
    z = Counter(lis)
    lis2 = []
    for i in range(n):
        lis2.append(z[lis[i]])
    print(*lis2)
       
main()

Solution (Python):
from collections import Counter

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


class UnionFind:
    def __init__(self, x):
        self.p = [e for e in range(x)]
        self.rank = [0] * x

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

    def unite(self, u, v):
        self.link(self.find_set(u), self.find_set(v))

    def find_set(self, u):
        if u != self.p[u]:
            self.p[u] = self.find_set(self.p[u])

        return self.p[u]

    def link(self, u, v):
        if self.rank[u] > self.rank[v]:
            self.p[v] = u
        else:
            self.p[u] = v
            if self.rank[u] == self.rank[v]:
                self.rank[v] += 1


road_uf = UnionFind(n)
train_uf = UnionFind(n)

for p, q in pq:
    p -= 1
    q -= 1
    road_uf.unite(p, q)

for r, s in rs:
    r -= 1
    s -= 1
    train_uf.unite(r, s)

group = [(road_uf.find_set(i), train_uf.find_set(i)) for i in range(n)]

c = Counter(group)

ans = []
for e in group:
    ans.append(c[e])

print(*ans)

Solution (Python):
n, k, l = map(int, input().split())
pq = [list(map(int, input().split())) for _ in range(k)]
rs = [list(map(int, input().split())) for _ in range(l)]
INF = 10 ** 6


class UnionFind:
    def __init__(self, x):
        self.p = [e for e in range(x)]
        self.rank = [0] * x

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

    def unite(self, u, v):
        self.link(self.find_set(u), self.find_set(v))

    def find_set(self, u):
        if u != self.p[u]:
            self.p[u] = self.find_set(self.p[u])

        return self.p[u]

    def link(self, u, v):
        if self.rank[u] > self.rank[v]:
            self.p[v] = u
        else:
            self.p[u] = v
            if self.rank[u] == self.rank[v]:
                self.rank[v] += 1


road_uf = UnionFind(n)
train_uf = UnionFind(n)

for p, q in pq:
    p -= 1
    q -= 1
    road_uf.unite(p, q)

for r, s in rs:
    r -= 1
    s -= 1
    train_uf.unite(r, s)

group = [(road_uf.find_set(i), train_uf.find_set(i)) for i in range(n)]

srt = sorted(group, key=lambda x: x[1])
srt.append((INF, INF))
srt.sort()

prev = (-1, -1)
cnt = 0
d = {}
for e in srt:
    if e == prev:
        cnt += 1
    else:
        d[prev] = cnt
        cnt = 1
        prev = e

ans = [d[e] for e in group]
print(*ans)

Solution (Python):

import sys
from collections import Counter
INF = float("inf")


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

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

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

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            self.tree[x] = y


def solve(N: int, K: int, L: int, p: "List[int]", q: "List[int]", r: "List[int]", s: "List[int]"):
    uf_train = UnionFind(N)
    uf_path = UnionFind(N)

    for i in range(K):
        uf_path.unite(p[i]-1, q[i]-1)
    for i in range(L):
        uf_train.unite(r[i]-1, s[i]-1)

    counter = Counter()
    for i in range(N):
        key = (uf_path.root(i), uf_train.root(i))
        counter[key] += 1

    for i in range(N):
        key = (uf_path.root(i), uf_train.root(i))
        if i != N-1:
            print(counter[key], end=" ")
        else:
            print(counter[key])

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    K = int(next(tokens))  
    L = int(next(tokens))  
    p = [int()] * (K)  
    q = [int()] * (K)  
    for i in range(K):
        p[i] = int(next(tokens))
        q[i] = int(next(tokens))
    r = [int()] * (L)  
    s = [int()] * (L)  
    for i in range(L):
        r[i] = int(next(tokens))
        s[i] = int(next(tokens))
    solve(N, K, L, p, q, r, s)


if __name__ == '__main__':
    main()

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):
        dic = {}
        for x in range(self.N):
            r = self.find(x)
            dic.setdefault(r, [])
            dic[r].append(x)
        return dic


import sys
sys.stdin.readline

def main():
    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)
    P = [None] * N
    D = {}
    for i in range(N):
        T = (UF1.find(i), UF2.find(i))
        P[i] = T
        D.setdefault(T, 0)
        D[T] += 1
    print(*[D[p] for p in P])


if __name__ == "__main__":
    main()

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

n,k,l=map(int, input().split())
p= [list(map(int, input().split())) for i in range(k)]
r = [list(map(int, input().split())) for i in range(l)]
uf1=UnionFind(n)
uf2=UnionFind(n)
for i in range(k):
    uf1.union(p[i][0]-1,p[i][1]-1)

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

from collections import defaultdict
p=defaultdict(int)
for i in range(n):
    a=uf1.find(i)
    b=uf2.find(i)
    p[(a,b)]+=1
ans=[]
for i in range(n):
    ans.append(p[uf1.find(i),uf2.find(i)])
print(*ans)

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

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

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

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

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

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

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

from collections import defaultdict

n,k,l = map(int, input().split())
u = UnionFind(n+1)
v = UnionFind(n+1)

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

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

d = defaultdict(int)
for i in range(1,n+1):
  x = (u.root(i), v.root(i))
  d[x] += 1

print(*[d[(u.root(i), v.root(i))] for i in range(1,n+1)])

Solution (Python):
from collections import Counter


class UnionFindTree:
    def __init__(self):
        self.p = {}
        self.rank = {}

    def make(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

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

    def unite(self, x, y):
        return self._unite(self.find(x), self.find(y))

    def _unite(self, x, y):
        if self.rank[x] < self.rank[y]:
            self.p[x] = y
            return y
        else:
            self.p[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            return x


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

utf1 = UnionFindTree()
utf2 = UnionFindTree()
for i in range(N):
    utf1.make(i+1)
    utf2.make(i+1)

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

pairs = [(utf1.find(i+1), utf2.find(i+1)) for i in range(N)]
counts = Counter(pairs)
print(" ".join([str(counts[k]) for k in pairs]))

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

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

def unite(parent, rank, u, v):
    u = find(parent, u)
    v = find(parent, v)
    if u == v:
        return
    if rank[u] < rank[v]:
        parent[u] = v
    else:
        parent[v] = u
        if rank[u] == rank[v]:
            rank[u] += 1

N, K, L = map(int, input().split())
roads = list(range(N+1))
rails = list(range(N+1))
r_rank = [0] * (N + 1)
t_rank = [0] * (N + 1)

for _ in range(K):
    p, q = map(int, input().split())
    unite(roads, r_rank, p, q)
for _ in range(L):
    p, q = map(int, input().split())
    unite(rails, t_rank, p, q)

d = {}
for i in range(1, N+1):
    p = (find(roads, i), find(rails, i))
    d[p] = d.get(p, 0) + 1

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

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


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rank = [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_root = self.Find_Root(x)
        y_root = self.Find_Root(y)

        if(x_root == y_root):
            return
        
        if self.rank[x_root] >= self.rank[y_root]:
            self.rank[x_root] += self.rank[y_root]
            self.root[y_root] = x_root
        else:
            self.rank[y_root] += self.rank[x_root]
            self.root[x_root] = y_root

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

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

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

for i in range(k):
    uf1.Unite(pq[i][0], pq[i][1])

for i in range(l):
    uf2.Unite(rs[i][0], rs[i][1])

pairs = []
d = defaultdict(int)

for i in range(1, n+1):
    name = "{} {}".format(uf1.Find_Root(i), uf2.Find_Root(i))
    pairs.append(name)
    d[name] += 1

ans = []
for i in range(n):
    ans.append(d[pairs[i]])

print(*ans)

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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rank = [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_root = self.Find_Root(x)
        y_root = self.Find_Root(y)

        if(x_root == y_root):
            return
        
        if self.rank[x_root] >= self.rank[y_root]:
            self.root[x_root] += self.root[y_root]
            self.root[y_root] = x_root
        else:
            self.root[y_root] += self.root[x_root]
            self.root[x_root] = y_root

    
    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())
pq = [list(map(int, input().split())) for _ in range(k)]
rs = [list(map(int, input().split())) for _ in range(l)]

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

for i in range(k):
    uf1.Unite(pq[i][0], pq[i][1])

for i in range(l):
    uf2.Unite(rs[i][0], rs[i][1])

pairs = []
d = defaultdict(int)

for i in range(1, n+1):
    name = "{} {}".format(uf1.Find_Root(i), uf2.Find_Root(i))
    pairs.append(name)
    d[name] += 1

ans = []
for i in range(n):
    ans.append(d[pairs[i]])

print(*ans)

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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rank = [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_root = self.Find_Root(x)
        y_root = self.Find_Root(y)

        if(x_root == y_root):
            return
        
        if self.rank[x_root] >= self.rank[y_root]:
            self.root[x_root] += self.root[y_root]
            self.root[y_root] = x_root
        else:
            self.root[y_root] += self.root[x_root]
            self.root[x_root] = y_root

    
    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())
pq = [list(map(int, input().split())) for _ in range(k)]
rs = [list(map(int, input().split())) for _ in range(l)]

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

for i in range(k):
    uf1.Unite(pq[i][0], pq[i][1])

for i in range(l):
    uf2.Unite(rs[i][0], rs[i][1])

pairs = []
d = defaultdict(int)

for i in range(1, n+1):
    name = "{} {}".format(uf1.Find_Root(i), uf2.Find_Root(i))
    pairs.append(name)
    d[name] += 1

ans = []
for i in range(n):
    ans.append(d[pairs[i]])

print(*ans)

Solution (Python):
class UnionFind():
    def __init__(self,n):
        self.n = n
        self.parents = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
    def find(self,x):
        root = x
        while self.parents[root] != root:
            root = self.parents[root]
        while self.parents[x] != root:
            parent = self.parents[x]
            self.parents[x] = root
            x = parent
        return root
    def unite(self,x,y):
        xroot = self.find(x)
        yroot = self.find(y)
        if xroot == yroot:
            return
        xrank = self.rank[xroot]
        yrank = self.rank[yroot]
        if xrank < yrank:
            self.parents[xroot] = yroot
        elif xrank == yrank:
            self.parents[yroot] = xroot
            self.rank[yroot] += 1
        else:
            self.parents[yroot] = xroot
            
N,K,L=map(int,input().split())
ufroad = UnionFind(N)
uftrain = UnionFind(N)

for i in range(K):
    p,q = map(int,input().split())
    ufroad.unite(p-1,q-1)
for i in range(L):
    r,s = map(int,input().split())
    uftrain.unite(r-1,s-1)
uflist=[]
for i in range(N):
    uflist.append((ufroad.find(i), uftrain.find(i)))
counter={}
for i in range(N):
  if uflist[i] not in counter.keys():
    counter[uflist[i]]=1
  else:
    counter[uflist[i]]+=1
print(' '.join(map(str, [counter[uflist[i]] for i in range(N)])))

Solution (Python):
from collections import Counter
n,k,l = map(int,input().split())
e1 = [[] for _ in range(n)]
e2 = [[] for _ in range(n)]

for _ in range(k):
    p,q = map(int,input().split())
    e1[p-1].append(q-1)
    e1[q - 1].append(p - 1)

for _ in range(l):
    p,q = map(int,input().split())
    e2[p-1].append(q-1)
    e2[q - 1].append(p - 1)

g1 = [-1]*n
for i in range(n):
    if g1[i] != -1:
        continue
    g1[i] = i
    s = [i]
    while s:
        v = s.pop()
        for d in e1[v]:
            if g1[d] != -1:
                continue
            g1[d] = i
            s.append(d)
g2 = [-1]*n
for i in range(n):
    if g2[i] != -1:
        continue
    g2[i] = i
    s = [i]
    while s:
        v = s.pop()
        for d in e2[v]:
            if g2[d] != -1:
                continue
            g2[d] = i
            s.append(d)
g = []
for i in range(n):
    g.append((g1[i], g2[i]))
c = Counter(g)
f = [c[g[i]] for i in range(n)]
print(' '.join(map(str, f)))