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(object):

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

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[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]:
            x, y = y, x

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

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

from collections import Counter
fn = lambda: map(int, input().split())
N, K, L = fn()
roads = UnionFind(N)
for i in range(K):
    pi, qi = fn()
    roads.union(pi-1, qi-1)
rails = UnionFind(N)
for i in range(L):
    ri, si = fn()
    rails.union(ri-1, si-1)
groups = []
for i in range(N):
    groups.append(str(roads.find(i)) + '-' + str(rails.find(i)))
c = Counter(groups)
print(*(c[g] for g in groups))

Solution (Python):
import sys
from collections import defaultdict

input = sys.stdin.readline


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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x

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


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

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

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

c = defaultdict(int)
for i in range(N):
    x = uf1.find(i)
    y = uf2.find(i)
    c[(x, y)] += 1

for i in range(N):
    x = uf1.find(i)
    y = uf2.find(i)
    print(c[(x, y)], end=' ')
print()

Solution (Python):
class UnionFind:
    def __init__(self, node:int) -> None:
        self.n = node
        self.par = [i for i in range(self.n)]
        self.rank = [0 for i in range(self.n)]
        
    def find(self, x:int) -> int:
        if x == self.par[x]:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    def unite(self, x:int, y:int) -> bool:
        if self.isSame(x,y):
            
            return False
        
        rx = self.find(x)
        ry = self.find(y)
        
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = self.par[ry]
        else:
            self.par[ry] = self.par[rx]
            
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1
                
        return True
                
    def isSame(self, x:int, y:int) -> bool:
        return self.find(x) == self.find(y)
    
from collections import defaultdict
import sys
sdin = sys.stdin.readline    


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

pq = []
for i in range(k):
    p, q = map(int, sdin().split())
    pq.append(tuple([p-1, q-1]))

rs = []
for i in range(l):
    r, s = map(int, sdin().split())
    rs.append(tuple([r-1, s-1]))


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

rail = UnionFind(n)
for r, s in rs:
    rail.unite(r, s)


path_rail = defaultdict(int)
    
for i in range(n):
    path_rail[(path.find(i), rail.find(i))] += 1


ans = [path_rail[(path.find(i), rail.find(i))] for i in range(n)]
print(*ans)

Solution (Python):
from collections import defaultdict

class UnionFind:
    def __init__(self, N):
        self.N = N
        self.parent = [i for i in range(N)]
        self.rank = [1]*(N)

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

    def is_group(self, x,y):
        return self.getroot(x) == self.getroot(y)

    def union(self, x, y):
        rootx = self.getroot(x)
        rankx = self.rank[rootx]
        rooty = self.getroot(y)
        ranky = self.rank[rooty]
        if rankx > ranky:
            self.parent[rooty] = rootx
        else:
            self.parent[rootx] = rooty
            self.rank[rooty] = max(self.rank[rooty], self.rank[rootx]+1)

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

loads = UnionFind(n)
rails = UnionFind(n)

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

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

pair = defaultdict(int)
for i in range(n):
    pair[(loads.getroot(i), rails.getroot(i))] += 1

ans = "" 
for i in range(n-1):
    ans += str(pair[(loads.getroot(i), rails.getroot(i))]) + " "
ans += str(pair[(loads.getroot(n-1), rails.getroot(n-1))])
print(ans)

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, L, PQ, RS):
    ans = 0
    gr = defaultdict(list)
    for p, q in PQ:
        gr[p].append(q)
        gr[q].append(p)

    gt = defaultdict(list)
    for r, s in RS:
        gt[r].append(s)
        gt[s].append(r)

    ccr = {}
    unused = set(gr.keys())
    while unused:
        q = [unused.pop()]
        con = set([])
        while q:
            v = q.pop()
            con.add(v)
            for u in gr[v]:
                if u in unused:
                    q.append(u)
                    unused.remove(u)
        for v in con:
            ccr[v] = con

    cct = {}
    unused = set(gt.keys())
    while unused:
        q = [unused.pop()]
        con = set([])
        while q:
            v = q.pop()
            con.add(v)
            for u in gt[v]:
                if u in unused:
                    q.append(u)
                    unused.remove(u)
        for v in con:
            cct[v] = con

    cache = {}

    def cc(t, r):
        k = (id(t), id(r))
        if k not in cache:
            cache[k] = len(t & r)
        return cache[k]

    ans = []
    for i in range(1, N+1):
        if i in cct and i in ccr:
            a = cc(cct[i], ccr[i])
        else:
            a = 1
        ans.append(a)
    return " ".join(map(str, ans))


