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):
from collections import defaultdict
class UnionFind:
    def __init__(self,size):
        self.parent=range(size)
        self.tree_num=size
        self.tree_w=[1]*size
        self.rank=[0]*size

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

    def unite(self,x,y):
        x=self.findset(x)
        y=self.findset(y)
        if x==y:
            return
        if self.rank[x]<self.rank[y]:
            self.parent[x]=y
            self.tree_num-=1
            self.tree_w[y]+=self.tree_w[x]
        else:
            self.parent[y]=x
            self.tree_num-=1
            self.tree_w[x]+=self.tree_w[y]
            if self.rank[x]==self.rank[y]:
                self.rank[x]+=1

    def same(self,x,y):
        if self.findset(x)==self.findset(y):
            return True
        else:
            return False

    def tree_number(self):
        return self.tree_num

    def tree_weight(self,x):
        return self.tree_w[self.findset(x)]

n,k,l=map(int,raw_input().split())
uf1=UnionFind(n)
uf2=UnionFind(n)
for i in xrange(k):
    p,q=map(int,raw_input().split())
    p-=1;q-=1
    uf1.unite(p,q)
for i in xrange(l):
    p,q=map(int,raw_input().split())
    p-=1;q-=1
    uf2.unite(p,q)
cnt=defaultdict(int)
for i in xrange(n):
    cnt[(uf1.findset(i),uf2.findset(i))]+=1
ans=[0]*n
for i in xrange(n):
    ans[i]+=cnt[(uf1.findset(i),uf2.findset(i))]
print " ".join(map(str,ans))

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

def root(x):
    if x == parent[x]: return x
    parent[x] = root(parent[x])
    return parent[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):

def f(m, r):
    connmap = [[] for _ in range(m + 1)]
    for _ in range(r):
        a, b = map(int, input().split())
        connmap[a].append(b)
        connmap[b].append(a)
    group = [0] * (m + 1)
    num = 0
    for i in range(1, m + 1):
        if group[i] > 0:
            continue
        num += 1
        group[i] = num
        for j in connmap[i]:
            group[j] = num
        bfs = connmap[i]
        while len(bfs) > 0:
            tmp = []
            for j in bfs:
                for k in connmap[j]:
                    if group[k] > 0:
                        continue
                    group[k] = num
                    tmp.append(k)
            bfs = tmp
    return group

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

road = f(n, k)
rail = f(n, l)

count = {}

for i in range(1, n + 1):
    key = '{0} {1}'.format(road[i], rail[i])
    if key in count:
        count[key] += 1
    else:
        count[key] = 1
    
for i in range(1, n + 1):
    key = '{0} {1}'.format(road[i], rail[i])
    print(count[key], end=' ' if i < n else '')
print()

Solution (Python):


import collections


class UnionFind(object):

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

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

    def in_the_same_set(self, node1, node2):
        return self.root(node1) == self.root(node2)

    def unite(self, node1, node2):
        x = self.root(node1)
        y = self.root(node2)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


def main():
    n, k, l = (int(x) for x in input().split())
    uf_roads = UnionFind(n)
    for _ in range(k):
        p, q = (int(x) - 1 for x in input().split())
        uf_roads.unite(p, q)
    uf_rails = UnionFind(n)
    for _ in range(l):
        r, s = (int(x) - 1 for x in input().split())
        uf_rails.unite(r, s)
    ctr = collections.Counter((uf_roads.root(i), uf_rails.root(i))
                              for i in range(n))
    ans = [ctr[(uf_roads.root(i), uf_rails.root(i))] for i in range(n)]
    print(" ".join(str(a) for a in ans))

