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


"""
参考：https://img.atcoder.jp/arc065/editorial.pdf
・Union-Find木
"""

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

from collections import Counter


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

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


pairs = [None] * N
for i in range(N):
    pairs[i] = (uf1.find(i+1), uf2.find(i+1))


c = Counter(pairs)

ans = [0] * N
for i in range(N):
    
    ans[i] = c[pairs[i]]
print(*ans)

Solution (Python):
def find(parents, x):
    if parents[x] == x:
        return x
    else:
        parents[x] = find(parents, parents[x])
        return parents[x]

def union(parents, x1, x2):
    y1 = find(parents, x1)
    y2 = find(parents, x2)
    if y1 != y2:
        parents[y1] = y2


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

parents1 = list(range(n))
for _ in range(k):
    p, q = map(int, input().split())
    union(parents1, p - 1, q - 1)

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

import collections

counter = collections.defaultdict(int)
for i in range(n):
    p1, p2 = find(parents1, i), find(parents2, i)
    counter[(p1, p2)] += 1

ans = ' '.join(str(counter[(find(parents1, i), find(parents2, i))]) for i in range(n))
print(ans)

Solution (Python):
import collections
N,K,L = map(int, input().split())
p = []
q = []
for i in range(K):
    pi, qi = map(int, input().split())
    p.append(pi)
    q.append(qi)
r = []
s = []
for i in range(L):
    ri, si = map(int, input().split())
    r.append(ri)
    s.append(si)

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)

u = UnionFind(N)
for i in range(K):
    u.union(p[i],q[i])


u2 = UnionFind(N)
for i in range(L):
    u2.union(r[i],s[i])

li = [None]*(N)
liw = [None]*(N)
for i in range(N):
    li[i] = (u.find(i + 1), u2.find(i + 1), i + 1)
    liw[i] = (u.find(i + 1), u2.find(i + 1))


liws = collections.Counter(liw)

ansli = [0]*(N+1)
for i in range(N):
    ansli[i + 1] = liws[(li[i][0], li[i][1])]

for i in range(1, N + 1):
    print(ansli[i], "", end="")

Solution (Python):
N, K, L = [int(_) for _ in input().split()]


def find(a, x):
    stack = []
    while a[x] != x:
        stack += [x]
        x = a[x]
    while stack:
        a[stack.pop()] = x
    return x


def unite(a, x, y):
    x = find(a, x)
    y = find(a, y)
    if x != y:
        a[x] = min(x, y)
        a[y] = a[x]


a_road = [i for i in range(N)]
for _ in range(K):
    p, q = [int(_) - 1 for _ in input().split()]
    unite(a_road, p, q)
a_railway = [i for i in range(N)]
for _ in range(L):
    r, s = [int(_) - 1 for _ in input().split()]
    unite(a_railway, r, s)
memo = {}
for i in range(N):
    memo[a_road[i], a_railway[i]] = memo.get(
        (find(a_road, i), find(a_railway, i)), 0) + 1

print(' '.join(str(memo[a_road[i], a_railway[i]]) for i in range(N)))

Solution (Python):
N, K, L = [int(_) for _ in input().split()]


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


def unite(a, x, y):
    x = find(a, x)
    y = find(a, y)
    if x != y:
        a[x] = min(x, y)
        a[y] = a[x]


a_road = [i for i in range(N)]
for _ in range(K):
    p, q = [int(_) - 1 for _ in input().split()]
    unite(a_road, p, q)
a_railway = [i for i in range(N)]
for _ in range(L):
    r, s = [int(_) - 1 for _ in input().split()]
    unite(a_railway, r, s)
memo = {}
for i in range(N):
    memo[a_road[i], a_railway[i]] = memo.get(
        (find(a_road, i), find(a_railway, i)), 0) + 1

print(' '.join(str(memo[a_road[i], a_railway[i]]) for i in range(N)))

Solution (Python):
from collections import Counter
def find(x):
  if x==Tree[x]:
      return x
  else:
      Tree[x]=find(Tree[x])
      return Tree[x]
def unite(x,y):
  s1=find(x)
  s2=find(y)
  if s1!=s2:
    Tree[s2]=s1
def find2(x):
  if x==Tree2[x]:
      return x
  else:
      Tree2[x]=find2(Tree2[x])
      return Tree2[x]