def main():
    N, K, L = read_int_n()
    PQ = [read_int_n() for _ in range(K)]
    RS = [read_int_n() for _ in range(L)]

    print(slv(N, K, L, PQ, RS))


if __name__ == '__main__':
    main()

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, L, PQ, RS):
    ans = 0
    gr = defaultdict(list)
    for p, q in PQ:
        gr[p].append(q)
        gr[q].append(p)

    gt = defaultdict(list)
    for r, s in RS:
        gt[r].append(s)
        gt[s].append(r)

    ccr = {}
    unused = set(gr.keys())
    while unused:
        q = [unused.pop()]
        con = set([])
        while q:
            v = q.pop()
            con.add(v)
            for u in gr[v]:
                if u in unused:
                    q.append(u)
                    unused.remove(u)
        for v in con:
            ccr[v] = con

    cct = {}
    unused = set(gt.keys())
    while unused:
        q = [unused.pop()]
        con = set([])
        while q:
            v = q.pop()
            con.add(v)
            for u in gt[v]:
                if u in unused:
                    q.append(u)
                    unused.remove(u)
        for v in con:
            cct[v] = con

    cache = {}

    def cc(t, r):
        k = (id(t), id(r))
        if k not in cache:
            cache[k] = len(t & r)
        return cache[k]

    ans = []
    for i in range(1, N+1):
        if i in cct and i in ccr:
            a = cc(cct[i], ccr[i])
        else:
            a = 1
        ans.append(a)
    return " ".join(map(str, ans))


def main():
    N, K, L = read_int_n()
    PQ = [read_int_n() for _ in range(K)]
    RS = [read_int_n() for _ in range(L)]

    print(slv(N, K, L, PQ, RS))


if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter
class UnionFind:
    

    def __init__(self, n):
        
        self.par = [i for i in range(n)]
        
        self.rank = [0] * n

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

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

    def union(self, x, y):
        
        
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


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

for i in range(K):
    pi, qi = map(lambda x: int(x) - 1, input().split())
    road.union(pi, qi)

for i in range(L):
    ri, si = map(lambda x: int(x) - 1, input().split())
    rail.union(ri, si)


road_and_rail = [(road.find(i), rail.find(i)) for i in range(N)]
count = Counter(road_and_rail)

ans = []
for i in range(N):
    ans.append(str(count.get(road_and_rail[i])))
print(' '.join(ans))

Solution (Python):
from collections import defaultdict
N, K, L = map(int, input().split())
G = [[[], []] for i in range(N)]
R = [[i, i] for i in range(N)]
def root(i, j):
  if R[i][j] != i:
    R[i][j] = root(R[i][j], j)
  return R[i][j]
for i in range(K):
  p, q = map(int, input().split())
  rp = root(p - 1, 0)
  rq = root(q - 1, 0)
  if rp != rq:
    R[rp][0] = min(rp, rq)
    R[rq][0] = min(rp, rq)
for i in range(L):
  r, s = map(int, input().split())
  rr = root(r - 1, 1)
  rs = root(s - 1, 1)
  if rr != rs:
    R[rr][1] = min(rr, rs)
    R[rs][1] = min(rr, rs)
A = defaultdict(int)
for i in range(N):
  R[i][0] = root(i, 0)
  R[i][1] = root(i, 1)
  A[(R[i][0], R[i][1])] += 1
for i in range(N):
  print(A[(R[i][0], R[i][1])])

Solution (Python):
from collections import defaultdict

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


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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x

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