if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict


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

    def find(self, x):
        while self.table[x] >= 0:
            x = self.table[x]
        return x

    def root(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.root(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


n, k, l = map(int, input().split())
ufd, ufr = UnionFind3(n), UnionFind3(n)
for _ in range(k):
    p, q = map(int, input().split())
    ufd.union(p - 1, q - 1)
for _ in range(l):
    r, s = map(int, input().split())
    ufr.union(r - 1, s - 1)
d = defaultdict(int)
for i in range(n):
    d[ufd.root(i), ufr.root(i)] += 1
print(*(d[ufd.root(i), ufr.root(i)] for i in range(n)))

Solution (Python):
import collections

class UnionFind:
    def __init__(self, n):
        self._id = list(range(n))
        self._sz = [1] * n

    def _root(self, i):
        j = i
        while (j != self._id[j]):
            self._id[j] = self._id[self._id[j]]
            j = self._id[j]
        return j

    def find(self, p, q):
        return self._root(p) == self._root(q)

    def union(self, p, q):
        i = self._root(p)
        j = self._root(q)
        if (self._sz[i] < self._sz[j]):
            self._id[i] = j
            self._sz[j] += self._sz[i]
        else:
            self._id[j] = i
            self._sz[i] += self._sz[j]

n, k, l = [int(x) for x in input().split()]
pqs = set(tuple(int(x) - 1 for x in input().split()) for _ in range(k))
rss = set(tuple(int(x) - 1 for x in input().split()) for _ in range(l))

road = UnionFind(n)
for pq in pqs:
    road.union(*pq)

rail = UnionFind(n)
for rs in rss:
    rail.union(*rs)

roadrail = [(road._root(i), rail._root(i)) for i in range(n)]
cnt = collections.Counter(roadrail)

print(' '.join([str(cnt[r]) for r in roadrail]))

Solution (Python):
class UnionFind:
 
    def __init__(self, size):
        
        
        self.size = size
        self.table = [-1 for _ in range(size)]
 
    def find(self, x):
        
        children = []
        while self.table[x] >= 0:
            children.append(x)
            x = self.table[x]
        for c in children:
            self.table[c] = x
        return 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 self.table[s1]
 
n,k,l= map(int, input().split())
road = UnionFind(n+1)
train = UnionFind(n+1)
for i in range(k):
    p,q = map(int, input().split())
    road.union(p, q)
for i in range(l):
    p,q = map(int, input().split())
    train.union(p,q)
import collections
d = collections.defaultdict(int)
for i in range(1,n+1):
    r = road.find(i)
    t = train.find(i)
    d[(r,t)] += 1
res = [d[(road.find(i), train.find(i))] for i in range(1,n+1)]

print(*res, sep=' ')

Solution (Python):
class UnionFind:
 
    def __init__(self, size):
        
        
        self.size = size
        self.table = [-1 for _ in range(size)]
 
    def find(self, x):
        
        children = []
        while self.table[x] >= 0:
            children.append(x)
            x = self.table[x]
        for c in children:
            self.table[c] = x
        return 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 self.table[s1]
 
n,k,l= map(int, input().split())
road = UnionFind(n+1)
train = UnionFind(n+1)
for i in range(k):
    p,q = map(int, input().split())
    road.union(p, q)
for i in range(l):
    p,q = map(int, input().split())
    train.union(p,q)
import collections
d = collections.defaultdict(int)
for i in range(1,n+1):
    r = road.find(i)
    t = train.find(i)
    d[(r,t)] += 1
res = [d[(road.find(i), train.find(i))] for i in range(1,n+1)]

print(*res, sep=' ')

Solution (Python):

class union_find:
	def __init__(self, size):
		
		
		self.size=size
		self.table = [-1 for _ in range(size)]
		self.num=[0 for i 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 unite(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 definite(self):
		for i in range(self.size):
			self.num[i]=self.find(i)
		return(True)


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

for i in range(K):
	a=list(map(int,input().split()))
	road.unite(a[0]-1,a[1]-1)

for i in range(L):
	a=list(map(int,input().split()))
	rail.unite(a[0]-1,a[1]-1)

road.definite()
rail.definite()

dic={}


for i in range(N):
	key=str(road.num[i])+":"+str(rail.num[i])
	if key in dic:
		dic[key].append(i)
	else:
		dic[key]=[i]


res=[0 for i in range(N)]
for i in dic.values():
	l=len(i)
	for j in i:
		res[j]=l

for i in res:
	print(i,end=" ")
print("")

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

road_parent = list(range(N))
road_rank = [0] * N
train_parent = list(range(N))
train_rank = [0] * N

def Find(parent, i):
	if parent[i] == i:
		return i
	else:
		parent[i] = Find(parent, parent[i])
		return parent[i]

def Union(parent, rank, i, j):
	i_root = Find(parent, i)
	j_root = Find(parent, j)
	if rank[i_root] > rank[j_root]:
		parent[j_root] = i_root
	elif rank[i_root] < rank[j_root]:
		parent[i_root] = j_root
	elif i_root != j_root:
		parent[j_root] = i_root
		rank[i_root] += 1

for cnt in range(K):
	i,j = map(int, input().split())
	Union(road_parent, road_rank, i-1, j-1)

for cnt in range(L):
	i,j = map(int, input().split())
	Union(train_parent, train_rank, i-1, j-1)

from collections import defaultdict

counter = defaultdict(int)
for i in range(N):
	counter[(Find(road_parent, i), Find(train_parent, i))] += 1

print(' '.join(str(counter[(Find(road_parent, i), Find(train_parent, i))]) for i in range(N)))

Solution (Python):
from sys import exit, setrecursionlimit
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

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

setrecursionlimit(1000000)

(N, K, L) = reads()

rail = union_find(N)
road = union_find(N)

for _ in range(K):
  (p, q) = reads()
  (p, q) = (p-1, q-1)
  road.unite(p, q)

for _ in range(L):
  (p, q) = reads()
  (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))