def unite2(x,y):
  s1=find2(x)
  s2=find2(y)
  if s1!=s2:
    Tree2[s2]=s1
N,K,L=map(int,input().split())
Tree=[i for i in range(N)]
Tree2=[i for i in range(N)]
ans=[]
for i in range(K):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  unite(a,b)
for i in range(L):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  unite2(a,b)
l=[(find(i),find2(i)) for i in range(N)]
lc=Counter(l)
for i in range(N):
  ans.append(lc[l[i]])
print(" ".join(map(str,ans)))

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)]
        self.rank = [0] * n
        self.size = [1] * n

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

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

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
            self.size[x] = 0
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

    
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)


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

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

D = defaultdict(int)
for r, t in zip(UF_road.par, UF_train.par):
    D[(r, t)] += 1

ans = [D[(r, t)] for r, t in zip(UF_road.par, UF_train.par)]
print(*ans, sep=' ')

Solution (Python):
import sys
from collections import Counter

sys.setrecursionlimit(10 ** 5)


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

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

        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


N, K, L = map(int, input().split())
r_union_find = UnionFind(N)
t_union_find = UnionFind(N)
for i in range(K):
    p, q = map(int, input().split())
    r_union_find.union(p, q)

for i in range(L):
    r, s = map(int, input().split())
    t_union_find.union(r, s)

pair = []

for i in range(1, N + 1):
    count = 0
    r_p = r_union_find.find(i)
    t_p = t_union_find.find(i)
    pair.append((r_p, t_p))

counter = Counter(pair)

answers = []
for p in pair:
    answers.append(counter[p])

answers = map(str, answers)
print(" ".join(answers))

Solution (Python):
import sys
from collections import Counter

sys.setrecursionlimit(10 ** 5)


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

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

        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


N, K, L = map(int, input().split())
r_union_find = UnionFind(N)
t_union_find = UnionFind(N)
for i in range(K):
    p, q = map(int, input().split())
    r_union_find.union(p, q)

for i in range(L):
    r, s = map(int, input().split())
    t_union_find.union(r, s)

pair = []

for i in range(1, N + 1):
    count = 0
    r_p = r_union_find.find(i)
    t_p = t_union_find.find(i)
    pair.append((r_p, t_p))

counter = Counter(pair)

answers = []
for p in pair:
    answers.append(counter[p])

answers = map(str, answers)
print(" ".join(answers))

Solution (Python):
N, K, L = [int(_) for _ in input().split()]
V1 = [[int(_) - 1 for _ in input().split()] for i in range(K)]
V2 = [[int(_) - 1 for _ in input().split()] for i in range(L)]


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

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

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


uf1 = UnionFind(N)
for p, q in V1:
    uf1.union(p, q)

uf2 = UnionFind(N)
for r, s in V2:
    uf2.union(r, s)

from collections import defaultdict
d = defaultdict(int)

for i in range(N):
    d[(uf1.find(i), uf2.find(i))] += 1

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

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)


A = UnionFind(N)
for i in range(K):
    x,y = map(int,input().split())
    A.unite(x,y)


B = UnionFind(N)
for i in range(L):
    x,y = map(int,input().split())
    B.unite(x,y)

dic = defaultdict(int)
for i in range(1,N+1):
    dic[A.find(i),B.find(i)] += 1

Ans = list(dic[A.par[i],B.par[i]] for i in range(1,N+1))
print(" ".join(map(str,Ans)))

Solution (Python):
class DisjointSet:
    def __init__(self):
        self.rank = {}
        self.p = {}

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

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

    def unite(self, x, y):
        self.link(self.findSet(x), self.findSet(y))

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

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

from collections import Counter
N, K, L = map(int, input().split())

ds = DisjointSet()
ds2 = DisjointSet()
for i in range(N):
    ds.makeSet(i+1)
    ds2.makeSet(i+1)

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

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

a = [(ds.findSet(i), ds2.findSet(i)) for i in range(1, N+1)]
c = Counter(a)

print(' '.join([str(c[i]) for i in a]))

Solution (Python):
class DisjointSet:
    def __init__(self):
        self.rank = {}
        self.p = {}

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

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

    def unite(self, x, y):
        self.link(self.findSet(x), self.findSet(y))

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

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

from collections import Counter
N, K, L = map(int, input().split())