uf1 = UnionFind(N)
for i in range(K):
    p, q = map(int, input().split())
    uf1.union(p - 1, q - 1)

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


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

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

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

    def union(self, x, y):
        x = self.root(x)
        y = self.root(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(self, x, y):
        return self.root(x) == self.root(y)

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

for _ in range(K):
    p,q = map(int,input().split())
    ufa.union(p,q)
for _ in range(L):
    r,s = map(int,input().split())
    ufb.union(r,s)

pairs = {}
for i in range(1,N+1):
    key = (ufa.root(i),ufb.root(i))
    if  key in pairs.keys():
        pairs[key] +=1
    else:
        pairs[key] =1
ans = []
for i in range(1,N+1):
    key = (ufa.root(i),ufb.root(i))
    ans.append(str(pairs[key]))
print(' '.join(ans))

Solution (Python):
from collections import deque

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

def get_groups(n, m):
    road = [[] for _ in range(n+1)]
    for _ in range(m):
        p, q = list(map(int, input().split()))
        road[p].append(q)
        road[q].append(p)

    groups = [0]*(n+1)
    group_idx = 1
    connect = deque()
    for i in range(1, n+1):
        if groups[i] == 0:
            groups[i] = group_idx
            connect.clear()
            connect.append(i)
            while len(connect) > 0:
                cnct = connect.popleft()
                for c in road[cnct]:
                    if groups[c] == 0:
                        groups[c] = group_idx
                        connect.append(c)
            group_idx += 1
            
    return groups

road_groups = get_groups(n, k)
train_groups = get_groups(n, l)

pairs = {}
for c in range(1, n+1):
    key = (road_groups[c], train_groups[c])
    if not key in pairs.keys():
        pairs[key] = 1
    else:
        pairs[key] += 1

ans = []
for c in range(1, n+1):
    key = (road_groups[c], train_groups[c])
    ans.append(str(pairs[key]))
print(' '.join(ans))

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):
N, k, l = map(int, input().split())


class Uf:
    def __init__(self):
        self.Par = list(range(N + 1))

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

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

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


K = Uf()
L = Uf()
for i in range(k):
    K.unite(*map(int, input().split()))
for i in range(l):
    L.unite(*map(int, input().split()))
U = [[i, K.root(i), L.root(i)] for i in range(1, N+1)]
from operator import itemgetter
U.sort(key=itemgetter(1, 2))
i = 0
while i < N:
    n = 1
    while i+n < N:
        if U[i+n][1:3] == U[i][1:3]:
            n += 1
        else:
            break
    for j in range(n):
        U[i+j].append(n)
    i += n
U.sort(key=itemgetter(0))
A = [u[3] for u in U]
print(" ".join(map(str, A)))

Solution (Python):
n, k, l = [int(i) for i in input().split()]
P = [[int(i) for i in input().split()] for j in range(k)]
R = [[int(i) for i in input().split()] for j in range(l)]

class UnionFind():
  def __init__(self, elements):
    self.elements = elements
    self._root = {}
    for e in self.elements:
      self._root[e] = e
    
  def unite(self, x, y):
    x = self.root(x)
    y = self.root(y)
    if x != y:
      self._root[x] = y
    
  def root(self, x):
    if self._root[x] != x:
      self._root[x] = self.root(self._root[x])
    return self._root[x]
  
  def count(self):
    cnt = {}
    for e in self.elements:
      cnt[self.root(e)] += cnt.get(self.root(e), 0)
      
    for e in self.elements:
      yield cnt.get(e, 0)
      
  def get_union(self):
    union = {}
    for e in self.elements:
      if self.root(e) in union:
        union[self.root(e)].add(e)
      else:
        union[self.root(e)] = {e}
    return union
      
  
road = UnionFind(range(1, n+1))
rail = UnionFind(range(1, n+1))

for i in range(k):
  road.unite(P[i][0], P[i][1])
  
for i in range(l):
  rail.unite(R[i][0], R[i][1])

ans = {}
key = []
for e in range(1, n+1):
  key.append((road.root(e), rail.root(e)))
  ans[key[-1]] = ans.get(key[-1], 0) +1
  
for k in key:
  print(ans[k], end=' ')

Solution (Python):
n, k, l = [int(i) for i in input().split()]
P = [[int(i) for i in input().split()] for j in range(k)]
R = [[int(i) for i in input().split()] for j in range(l)]

