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.par = [i for i 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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return

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


n,k,l = map(int, input().split())
pq = UnionFind(n)
for _ in range(k):
    p,q = map(int, input().split())
    pq.unite(p-1,q-1)
rs = UnionFind(n)
for _ in range(l):
    r,s = map(int, input().split())
    rs.unite(r-1,s-1)



d = {}
for x in range(n):
    a = pq.find(x)
    b = rs.find(x)
    if (a,b) not in d:
        d[(a,b)] = 0
    d[(a,b)] += 1

ret = []
for x in range(n):
    a = pq.find(x)
    b = rs.find(x)
    ret.append(str(d[(a,b)]))

print(" ".join(ret  ))

Solution (Python):


def main():
    n, k, l = map(int, input().split())
    pq = get_edges(k)
    rs = get_edges(l)
    road_groups = get_group(n, pq)
    rail_groups = get_group(n, rs)
    count = {}
    for i in range(n):
        gp = (find(i, road_groups), find(i, rail_groups))
        if gp not in count:
            count[gp] = 1
        else:
            count[gp] += 1
    res = []
    for i in range(n):
        gp = (find(i, road_groups), find(i, rail_groups))
        res.append(count[gp])
    print(" ".join(map(str, res)))

def get_edges(k):
    pq = []
    for i in range(k):
        p1, q1 = map(int, input().split())
        pq.append((p1 - 1, q1 - 1))
    return pq

def get_group(n, edges):
    group = [i for i in range(n)]
    for x, y in edges:
        unite(x, y, group)
    return group

def unite(x, y, parents):
    px = find(x, parents)
    py = find(y, parents)
    parents[py] = px

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

main()

Solution (Python):
from collections import Counter

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

def unite(par, x, y):
    rx, ry = root(par, x), root(par, y)
    if rx == ry:
        return

    if rank[rx] > rank[ry]:
        par[ry] = rx
    elif rank[rx] < rank[ry]:
        par[rx] = ry
    else:
        par[ry] = rx
        rank[rx] += 1
        
N, K, L = map(int, input().split())

rank = [1] * N
roads = [i for i in range(N)]
for _ in range(K):
    unite(roads, *map(lambda x: int(x) - 1, input().split()))

rank = [1] * N
rails = [i for i in range(N)]
for _ in range(L):
    unite(rails, *map(lambda x: int(x) - 1, input().split()))

count = Counter((root(roads, i), root(rails, i)) for i in range(N))
print(*(count[root(roads, i), root(rails, i)] for i in range(N)))

Solution (Python):
f = lambda: list(map(int,input().split()))
f_ = lambda: [int(x)-1 for x in input().split()]


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

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

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

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


n,k,l = f()
ud = UnionFind(n)
for _ in range(k):
    p,q = f_()
    ud.unite(p,q)
ut = UnionFind(n)
for _ in range(l):
    p,q = f_()
    ut.unite(p,q)

p = [(ud.find(i),ut.find(i)) for i in range(n)]

from collections import Counter
c = Counter(p)
print(*[c[p[i]] for i in range(n)])

Solution (Python):
from collections import defaultdict

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

class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]






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


	def union(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 != s2:
			if self.table[s1] > self.table[s2]:
				self.table[s2] = s1
			elif self.table[s1] < self.table[s2]:
				self.table[s1] = s2
			else:
				self.table[s1] = s2
				self.table[s2] -= 1
		return

road = UnionFind(n)
train = UnionFind(n)

for _ in range(k):
	a, b = map(int, input().split())
	road.union(a - 1, b - 1)

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

road_root = []
for i in range(n):
	num = road.find(i)
	road_root.append(num)

train_root = []
for i in range(n):
	num = train.find(i)
	train_root.append(num)

count = defaultdict(int)
for i in range(n):
	count[road_root[i] * (10 ** 6) +  train_root[i]] += 1

ans = []
for i in range(n):
	ans.append(count[road_root[i] * (10 ** 6) +  train_root[i]])

print(*ans)

Solution (Python):
N,K,L=map(int,input().split())
G=[[] for i in range(N)]
H=[[] for i in range(N)]


for i in range(K):
    p,q=map(int,input().split())
    G[p-1].append(q-1)
    G[q-1].append(p-1)
for i in range(L):
    r,s=map(int,input().split())
    H[r-1].append(s-1)
    H[s-1].append(r-1)
def dfs(A):
    k=1
    q=[]
    reached=[0 for i in range(N)]
    res=[0 for i in range(N)]
    for i in range(N):
        if reached[i]==1:
            continue
        q.append(i)
        while(len(q)>0):
            r=q[-1]
            q.pop()
            res[r]=k
            for p in A[r]:
                if reached[p]==1:
                    continue
                q.append(p)
                reached[p]=1
        k+=1
    return res
T=dfs(G)
B=dfs(H)
TB=[(T[i],B[i]) for i in range(N)]
D=dict()
for i in range(N):
    if TB[i] in D:
        D[TB[i]]+=1
    else:
        D[TB[i]]=1
ans=[str(D[TB[i]]) for i in range(N)]
print(" ".join(ans))

Solution (Python):
N,K,L=map(int,input().split())
G=[[] for i in range(N)]
H=[[] for i in range(N)]


for i in range(K):
    p,q=map(int,input().split())
    G[p-1].append(q-1)
    G[q-1].append(p-1)
for i in range(L):
    r,s=map(int,input().split())
    H[r-1].append(s-1)
    H[s-1].append(r-1)
def dfs(A):
    k=1
    q=[]
    reached=[0 for i in range(N)]
    res=[0 for i in range(N)]
    for i in range(N):
        if reached[i]==1:
            continue
        q.append(i)
        while(len(q)>0):
            r=q[-1]
            q.pop()
            res[r]=k
            for p in A[r]:
                if reached[p]==1:
                    continue
                q.append(p)
                reached[p]=1
        k+=1
    return res
T=dfs(G)
B=dfs(H)
TB=[(T[i],B[i]) for i in range(N)]
D=dict()
for i in range(N):
    if TB[i] in D:
        D[TB[i]]+=1
    else:
        D[TB[i]]=1
ans=[str(D[TB[i]]) for i in range(N)]
print(" ".join(ans))

Solution (Python):
N,K,L=map(int,input().split())
G=[[] for i in range(N)]
H=[[] for i in range(N)]


for i in range(K):
    p,q=map(int,input().split())
    G[p-1].append(q-1)
    G[q-1].append(p-1)
for i in range(L):
    r,s=map(int,input().split())
    H[r-1].append(s-1)
    H[s-1].append(r-1)
def bfs(A):
    k=1
    q=[]
    reached=[0 for i in range(N)]
    res=[0 for i in range(N)]
    for i in range(N):
        if reached[i]==1:
            continue
        q.append(i)
        while(len(q)>0):
            r=q[-1]
            q.pop()
            res[r]=k
            for p in A[r]:
                if reached[p]==1:
                    continue
                q.append(p)
                reached[p]=1
        k+=1
    return res
T=bfs(G)
B=bfs(H)
TB=[(T[i],B[i]) for i in range(N)]
D=dict()
for i in range(N):
    if TB[i] in D:
        D[TB[i]]+=1
    else:
        D[TB[i]]=1
ans=[str(D[TB[i]]) for i in range(N)]
print(" ".join(ans))

Solution (Python):
from collections import deque

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

G = [[[] for j in range(N)] for i in range(2)]
check = [[0 for l in range(N)] for k in range(2)]


def bfs(s, cnt, mode):
    q = deque()
    q.append(s)
    check[mode][s] = cnt

    while len(q) != 0:
        u = q.popleft()
        for i in G[mode][u]:
            if check[mode][i] == 0:
                q.append(i)
                check[mode][i] = cnt


def main():
    for i in range(K):
        p, q = map(int, input().split())
        G[0][p-1].append(q-1)
        G[0][q-1].append(p-1)
    for i in range(L):
        r, s = map(int, input().split())
        G[1][r-1].append(s-1)
        G[1][s-1].append(r-1)

    cnt = 1
    for i in range(N):
        if check[0][i] == 0:
            bfs(i, cnt, 0)
            cnt += 1

    cnt = 1
    for i in range(N):
        if check[1][i] == 0:
            bfs(i, cnt, 1)
            cnt += 1

    groups = {}
    for i in range(N):
        a, b = check[0][i], check[1][i]
        groups[(a, b)] = groups.get((a, b), 0) + 1

    nums = []
    for i in range(N):
        a, b = check[0][i], check[1][i]
        nums.append(str(groups[(a, b)]))

    print(" ".join(nums))


if __name__ == '__main__':
    main()

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)