ds = DisjointSet()
ds2 = DisjointSet()
for i in range(N):
    ds.makeSet(i+1)
    ds2.makeSet(i+1)

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

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

a = [(ds.findSet(i), ds2.findSet(i)) for i in range(1, N+1)]
c = Counter(a)

print(' '.join([str(c[i]) for i in a]))

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



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

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

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

def uniteOne(num, uf):
    for _ in range(num):
        d0, d1 = map(int, input().split())
        uf.unite(d0-1, d1-1)
        
uf_D = UnionFind(N)
uf_T = UnionFind(N)

uniteOne(K, uf_D)
uniteOne(L, uf_T)

pairs = []
for i in range(N):
    pairs.append((uf_D.find_root(i), uf_T.find_root(i)))
 
pairs_count = {}
for p in pairs:
    if not p in pairs_count:
        pairs_count[p] = 1
    else:
        pairs_count[p] += 1
 
res = [0] * N
for i in range(N):
    res[i] = pairs_count[pairs[i]]

print(" ".join([str(i) for i in res]))

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



class UnionFind:
    def __init__(self, n: int) -> None:
        self.par = [i for i in range(n)]
        self.rank = [0] * n

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

    def unite(self, x: int, y: int) -> None:
        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 uniteOne(num, uf):
    for _ in range(num):
        d0, d1 = map(int, input().split())
        uf.unite(d0-1, d1-1)
        
uf_D = UnionFind(N)
uf_T = UnionFind(N)

uniteOne(K, uf_D)
uniteOne(L, uf_T)

from collections import Counter

keys = []
counts = Counter()

for i in range(N):
    key = uf_D.find(i), uf_T.find(i)
    keys.append(key)
    counts[key] += 1

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

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



class UnionFind:
    def __init__(self, n: int) -> None:
        self.par = [i for i in range(n)]
        self.rank = [0] * n

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

    def unite(self, x: int, y: int) -> None:
        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 uniteOne(num, uf):
    for _ in range(num):
        d0, d1 = map(int, input().split())
        uf.unite(d0-1, d1-1)
        
uf_D = UnionFind(N)
uf_T = UnionFind(N)

uniteOne(K, uf_D)
uniteOne(L, uf_T)

pairs = []
for i in range(N):
    pairs.append((uf_D.find(i), uf_T.find(i)))

pairs_count = {}
for p in pairs:
    if not p in pairs_count:
        pairs_count[p] = 1
    else:
        pairs_count[p] += 1

res = [0] * N
for i in range(N):
    res[i] = pairs_count[pairs[i]]

print(" ".join([str(i) for i in res]))

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



class UnionFind:
    def __init__(self, n: int) -> None:
        self.par = [i for i in range(n)]
        self.rank = [0] * n

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

    def unite(self, x: int, y: int) -> None:
        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
        
    
    
    

uf_D = UnionFind(N)
uf_T = UnionFind(N)

for d0, d1 in (map(int, input().split()) for _ in range(K)):
    uf_D.unite(d0-1, d1-1)
for d0, d1 in (map(int, input().split()) for _ in range(L)):
    uf_T.unite(d0-1, d1-1)

pairs = []
for i in range(N):
    pairs.append((uf_D.find(i), uf_T.find(i)))

pairs_count = {}
for p in pairs:
    if not p in pairs_count:
        pairs_count[p] = 1
    else:
        pairs_count[p] += 1

res = [0] * N
for i in range(N):
    res[i] = pairs_count[pairs[i]]

print(" ".join([str(i) for i in res]))

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

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



class UnionFind:
    def __init__(self, n: int) -> None:
        self.par = [i for i in range(n)]
        self.rank = [0] * n

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

    def unite(self, x: int, y: int) -> None:
        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 uniteOne(num, uf):
    for _ in range(num):
        d0, d1 = map(int, input().split())
        d0 = d0 - 1
        d1 = d1 - 1
        uf.unite(d0, d1)

uf_D = UnionFind(N)
uf_T = UnionFind(N)

uniteOne(K, uf_D)
uniteOne(L, uf_T)


pairs = []
for i in range(N):
    pairs.append((uf_D.find(i), uf_T.find(i)))

pairs_count = {}
for p in pairs:
    if not p in pairs_count:
        pairs_count[p] = 1
    else:
        pairs_count[p] += 1