class UnionFind():
  def __init__(self, elements):
    self.elements = elements
    self._root = {}
    for e in self.elements:
      self._root[e] = e
    
  def unite(self, x, y):
    x = self.root(x)
    y = self.root(y)
    if not x == y:
      self._root[x] = y
    
  def root(self, x):
    if not self._root[x] == x:
      self._root[x] = self.root(self._root[x])
    return self._root[x]
  
  def count(self):
    cnt = {}
    for e in self.elements:
      cnt[self.root(e)] += cnt.get(self.root(e), 0)
      
    for e in self.elements:
      yield cnt.get(e, 0)
      
  def get_union(self):
    union = {}
    for e in self.elements:
      if self.root(e) in union:
        union[self.root(e)].add(e)
      else:
        union[self.root(e)] = {e}
    return union
      
  
road = UnionFind(range(1, n+1))
rail = UnionFind(range(1, n+1))

for i in range(k):
  road.unite(P[i][0], P[i][1])
  
for i in range(l):
  rail.unite(R[i][0], R[i][1])

ans = {}
key = []
for e in range(1, n+1):
  key.append((road.root(e), rail.root(e)))
  ans[key[-1]] = ans.get(key[-1], 0) +1
  
for k in key:
  print(ans[k], end=' ')

Solution (Python):
import sys
import itertools
from collections import defaultdict

sys.setrecursionlimit(10**8)

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

def union(x,y,table,rank):	
	x = find(x,table)	
	y = find(y,table)
	
	if x == y:
		return
	
	if rank[x] > rank[y]:
		table[y] = x
	else:
		table[x] = y
		if rank[x] == rank[y]:
			rank[y] += 1

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

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

table_car = [i for i in range(N)]	
rank_car  = [1 for i in range(N)]	
table_tr  = [i for i in range(N)] 
rank_tr   = [1 for i in range(N)]

for i in range(0,K):
	a,b = map(int, input().split())
	union(a-1,b-1,table_car,rank_car)
	
for i in range(0,L):
	a,b = map(int, input().split())
	union(a-1,b-1,table_tr,rank_tr)
	
ar = [(find(i,table_car),find(i,table_tr)) for i in range(N)]
dd = defaultdict(int)
for s in ar:
    dd[s] += 1
	
ans =[]
for i in range(N):
    ans.append(dd[ar[i]])
	
print(' '.join(map(str, ans)))

Solution (Python):
from collections import defaultdict

class Unionfindtree:
    def __init__(self,number):
        self.par = [i for i in range(number)]
        self.rank = [0]*(number)

    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):
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return 
        if self.rank[px]<self.rank[py]:
            self.par[px]=py
        else:
            self.par[py]=px
        if self.rank[px]==self.rank[py]:
            self.rank[px] +=1
    
    def connect(self,x,y):
        return self.find(x)==self.find(y)

N,K,L = map(int,input().split())
load = Unionfindtree(N)
train = Unionfindtree(N)
for i in range(K):
    a,b = map(int,input().split())
    load.union(a-1,b-1)
for i in range(L):
    a,b = map(int,input().split())
    train.union(a-1,b-1)

ar = [(load.find(i),train.find(i)) for i in range(N)]

dd = defaultdict(int)
for s in ar:
    dd[s] += 1
ans =[]
for i in range(N):
    ans.append(dd[ar[i]])
print(' '.join(map(str, ans)))

Solution (Python):
import sys
sys.setrecursionlimit(20000)

n, k, l = map(int, input().split())
a = [list() for _ in range(n)]
b = [list() for _ in range(n)]
for _ in range(k):
    p, q = [int(x) - 1 for x in input().split()]
    a[p].append(q)
    a[q].append(p)
for _ in range(l):
    r, s = [int(x) - 1 for x in input().split()]
    b[r].append(s)
    b[s].append(r)

def g(a, b, i, k):
    b[i] = k
    for e in a[i]:
        if b[e] is not None: continue
        g(a, b, e, k)

def f(a, b):
    k = 0
    for i in range(n):
        if b[i] is not None: continue
        g(a, b, i, k)
        k += 1

c = [None] * n
f(a, c)
d = [None] * n
f(b, d)
e = {}
for i in range(n):
    k = (c[i], d[i])
    e[k] = e.get(k, 0) + 1

print(' '.join([str(e[(c[i], d[i])]) for i in range(n)]))

Solution (Python):
from collections import Counter
n,k,l = (int(i) for i in input().split())
rpar,tpar,x = [i for i in range(n+1)],[i for i in range(n+1)],[]
def root(x,par):
	if par[x]!=x: par[x] = root(par[x],par)
	return par[x]