UF1 = UnionFind(N)
UF2 = UnionFind(N)

for k in range(K):
    p, q = map(int, input().split())
    p, q = p-1, q-1
    UF1.union(p, q)
for l in range(L):
    r, s = map(int, input().split())
    r, s = r-1, s-1
    UF2.union(r, s)

UF1.all_find()
UF2.all_find()

D = defaultdict(int)
for p1, p2 in zip(UF1.par, UF2.par):
    D[(p1, p2)] += 1

ans = [D[(p1, p2)] for p1, p2 in zip(UF1.par, UF2.par)]
print(*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_check(self, x, y):
        return self.find(x) == self.find(y)

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


UF1 = UnionFind(N)
UF2 = UnionFind(N)

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

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

UF1.all_find()
UF2.all_find()

D = defaultdict(int)
for i in range(N):
    D[UF1.par[i], UF2.par[i]] += 1

ans = [D[UF1.par[i], UF2.par[i]] for i in range(N)]
print(*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_check(self, x, y):
        return self.find(x) == self.find(y)

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


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

for l in range(L):
    l, s = map(int, input().split())
    UF2.union(l-1, s-1)

UF1.all_find()
UF2.all_find()

D = defaultdict(int)
for i in range(N):
    D[UF1.par[i], UF2.par[i]] += 1

ans = [D[UF1.par[i], UF2.par[i]] for i in range(N)]
print(" ".join(map(str, ans)))

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

def rr(x, gr):
    if x != gr[x]: gr[x] = x = rr(gr[x], gr)
    return x

def g(x, y, gr):
    px = rr(x, gr)
    py = rr(y, gr)
    if px < py:
        gr[py] = px
    else:
        gr[px] = py

roads = range(n)
for _ in range(k):
    p, q = map(int, raw_input().split())
    g(p - 1, q - 1, roads)
for i in range(n): rr(i, roads)

rails = range(n)
for _ in range(l):
    r, s = map(int, raw_input().split())
    g(r - 1, s - 1, rails)
for i in range(n): rr(i, rails)

c = {}
for p1, p2 in zip(roads, rails):
    try:
        c[p1, p2] += 1
    except KeyError:
        c[p1, p2] = 1

ans = [c[p1, p2] for p1, p2 in zip(roads, rails)]
print ' '.join(map(str, ans))

Solution (Python):

from itertools import combinations
from collections import defaultdict
import sys
sys.setrecursionlimit(10000)
def inpl(): return tuple(map(int, input().split()))
 
N, K, L = inpl()
 
tree = [[[-1, 1]  for _ in range(N+1)] for _ in range(2)] 

def find(i, t):
    if tree[t][i][0] == -1:
        group = i
    else:
        group = find(tree[t][i][0], t)
        tree[t][i][0] = group
    return group
 
def unite(x, y, t):
    px = find(x, t)
    py = find(y, t)
     
    if tree[t][px][1] == tree[t][py][1]: 
        tree[t][py][0] = px
        tree[t][px][1] += 1
    else:
        if tree[t][px][1] < tree[t][py][1]:
            px, py = py, px
        tree[t][py][0] = px
 
for _ in range(K):
    x, y = inpl()
    if not int(find(x, 0) == find(y, 0)):
        unite(x, y, 0)

for _ in range(L):
    x, y = inpl()
    if not int(find(x, 1) == find(y, 1)):
        unite(x, y, 1)

D = defaultdict(lambda: 0)
P = []
for i in range(1, N+1):
    a, b = find(i, 0), find(i, 1)
    D[(a, b)] += 1
    P.append((a, b))
print(" ".join(map(str, [D[(a, b)] for a, b in P])))

Solution (Python):
class UnionFind:
    def __init__(self, n): 
        self.par = [-1]*n
        
    def __repr__(self):
        return "union_find({0})".format(self.par)
        
    def unite(self, x, y):
        if self.root(x) != self.root(y):
            self.par[self.root(x)] = y
        
    def root(self, x):
        if self.par[x] == -1:
            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)
        
        
from sys import stdin
def readLine_int_list():return list(map(int, stdin.readline().split()))
from collections import defaultdict

def main():
    n,k,l = readLine_int_list()
    
    rail = UnionFind(n)
    road = UnionFind(n)
    
    for _ in range(k):
        p, q = readLine_int_list()
        p, q = p-1, q-1
        road.unite(p, q)
     
    for _ in range(l):
        p, q = readLine_int_list()
        p, q = p-1, q-1
        rail.unite(p, q)
        
    d = defaultdict(int)
    
    for i in range(n):
        d[road.root(i), rail.root(i)] += 1
    results = (d[road.root(i), rail.root(i)] for i in range(n))


    print(" ".join(str(n) for n in results))
    

if __name__ == "__main__":main()

Solution (Python):

def root(v, uni):
  if uni[v] < 0:  
    return v
  else:           
    uni[v] = root(uni[v], uni)  
    return uni[v]


def connect(a, b, uni):
  
  ra = root(a, uni)
  rb = root(b, uni)
  if ra == rb:  
    return False
	
  
  if uni[ra] > uni[rb]: 
    tmp = ra
    ra  = rb 
    rb  = tmp

  
  uni[ra] += uni[rb]
  uni[rb] = ra
  return True
      

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

road = [-1]*(N+1)
rail = [-1]*(N+1)

for i in range(K):
  a, b = map(int, input().split())
  connect(a, b, road)

for i in range(L):
  a, b = map(int, input().split())
  connect(a, b, rail)



dp = [0]*(N+1)
for i in range(1, N+1):
  dp[i] = (root(i, road), root(i, rail))

dic = {}
for i in range(1, N+1):
  key = dp[i]
  if key not in dic:
    dic[key] = 1
  else:
    dic[key] += 1

for i in range(1, N+1):
  ans = dic[dp[i]]
  if i == N:
    print(ans)
  else:
    print(ans, end=" ")

Solution (Python):
from collections import defaultdict
class UnionFind:
    def __init__(self, size):
        self.rank = [0] * size
        self.par = range(size)

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

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

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

        if (self.rank[x] > self.rank[y]):
            self.par[y] = x
        else:
            self.par[x] = y
            if (self.rank[x] == self.rank[y]): self.rank[y] += 1

N, K, L = map(int, raw_input().split())
pq = [map(int, raw_input().split()) for i in xrange(K)]
rs = [map(int, raw_input().split()) for i in xrange(L)]

road = UnionFind(N)
rail = UnionFind(N)
for p, q in pq:
    road.unite(p - 1, q - 1)
for r, s in rs:
    rail.unite(r - 1, s - 1)

for i in xrange(N):
    road.find(i)
    rail.find(i)

pair = defaultdict(int) 
for i, j in zip(road.par, rail.par):
    pair[i, j] += 1

print " ".join(map(str, [pair[road.par[i], rail.par[i]] for i in xrange(N)]))

Solution (Python):
import sys
from collections import Counter

class UnionFind:

    def __init__(self, n):
        self.p = list(range(n))
        self.rank = [0] * n

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

        return self.p[x]

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

    def unite(self, x, y):
        u = self.find_root(x)
        v = self.find_root(y)

        if u == v:
            return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
        else:
            self.p[v] = u

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1


N, K, L = map(int, sys.stdin.readline().split())

uf1 = UnionFind(N)
uf2 = UnionFind(N)

for i in range(K):
    p, q = map(int, sys.stdin.readline().split())
    p, q = p - 1, q - 1
    uf1.unite(p, q)

for i in range(L):
    r, s = map(int, sys.stdin.readline().split())
    r, s = r - 1, s - 1
    uf2.unite(r, s)

cntr = Counter()

for i in range(N):
    u = uf1.find_root(i)
    v = uf2.find_root(i)

    cntr[(u, v)] += 1

ans = []

for i in range(N):
    u = uf1.find_root(i)
    v = uf2.find_root(i)

    ans.append(cntr[(u, v)])

print(*ans)

Solution (Python):
import sys
from collections import Counter

class UnionFind:

    def __init__(self, n):
        self.p = list(range(n))
        self.rank = [0] * n

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

        return self.p[x]

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

    def unite(self, x, y):
        u = self.find_root(x)
        v = self.find_root(y)

        if u == v:
            return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
        else:
            self.p[v] = u

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1


N, K, L = map(int, sys.stdin.readline().split())

uf1 = UnionFind(N)
uf2 = UnionFind(N)

for i in range(K):
    p, q = map(int, sys.stdin.readline().split())
    p, q = p - 1, q - 1
    uf1.unite(p, q)

for i in range(L):
    r, s = map(int, sys.stdin.readline().split())
    r, s = r - 1, s - 1
    uf2.unite(r, s)

cntr = Counter()

for i in range(N):
    u = uf1.find_root(i)
    v = uf2.find_root(i)

    cntr[(u, v)] += 1

ans = []

for i in range(N):
    u = uf1.find_root(i)
    v = uf2.find_root(i)

    ans.append(cntr[(u, v)])

print(*ans)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**10
mod = 10**9 + 7


class UnionFind:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

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

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

    def subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a

def main():
    n,k,l = list(map(int, input().split()))
    uk = UnionFind(n)
    ul = UnionFind(n)
    for _ in range(k):
        p,q = list(map(int, input().split()))
        uk.union(p-1,q-1)
    for _ in range(l):
        p,q = list(map(int, input().split()))
        ul.union(p-1,q-1)

    sk = collections.defaultdict(set)
    sl = collections.defaultdict(set)
    m = {}

    for i in range(n):
        sk[uk.find(i)].add(i)
        sl[ul.find(i)].add(i)
    r = []
    for i in range(n):
        if i in m:
            r.append(m[i])
            continue
        ss = sk[uk.find(i)] & sl[ul.find(i)]
        ssl = len(ss)
        for sc in ss:
            m[sc] = ssl
        r.append(m[i])

    return " ".join(map(str, r))



print(main())

Solution (Python):
from collections import defaultdict

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


class UnionFind(object):

    def __init__(self, n):
        self.n = n
        self.par = list(range(n))
        self.rank = [1] * n

    def is_same(self, a, b):
        return self.root(a) == self.root(b)

    def root(self, x):
        if self.par[x] == x:
            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.rank[x] > self.rank[y]:
            self.par[y] = x
        elif self.rank[x]  < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            self.rank[x] += 1

load_uf = UnionFind(N)
rail_uf = UnionFind(N)

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

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

ans = []
d = defaultdict(int)
for i in range(N):
    lp = load_uf.root(i)
    rp = rail_uf.root(i)
    d[lp, rp] += 1

for i in range(N):
    lp = load_uf.par[i]
    rp = rail_uf.par[i]
    if i == N-1:
        print(d[lp, rp])
    else:
        print(d[lp, rp], end=' ')

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

def root(x):
    
    if x != parent[x]: parent[x] = x = root(parent[x])
    return x
def unite(x, y):
    px = root(x)
    py = root(y)
    if px < py:
        parent[py] = px
    else:
        parent[px] = py

parent = range(n)
for i in xrange(k):
    p, q = map(int, raw_input().split())
    unite(p-1, q-1)
parent1 = parent
for i in xrange(n):root(i)

parent = range(n)
for i in xrange(l):
    r, s = map(int, raw_input().split())
    unite(r-1, s-1)
parent2 = parent
for i in xrange(n):root(i)

dic = {}
for p1, p2 in zip(parent1, parent2):
    dic[p1, p2] = dic.get((p1, p2), 0) + 1

ans = [dic[p1, p2] for p1, p2 in zip(parent1, parent2)]
print " ".join(map(str, ans))

Solution (Python):


import sys
import re
import math
import itertools
import collections
import bisect



mod=1000000007

pi=3.141592653589
IS=float('inf')
xy=[(1,0),(-1,0),(0,1),(0,-1)]
bs=[(-1,-1),(-1,1),(1,1),(1,-1)]
def niten(a,b): return abs(a-b) if a>=0 and b>=0 else  a+abs(b) if a>=0 else abs(a)+b if b>=0 else abs(abs(a)-abs(b))
def fib(n): return [(seq.append(seq[i-2] + seq[i-1]), seq[i-2])[1] for seq in [[0, 1]] for i in range(2, n)]
def gcd(a,b): return a if b==0 else gcd(b,a%b)
def lcm(a,b): return a*b/gcd(a,b)
def eucl(x1,y1,x2,y2): return ((x1-x2)**2+(y1-y2)**2)**0.5
def choco(xa,ya,xb,yb,xc,yc,xd,yd): return 1 if abs((yb-ya)*(yd-yc)+(xb-xa)*(xd-xc))<1.e-10 else 0
def pscl(num,l=[1]):
    for i in range(num):
        l = map(lambda x,y:x+y,[0]+l,l+[0])
    return l

class UnionFind:
    def __init__(self, size):
        self.rank=[0]*size
        self.par =range(size)
        self.grp =size

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

        self.par[x]=self.find(self.par[x])
        return self.par[x]

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

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

        self.grp-=1
        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 group_num(self):
        return self.grp
    def ra(self):
        return self.par

n,k,l=map(int,raw_input().split())
uf=UnionFind(n)
uf2=UnionFind(n)
ans=[1]*n

for i in range(k):
    a,b=map(int,raw_input().split())
    uf.unite(a-1,b-1)

for i in range(l):
    a,b=map(int,raw_input().split())
    uf2.unite(a-1,b-1)

q1=uf.ra()
q2=uf2.ra()
d={}
for i in range(n):
    while 1:
        if q1[i]!=q1[q1[i]]:
            q1[i]=q1[q1[i]]
        else:
            break
    while 1:
        if q2[i]!=q2[q2[i]]:
            q2[i]=q2[q2[i]]
        else:
            break

for i in range(n):
    if (q1[i],q2[i]) in d:
        d[(q1[i],q2[i])]+=1
    else:
        d[(q1[i],q2[i])]=1
for i in range(n):
    print d[(q1[i],q2[i])],

Solution (Python):

import sys
import re
import math
import itertools
import collections
import bisect



mod=1000000007

pi=3.141592653589
IS=float('inf')
xy=[(1,0),(-1,0),(0,1),(0,-1)]
bs=[(-1,-1),(-1,1),(1,1),(1,-1)]
def niten(a,b): return abs(a-b) if a>=0 and b>=0 else  a+abs(b) if a>=0 else abs(a)+b if b>=0 else abs(abs(a)-abs(b))
def fib(n): return [(seq.append(seq[i-2] + seq[i-1]), seq[i-2])[1] for seq in [[0, 1]] for i in range(2, n)]
def gcd(a,b): return a if b==0 else gcd(b,a%b)
def lcm(a,b): return a*b/gcd(a,b)
def eucl(x1,y1,x2,y2): return ((x1-x2)**2+(y1-y2)**2)**0.5
def choco(xa,ya,xb,yb,xc,yc,xd,yd): return 1 if abs((yb-ya)*(yd-yc)+(xb-xa)*(xd-xc))<1.e-10 else 0
def pscl(num,l=[1]):
    for i in range(num):
        l = map(lambda x,y:x+y,[0]+l,l+[0])
    return l

class UnionFind:
    def __init__(self, size):
        self.rank=[0]*size
        self.par =range(size)
        self.grp =size

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

        self.par[x]=self.find(self.par[x])
        return self.par[x]

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

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

        self.grp-=1
        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 group_num(self):
        return self.grp
    def ra(self):
        return self.par

n,k,l=map(int,raw_input().split())
uf=UnionFind(n)
uf2=UnionFind(n)
ans=[1]*n

for i in range(k):
    a,b=map(int,raw_input().split())
    uf.unite(a-1,b-1)

for i in range(l):
    a,b=map(int,raw_input().split())
    uf2.unite(a-1,b-1)

q1=uf.ra()
q2=uf2.ra()
d={}
for i in range(n):
    while 1:
        if q1[i]!=q1[q1[i]]:
            q1[i]=q1[q1[i]]
        else:
            break
    while 1:
        if q2[i]!=q2[q2[i]]:
            q2[i]=q2[q2[i]]
        else:
            break

for i in range(n):
    if (q1[i],q2[i]) in d:
        d[(q1[i],q2[i])]+=1
    else:
        d[(q1[i],q2[i])]=1
for i in range(n):
    print d[(q1[i],q2[i])],