res = [0] * N
for i in range(N):
    res[i] = pairs_count[pairs[i]]

print(" ".join([str(i) for i in res]))

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

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



class UnionFind:
    def __init__(self, n):
        self.par = [i for i 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.par[x]

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

def execOne(num, uf):
    for _ in range(num):
        d0, d1 = map(int, input().split())
        d0 = d0 - 1
        d1 = d1 - 1
        uf.union(d0, d1)

uf_D = UnionFind(N)
uf_T = UnionFind(N)

execOne(K, uf_D)
execOne(L, uf_T)


pairs = []
for i in range(N):
    pairs.append((uf_D.find(i), uf_T.find(i)))

pairs_count = {}
for p in pairs:
    if not p in pairs_count:
        pairs_count[p] = 1
    else:
        pairs_count[p] += 1

res = [0] * N
for i in range(N):
    res[i] = pairs_count[pairs[i]]

print(" ".join([str(i) for i in res]))

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

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

def execOne(num, uf):
    for _ in range(num):
        d0, d1 = map(int, input().split())
        d0 = d0 - 1
        d1 = d1 - 1
        uf.union(d0, d1)

uf_D = UnionFind(N)
uf_T = UnionFind(N)

execOne(K, uf_D)
execOne(L, uf_T)


pairs = []
for i in range(N):
    pairs.append((uf_D.find(i), uf_T.find(i)))

pairs_count = {}
for p in pairs:
    if not p in pairs_count:
        pairs_count[p] = 1
    else:
        pairs_count[p] += 1

res = [0] * N
for i in range(N):
    res[i] = pairs_count[pairs[i]]

print(" ".join([str(i) for i in res]))

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

N,K,L=map(int,input().split())
R=[list(map(int,input().split())) for i in range(K)]
T=[list(map(int,input().split())) for i in range(L)]

Group1=[i for i in range(N+1)]
Group2=[i for i in range(N+1)]

def find1(x):
    while Group1[x] != x:
        x=Group1[x]
    return x

def Union1(x,y):
    if find1(x) != find1(y):
        Group1[find1(y)]=Group1[find1(x)]=min(find1(y),find1(x))

def find2(x):
    while Group2[x] != x:
        x=Group2[x]
    return x

def Union2(x,y):
    if find2(x) != find2(y):
        Group2[find2(y)]=Group2[find2(x)]=min(find2(y),find2(x))

for i,j in R:
    Union1(i,j)

for i,j in T:
    Union2(i,j)

from collections import defaultdict
ANS = defaultdict(int)

for i in range(1,N+1):
    ANS[(find1(i),find2(i))]+=1

for i in range(1,N+1):
    print(ANS[(find1(i),find2(i))])

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

sys.setrecursionlimit(10000)

N, K, L = (int(i) for i in input().split())

import collections
import itertools
import operator

class UnionFind:
    def __init__(self, elems=None):
        class KeyDict(dict):
            def __missing__(self, key):
                self[key] = key
                return key

        self.parent = KeyDict()
        self.rank = collections.defaultdict(int)

        if elems is not None:
            for elem in elems:
                _, _ = self.parent[elem], self.rank[elem]

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

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

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

    def grouper(self):
        roots = [(x, self.find(x_par)) for x, x_par in self.parent.items()]
        root = operator.itemgetter(1)
        for _, group in itertools.groupby(sorted(roots, key=root), root):
            yield [x for x, _ in group]

ufk = UnionFind()
for i in range(K):
    a, b = (int(i) for i in input().split())
    ufk.unite(a, b)

ufl = UnionFind()
for i in range(L):
    a, b = (int(i) for i in input().split())
    ufl.unite(a, b)

L = []
for i in range(1,N+1):
    L.append( (ufk.find(i), ufl.find(i), i) )

def countList(L, ma = None):
    if ma == None:
        ma = len(L)
    L.sort() 
    temp = (None, None, None)
    cc = 1
    reslis = [0] * (N+1)
    v = [L[0][2]]
    for se in L:
        if temp[0] == se[0] and temp[1] == se[1]:
            cc += 1
            v.append(se[2])
        else:
            if temp[0] == None:
                pass
            else:
                for aa in v:
                    reslis[aa] = cc
                v = [se[2]]
                cc = 1
            temp = se
    for aa in v:
        reslis[aa] = cc
    return reslis

reslis = countList(L, N)
reslis = reslis[1:]
reslis = [str(i) for i in reslis]
print(" ".join(reslis))

Solution (Python):
def root(parents, i):
    if parents[i] == i:
        return i
    parents[i] = root(parents, parents[i])
    return parents[i]


def main():
    n, k, l = map(int, input().split())
    roads = list(range(n))
    rails = list(range(n))

    for _ in range(k):
        a, b = map(lambda s: int(s) - 1, input().split())
        root_a, root_b = root(roads, a), root(roads, b)
        if root_a != root_b:
            roads[root_a] = root_b

    for _ in range(l):
        a, b = map(lambda s: int(s) - 1, input().split())
        root_a, root_b = root(rails, a), root(rails, b)
        if root_a != root_b:
            rails[root_a] = root_b

    counts = dict()
    for i in range(n):
        pair = (root(roads, i), root(rails, i))
        if not pair in counts:
            counts[pair] = 1
        else:
            counts[pair] += 1

    print(' '.join(
        map(lambda i: str(counts[(root(roads, i), root(rails, i))]), range(n))))


if __name__ == '__main__':
    main()

Solution (Python):
N, K, L = [int(_) for _ in input().split()]


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


def unite(a, x, y):
    x = find(a, x)
    y = find(a, y)
    if x != y:
        a[x] = min(x, y)
        a[y] = a[x]


a_road = [i for i in range(N)]
for _ in range(K):
    p, q = [int(_) - 1 for _ in input().split()]
    unite(a_road, p, q)
a_railway = [i for i in range(N)]
for _ in range(L):
    r, s = [int(_) - 1 for _ in input().split()]
    unite(a_railway, r, s)
memo = {}
for i in range(N):
    memo[a_road[i], a_railway[i]] = memo.get(
        (find(a_road, i), find(a_railway, i)), 0) + 1

print(' '.join(str(memo[a_road[i], a_railway[i]]) for i in range(N)))

Solution (Python):
N, K, L = [int(_) for _ in input().split()]


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


def unite(a, x, y):
    x = find(a, x)
    y = find(a, y)
    if x != y:
        a[x] = min(x, y)
        a[y] = a[x]


a_road = [i for i in range(N)]
for _ in range(K):
    p, q = [int(_) - 1 for _ in input().split()]
    unite(a_road, p, q)
a_railway = [i for i in range(N)]
for _ in range(L):
    r, s = [int(_) - 1 for _ in input().split()]
    unite(a_railway, r, s)
memo = {}
for i in range(N):
    memo[find(a_road, i), find(a_railway, i)] = memo.get(
        (find(a_road, i), find(a_railway, i)), 0) + 1

print(' '.join(str(memo[a_road[i], a_railway[i]]) for i in range(N)))

Solution (Python):
N, K, L = [int(_) for _ in input().split()]


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


def unite(a, x, y):
    x = find(a, x)
    y = find(a, y)
    if x != y:
        a[x] = max(x, y)
        a[y] = a[x]


a_road = [i for i in range(N)]
for _ in range(K):
    p, q = [int(_) - 1 for _ in input().split()]
    unite(a_road, p, q)
a_railway = [i for i in range(N)]
for _ in range(L):
    r, s = [int(_) - 1 for _ in input().split()]
    unite(a_railway, r, s)
memo = {}
for i in range(N):
    memo[find(a_road, i), find(a_railway, i)] = memo.get(
        (find(a_road, i), find(a_railway, i)), 0) + 1

print(' '.join(str(memo[find(a_road, i), find(a_railway, i)])
               for i in range(N)))

Solution (Python):
N, K, L = [int(_) for _ in input().split()]

par = [i for i in range(2 * N)]
rank = [0] * (2 * N)


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


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

    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1


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


for _ in range(K):
    p, q = [int(_) - 1 for _ in input().split()]
    unite(p, q)
for _ in range(L):
    r, s = [int(_) + N - 1 for _ in input().split()]
    unite(r, s)
memo = {}
for i in range(N):
    memo[find(i), find(i + N)] = memo.get(
        (find(i), find(i + N)), 0) + 1

print(' '.join(str(memo[find(i), find(i + N)])
               for i in range(N)))