def unite(x,y,par):
	x2,y2 = root(x,par),root(y,par)
	if x2==y2: return
	par[x2] = y2
r = [[int(i) for i in input().split()] for i in range(k)]
t = [[int(i) for i in input().split()] for i in range(l)]
for i,j in r: unite(i,j,rpar)
for i,j in t: unite(i,j,tpar)
for i in range(1,n+1): x.append((root(i,rpar),root(i,tpar)))
y = Counter(x)
for i in x: print(y[i],end=" ")

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

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 unite(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 check(self, x, y):
        return self.find(x) == self.find(y)

P,Q = UnionFind(N),UnionFind(N)
for _ in range(K):
    x,y = map(int,input().split())
    P.unite(x,y)
for _ in range(L):
    x,y = map(int,input().split())
    Q.unite(x,y)

D = defaultdict(int)
for i in range(1,N+1):
    D[P.find(i),Q.find(i)] += 1

print(" ".join(map(str,list(D[P.par[i],Q.par[i]] for i in range(1,N+1)))))

Solution (Python):
from collections import defaultdict

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

class UnionFind(object):
  def __init__(self,n):
    self.table=[-1]*n
 
  def find(self,x):
    parent=self.table[x]
    if parent<0:
      return x
    else:
      root=self.find(parent)
      self.table[x]=root
      return root
 
  def union(self,a,b):
    root1=self.find(a)
    root2=self.find(b)
    if root1 != root2:
      if self.table[root1] != self.table[root2]:
        if self.table[root1] < self.table[root2]:
          self.table[root2]=root1
        else:
          self.table[root1]=root2
      else:
        self.table[root1]+=(-1)
        self.table[root2]=root1
      
ufK=UnionFind(N)
for i in range(K):
  p,q=map(int,input().split())
  ufK.union(p-1,q-1)

ufL=UnionFind(N)
for i in range(L):
  p,q=map(int,input().split())
  ufL.union(p-1,q-1)

KL=defaultdict(int)
ans=[]
for i in range(N):
  a=ufK.find(i)
  b=ufL.find(i)
  KL[(a,b)]+=1
for i in range(N):
  a=ufK.find(i)
  b=ufL.find(i)
  ans.append(KL[(a,b)])
  
print(*ans)

Solution (Python):
class UnionFind(object):

    def __init__(self, n):
        
        self.par = [i for i in range(n)]

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

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

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

        self.par[x] = y


class UnionFindRank(UnionFind):

    def __init__(self, n):
        UnionFind.__init__(self, n)

        self.rank = [0 for _ in range(n)]

    def union(self, x, y):
        x = self.root(x)
        y = self.root(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 _abc049_d():
    """連結"""

    N, K, L = list(map(int, input().split(' ')))
    ur = UnionFindRank(N)
    for _ in range(K):
        p, q = list(map(int, input().split(' ')))
        p -= 1
        q -= 1
        ur.union(p, q)

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

    def _id(r, t):
        return r * 1e8 + t

    from collections import defaultdict
    d = defaultdict(int)

    ids = []
    for i in range(N):
        __id = _id(ur.root(i), ut.root(i))
        d[__id] += 1
        ids.append(__id)

    for i in range(N):
        print(d[ids[i]], end=' ')

_abc049_d()

Solution (Python):
class UnionFind(object):

    def __init__(self, n):
        
        self.par = [i for i in range(n)]

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

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

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

        self.par[x] = y


class UnionFindRank(UnionFind):

    def __init__(self, n):
        UnionFind.__init__(self, n)

        self.rank = [0 for _ in range(n)]

    def union(self, x, y):
        x = self.root(x)
        y = self.root(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 _abc049_d():
    """連結"""

    N, K, L = list(map(int, input().split(' ')))
    ur = UnionFindRank(N)
    for _ in range(K):
        p, q = list(map(int, input().split(' ')))
        p -= 1
        q -= 1
        ur.union(p, q)

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

    def _id(r, t):
        return r * 1e8 + t

    from collections import defaultdict
    d = defaultdict(int)

    ids = []
    for i in range(N):
        __id = _id(ur.root(i), ut.root(i))
        d[__id] += 1
        ids.append(__id)

    for i in range(N):
        print(d[ids[i]], end=' ')

_abc049_d()