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

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

    for i in range(N):
        print(d[_id(ur.root(i), ut.root(i))], end=' ')

_abc049_d()

Solution (Python):
class uf_tree:
    def __init__(self, n):
        self.sizes = [0] * n
        self.par = range(n)

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

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.sizes[x] < self.sizes[y]:
            x, y = y, x
        self.par[y] = x
        self.sizes[x] += self.sizes[y]

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

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


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

uf_1 = uf_tree(N+1)
uf_2 = uf_tree(N+1)

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

for i in range(L):
    r, s = map(int, raw_input().split())
    uf_2.unite(r, s);

dic = {}

for i in range(1, N+1):
    key = (uf_1.find(i), uf_2.find(i))
    dic[key] = dic.get(key, 0) + 1

for i in range(1, N+1):
    print dic[(uf_1.find(i), uf_2.find(i))],

Solution (Python):
from collections import deque
from collections import Counter

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

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

for i in range(K):
	p,q=map(int, raw_input().split())
	nl[p].append(q)
	nl[q].append(p)

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

for i in range(L):
	p,q=map(int, raw_input().split())
	nl2[p].append(q)
	nl2[q].append(p)


v1=[ None for i in range(N+1) ]
v2=[ None for i in range(N+1) ]


def bfs(start,nl,V,l):
	q = deque([]) 
	V[start]=1
	l[start]=start
	q.append(start)

	while len(q)!=0:
		v=q.popleft()
		for i in nl[v]:
			if V[i] is None:
				V[i]=1
				q.append(i)
				l[i]=start
			
	return V

l1=[ "" for i in range(N+1) ]
l2=[ "" for i in range(N+1) ]


for i in range(1,N+1):
	if v1[i] is None:
		bfs(i,nl,v1,l1)

for i in range(1,N+1):
	if v2[i] is None:
		bfs(i,nl2,v2,l2)


c=[]
for idx,i in enumerate( zip(l1,l2) ):
	x=i[0]; y=i[1]
	if idx==0: continue
	c.append( (x,y) )


C=Counter(c)

for idx,i in enumerate( zip(l1,l2) ):
	x=i[0]; y=i[1]
	if idx==0: continue
	print C[(x,y)],

Solution (Python):
from collections import Counter
N, K, L = map(int, input().split())
u1, u2 = list(range(N+1)), list(range(N+1))

def root(u, r):
    if u[r] == r:
        return r
    u[r] = root(u, u[r])
    return u[r]

def update(u, r, n):
    rr = root(u, r)
    nr = root(u, n)
    if rr > nr:
        rr, nr = nr, rr
    u[nr] = rr

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

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

rs = [(root(u1, i), root(u2, i)) for i in range(1, N+1)]
c = Counter(rs)
 
print(' '.join(map(str, [c[r] for r in rs])))

Solution (Python):
def d_Connectivity(N, K, L, R, T):  
    class UnionFind:
        def __init__(self, N):
            self.p = list(range(N))  
            self.rank = [0] * N  
            self.size = [1] * N  

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

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

        def union(self, x, y):
            
            u = self.find(x)
            v = self.find(y)
            if u == v:
                
                return
            if self.rank[u] < self.rank[v]:
                self.p[u] = v  
                self.size[v] += self.size[u]  
                self.size[u] = 0  
            else:
                
                self.p[v] = u
                self.size[u] += self.size[v]
                self.size[v] = 0
                if self.rank[u] == self.rank[v]:
                    
                    self.rank[u] += 1

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

        def show(self):
            return self.p

    road = UnionFind(N)  
    train = UnionFind(N)  
    for p, q in R:
        road.union(p - 1, q - 1)
    for r, s in T:
        train.union(r - 1, s - 1)

    from collections import defaultdict
    d = defaultdict(int)
    for i in range(N):
        d[road.find(i), train.find(i)] += 1  
    ans = (d[road.find(i), train.find(i)] for i in range(N))
    return ' '.join(str(i) for i in ans)

N,K,L = [int(i) for i in input().split()]
R = [[int(i) for i in input().split()] for j in range(K)]
T = [[int(i) for i in input().split()] for j in range(L)]
print(d_Connectivity(N, K, L, R, T))

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

p_road = [i for i in range(N)]
p_rail = [i for i in range(N)]

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

def unite(a,b,par):
    ra = root(a,par)
    rb = root(b,par)
    if ra == rb: return
    par[ra] = rb

for i in range(K):
    a,b = map(lambda x:int(x)-1, input().split())
    unite(a,b,p_road)

for i in range(L):
    a,b = map(lambda x:int(x)-1, input().split())
    unite(a,b,p_rail)

road_ids = []
rail_ids = []
for i in range(N):
    road_ids.append(root(i,p_road))
    rail_ids.append(root(i,p_rail))

ctr = Counter()
for a,b in zip(road_ids, rail_ids):
    ctr.update([(a,b)])

print(' '.join(list(map(str, [ctr[(road_ids[i], rail_ids[i])] for i in range(N)]))))

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

def root(u, n):
    if u[n] == n:
        return n
    else:
        t = root(u, u[n])
        u[n] = t
        return t

def update(u, r, n):
    u[root(u, n)] = root(u, r)

for i in range(K):
    p, q = map(int, input().split())
    p -= 1
    q -= 1
    update(u1, p, q)

for i in range(L):
    r, s = map(int, input().split())
    r -= 1
    s -= 1
    update(u2, r, s)

p = [(root(u1, i), root(u2, i)) for i in range(N)]
ans = {}
for x in p:
    if x not in ans:
        ans[x] = 1
    else:
        ans[x] += 1
print(' '.join(map(str, [ans[x] for x in p])))

Solution (Python):
n,k,l=[int(x) for x in input().split()]
from collections import deque
road=[{i} for i in range(n)]
rail=[{i} for i in range(n)]
for i in [0]*k:
    p,q=[int(x)-1 for x in input().split()]
    road[p].add(q)
    road[q].add(p)
for i in [0]*l:
    r,s=[int(x)-1 for x in input().split()]
    rail[r].add(s)
    rail[s].add(r)
flag=[0]*n
for i in range(n):
    if flag[i]==1:
        continue
    flag[i]=1
    d=deque(road[i])
    while d:
        tmp=d.popleft()
        if flag[tmp]==1:
            continue
        flag[tmp]=1
        d.extend(road[tmp])
        road[i].update(road[tmp])
    for j in road[i]:
        road[j]=road[i]
flag=[0]*n
for i in range(n):
    if flag[i]==1:
        continue
    flag[i]=1
    d=deque(rail[i])
    while d:
        tmp=d.popleft()
        if flag[tmp]==1:
            continue
        flag[tmp]=1
        d.extend(rail[tmp])
        rail[i].update(rail[tmp])
    for j in rail[i]:
        rail[j]=rail[i]
ans=[0]*n
for i in range(n):
    if ans[i]!=0:
        continue
    sumset=road[i]&rail[i]
    for j in sumset:
        ans[j]=str(len(sumset))
print(" ".join(ans))

Solution (Python):
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 5 + 1)


class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))

    def is_same_set(self, x: int, y: int) -> bool:
        return self.find_root(x) == self.find_root(y)

    def union_set(self, x: int, y: int):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return

        self.parent[x] = y

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


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

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

    groups = [(uf1.find_root(i), uf2.find_root(i)) for i in range(N)]
    c = Counter(groups)

    print(*(c[g] for g in groups))


if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter

class UnionFind:
    def __init__(self, size):
        self.size = size
        self.parents = list(range(size))

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

    def find(self, x):
        path = [x]
        v = x
        while self.parents[v]!=v:
            v = self.parents[v]
            path.append(v)
        for p in path:
            self.parents[p] = v
        return v

if __name__=='__main__':
    n, k, l = map(int, input().split())

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

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

    groups = [str(road.find(i))+"&"+str(railway.find(i)) for i in range(n)]
    ctr = Counter(groups)

    print(*(ctr[g] for g in groups))

Solution (Python):

INF=10**10
from collections import deque

def dfs(N,graph):
    arr=[-1 for _ in range(N)]
    queue=deque()
    temp=0
    for i in range(N):
        if arr[i]!=-1:
            continue
        arr[i]=temp
        for i in graph[i]:
            queue.append(i)
        while(queue):
            to=queue.pop()
            arr[to]=temp
            for i in graph[to]:
                if arr[i]==-1:
                    queue.append(i)
        temp+=1
    return arr
            
            

def main():
    N,K,L=list(map(int,input().split()))
 
    graph1=[[]for _ in range(N)]
    graph2=[[]for _ in range(N)]
    for _ in range(K):
        p,q=list(map(int,input().split()))
        p-=1
        q-=1
        graph1[p].append(q)
        graph1[q].append(p)
    for _ in range(L):
        p,q=list(map(int,input().split()))
        p-=1
        q-=1
        graph2[p].append(q)
        graph2[q].append(p)
        
    a=dfs(N,graph1)
    b=dfs(N,graph2)
    
    dict={}
    for i in range(N):
        dict[(a[i],b[i])]=dict.get((a[i],b[i]),0)+1
    for i in range(N):
        print(dict[(a[i],b[i])],end=' ')
    
    
if __name__=="__main__":
    main()

Solution (Python):
import sys
from collections import deque, Counter

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def solve():
    N, K, L = map(int, input().split())
    Adj_r = [[] for i in range(N)]
    Adj_t = [[] for i in range(N)]

    for i in range(K):
        p, q = map(int, input().split())
        p, q = p-1, q-1
        Adj_r[p].append(q)
        Adj_r[q].append(p)

    for i in range(L):
        r, s = map(int, input().split())
        r, s = r-1, s-1
        Adj_t[r].append(s)
        Adj_t[s].append(r)

    col = 0
    cols_r = [None] * N
    cols_t = [None] * N

    for u in range(N):
        if cols_r[u] is None:
            bfs_color(N, Adj_r, cols_r, u, col)
            col += 1
        if cols_t[u] is None:
            bfs_color(N, Adj_t, cols_t, u, col)
            col += 1

    
    

    cnt = Counter((cols_r[u], cols_t[u]) for u in range(N))

    ans = [cnt[cols_r[u], cols_t[u]] for u in range(N)]

    print(*ans)


def bfs_color(N, Adj, v_cols, u, col):
    v_cols[u] = col
    nxts = deque([u])

    while nxts:
        v = nxts.popleft()

        for w in Adj[v]:
            if v_cols[w] is None:
                v_cols[w] = col
                nxts.append(w)


if __name__ == '__main__':
    solve()

Solution (Python):
import sys
from collections import deque, Counter

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def solve():
    N, K, L = map(int, input().split())
    Adj_r = [[] for i in range(N)]
    Adj_t = [[] for i in range(N)]

    for i in range(K):
        p, q = map(int, input().split())
        p, q = p-1, q-1
        Adj_r[p].append(q)
        Adj_r[q].append(p)

    for i in range(L):
        r, s = map(int, input().split())
        r, s = r-1, s-1
        Adj_t[r].append(s)
        Adj_t[s].append(r)

    col = 0
    cols_r = [None] * N
    cols_t = [None] * N

    for u in range(N):
        if cols_r[u] is None:
            bfs_color(N, Adj_r, cols_r, u, col)
            col += 1
        if cols_t[u] is None:
            bfs_color(N, Adj_t, cols_t, u, col)
            col += 1

    
    

    cnt = Counter((cols_r[u], cols_t[u]) for u in range(N))

    ans = [cnt[cols_r[u], cols_t[u]] for u in range(N)]

    print(*ans)


def bfs_color(N, Adj, v_cols, u, col):
    v_cols[u] = col
    nxts = deque([u])

    while nxts:
        v = nxts.popleft()

        for w in Adj[v]:
            if v_cols[w] is None:
                v_cols[w] = col
                nxts.append(w)


if __name__ == '__main__':
    solve()

Solution (Python):
from collections import deque


def create_group(N, n):
    city = [[] for _ in range(N + 1)]
    for _ in range(n):
        p, q = map(int, input().split(" "))
        city[p].append(q)
        city[q].append(p)

    group_list = [0] * (N + 1)
    gid = 0
    Q = deque()
    for i in range(1, N + 1):
        if group_list[i] == 0:
            gid += 1
            Q.clear()
            Q.append(i)
            group_list[i] = gid
            while len(Q) > 0:
                x = Q.popleft()
                for y in city[x]:
                    if group_list[y] == 0:
                        group_list[y] = gid
                        Q.append(y)

    return group_list

if __name__ == "__main__":
    N, K, L = list(map(int, input().split(" ")))
    rg = create_group(N, K)
    lg = create_group(N, L)

    rg_lg_dict = {}
    for i in range(1, N+1):
        key = (rg[i], lg[i])
        if key in rg_lg_dict:
            rg_lg_dict[key] += 1
        else:
            rg_lg_dict[key] = 1

    print_list = []
    for i in range(1, N+1):
        key = (rg[i], lg[i])
        print_list.append(str(rg_lg_dict[key]))
    print(" ".join(print_list))

Solution (Python):
from collections import deque

def makegroup(rg, n):
    city = [[] for i in range(N+1)]
    for i in range(n):
        p, q = map(int, input().split())
        city[p].append(q)
        city[q].append(p)

    Q = deque()
    gid = 0
    for i in range(1, N+1):
        if rg[i] == 0:
            gid += 1
            Q.clear()
            Q.append(i)
            rg[i] = gid
            while len(Q) > 0:
                x = Q.popleft()
                for y in city[x]:
                    if rg[y] == 0:
                        rg[y] = gid
                        Q.append(y)

N, K, L = map(int, input().split())
rg = [0] * (N + 1)
makegroup(rg, K)
lg = [0] * (N + 1)
makegroup(lg, L)

dict = {}
for i in range(1, N+1):
    key = (rg[i], lg[i])
    if key in dict:
        dict[key] += 1
    else:
        dict[key] = 1

key = (rg[1], lg[1])
print(dict[key], end="")
for i in range(2,N+1):
    key = (rg[i], lg[i])
    print(" ", dict[key], sep="", end="")
print()

Solution (Python):
class UnionFind:
	"""Union-Find, 
	http://www.slideshare.net/chokudai/union-find-49066733"""

	def __init__(self, N):
		self.par = [i for i in range(N)]
		self.rank = [0 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 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[x] = y
		else:
			self.par[y] = x
			if self.rank[x]==self.rank[y]:
				self.rank[x] = self.rank[x]+1
		return

N, K, L = map(lambda x:int(x), input().split())
P = [0]*K
Q = [0]*K
R = [0]*L
S = [0]*L
for i in range(K):
	P[i], Q[i] = map(lambda x:int(x), input().split())
for i in range(L):
	R[i], S[i] = map(lambda x:int(x), input().split())

uf_k = UnionFind(N)
uf_l = UnionFind(N)

for i in range(K):
	uf_k.unite(P[i]-1, Q[i]-1)
for i in range(L):
	uf_l.unite(R[i]-1, S[i]-1)

k_groups = [uf_k.root(i) for i in range(N)]
l_groups = [uf_l.root(i) for i in range(N)]

kl_groups = [(k_groups[i], l_groups[i]) for i in range(N)]
kl_groups_origin = kl_groups
kl_groups = sorted(kl_groups)

results_dict = {}

idx = 0
count = 1
pair = kl_groups[0]
for i in range(1, N):
	if kl_groups[i]==pair:
		count = count+1
	else:
		results_dict[pair] = count
		pair = kl_groups[i]
		count = 1
results_dict[pair] = count

for i in range(N):
	pair = kl_groups_origin[i]
	print(results_dict[pair], end=" ")

Solution (Python):
class UnionFind:
	"""Union-Find, 
	http://www.slideshare.net/chokudai/union-find-49066733"""

	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 unite(self, x, y):
		x = self.root(x)
		y = self.root(y)
		
		
		self.par[x] = y
		return

N, K, L = map(lambda x:int(x), input().split())
P = [0]*K
Q = [0]*K
R = [0]*L
S = [0]*L
for i in range(K):
	P[i], Q[i] = map(lambda x:int(x), input().split())
for i in range(L):
	R[i], S[i] = map(lambda x:int(x), input().split())

uf_k = UnionFind(N)
uf_l = UnionFind(N)

for i in range(K):
	uf_k.unite(P[i]-1, Q[i]-1)
for i in range(L):
	uf_l.unite(R[i]-1, S[i]-1)

k_groups = [uf_k.root(i) for i in range(N)]
l_groups = [uf_l.root(i) for i in range(N)]

kl_groups = [(k_groups[i], l_groups[i]) for i in range(N)]
kl_groups_origin = kl_groups
kl_groups = sorted(kl_groups)

results_dict = {}

idx = 0
count = 1
pair = kl_groups[0]
for i in range(1, N):
	if kl_groups[i]==pair:
		count = count+1
	else:
		results_dict[pair] = count
		pair = kl_groups[i]
		count = 1
results_dict[pair] = count

for i in range(N):
	pair = kl_groups_origin[i]
	print(results_dict[pair], end=" ")

Solution (Python):
from collections import Counter
n,k,l = map(int, input().split())
def f(m):
    a = list(range(n))
    def g(i):
        if a[i] == i:
            return i
        a[i] = g(a[i])
        return a[i]
    for _ in range(m):
        p,q = map(int, input().split())
        i = g(p-1)
        j = g(q-1)
        a[j] = i
    return g
g = f(k)
h = f(l)
c = Counter((g(i),h(i)) for i in range(n))
print(' '.join((str(c[g(i),h(i)]) for i in range(n))))

Solution (Python):
from collections import Counter
n,k,l = map(int, input().split())
def f(m):
    a = list(range(n))
    def g(i):
        if a[i] == i:
            return i
        a[i] = g(a[i])
        return a[i]
    for _ in range(m):
        p,q = map(int, input().split())
        i = g(p-1)
        j = g(q-1)
        a[j] = i
    return g
g = f(k)
h = f(l)
c = Counter((g(i),h(i)) for i in range(n))
print(' '.join((str(c.get((g(i),h(i)), 1)) for i in range(n))))

Solution (Python):


import sets
import sys

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

def union(parent, x, y):
    find(parent, x)
    find(parent, y)

    if parent[x] != parent[y]:
        parent[parent[y]] = parent[parent[x]]

def main(argv):
    tokens = sys.stdin.readline().rstrip("\n").split()

    while len(tokens) == 3:
        n, k, l = [int(i) for i in tokens]

        parent_roads = [int(i) for i in xrange(n)]
        parent_railways = [int(i) for i in xrange(n)]

        for i in xrange(k):
            x, y = [int(i) for i in raw_input().split(" ")]
            union(parent_roads, x - 1, y - 1)

        for i in xrange(l):
            x, y = [int(i) for i in raw_input().split(" ")]
            union(parent_railways, x - 1, y - 1)

        count = dict()
        for i in xrange(n):
            key = (find(parent_roads, i), find(parent_railways, i))
            if not count.has_key(key):
                count[key] = 0
            count[key] += 1

        results = []
        for i in xrange(n):
            key = (find(parent_roads, i), find(parent_railways, i))
            results.append(str(count[key]))
        print " ".join(results)

        tokens = sys.stdin.readline().rstrip("\n").split()

if __name__ == "__main__":
    main(sys.argv)

Solution (Python):


import sets
import sys

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

def union(parent, x, y):
    parent_x = find(parent, x)
    parent_y = find(parent, y)

    if parent_x != parent_y:
        parent[parent_y] = parent[parent_x]

def main(argv):
    tokens = sys.stdin.readline().rstrip("\n").split()

    while len(tokens) == 3:
        n, k, l = [int(i) for i in tokens]

        parent_roads = [int(i) for i in xrange(n)]
        parent_railways = [int(i) for i in xrange(n)]

        for i in xrange(k):
            x, y = [int(i) for i in raw_input().split(" ")]
            union(parent_roads, x - 1, y - 1)

        for i in xrange(l):
            x, y = [int(i) for i in raw_input().split(" ")]
            union(parent_railways, x - 1, y - 1)

        count = dict()
        for i in xrange(n):
            key = (find(parent_roads, i), find(parent_railways, i))
            if not count.has_key(key):
                count[key] = 0
            count[key] += 1

        results = []
        for i in xrange(n):
            key = (find(parent_roads, i), find(parent_railways, i))
            results.append(str(count[key]))
        print " ".join(results)

        tokens = sys.stdin.readline().rstrip("\n").split()

if __name__ == "__main__":
    main(sys.argv)

Solution (Python):
from collections import defaultdict


class UF:
    def __init__(self, _n):
        assert _n >= 0
        self._count = _n
        self._parent = list(range(_n))
        self._rank = [1] * _n

    def find(self, p):
        assert p >= 0 & p < len(self._parent)
        while p != self._parent[p]:
            self._parent[p] = self._parent[self._parent[p]]    
            p = self._parent[p]
        return p

    def count(self):
        return self._count

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

    def union(self, p, q):
        root_p = self.find(p)
        root_q = self.find(q)
        if root_p == root_q:
            return
        
        if self._rank[root_p] < self._rank[root_q]:
            self._parent[root_p] = root_q
        elif self._rank[root_p] > self._rank[root_q]:
            self._parent[root_q] = root_p
        else:
            self._parent[root_q] = root_p
            self._rank[root_p] += 1
        self._count -= 1


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

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

for _ in range(l):
    p, q = map(int, input().split())
    uf_rail.union(p-1, q-1)

d = defaultdict(int)
for i in range(n):
    d[uf_road.find(i), uf_rail.find(i)] += 1


print(*(d[uf_road.find(i), uf_rail.find(i)] for i in range(n)))

Solution (Python):

class UF(object):
    def __init__(self, n):
        self.table = [None for i in range(n)]
    def find(self, x):
        if self.table[x] is None:
            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:
            self.table[s2] = s1

n, k, l = [int(x) for x in raw_input().split()]
d = UF(n)
t = UF(n)
for i in range(k):
    p, q = [int(x) - 1 for x in raw_input().split()]
    d.union(p, q)
for i in range(l):
    r, s = [int(x) - 1 for x in raw_input().split()]
    t.union(r, s)
res = {}
for i in range(n):
    key = (d.find(i), t.find(i))
    res[key] = res.get(key, 0) + 1
for i in range(n):
    print res[(d.find(i), t.find(i))],

Solution (Python):



from collections import defaultdict


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


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


def main():
    n, k, l = [int(i) for i in raw_input().split()]
    road_parent = range(n)
    road_rank = [0 for _ in xrange(n)]
    train_parent = range(n)
    train_rank = [0 for _ in xrange(n)]

    for i in range(k):
        p, q = [int(i)-1 for i in raw_input().split()]
        union(road_parent, road_rank, p, q)
    for i in range(l):
        r, s = [int(i)-1 for i in raw_input().split()]
        union(train_parent, road_rank, r, s)
    counter = defaultdict(int)
    for i in range(n):
        counter[(find(road_parent, i), find(train_parent, i))] += 1
    ans_list = [counter[(find(road_parent, i), find(train_parent, i))] for i in xrange(n)]
    print ' '.join(map(str, ans_list))


if __name__ == "__main__":
    main()

Solution (Python):



from collections import defaultdict
def find(x, parent):
    if parent[x] == x:
        return x
    else:
        parent[x] = find(parent[x], parent)
        return parent[x]


def union(x, y, parent):
    x = find(x, parent)
    y = find(y, parent)
    if x == y:
        return
    parent[y] = x


def main():
    n, k, l = [int(i) for i in raw_input().split()]
    road_parent = range(n)
    train_parent = range(n)

    for i in range(k):
        p, q = [int(i)-1 for i in raw_input().split()]
        union(p, q, road_parent)
    for i in range(l):
        r, s = [int(i)-1 for i in raw_input().split()]
        union(r, s, train_parent)
    counter = defaultdict(int)
    for i in range(n):
        counter[(find(i, road_parent), find(i, train_parent))] += 1
    ans_list = [counter[(find(i, road_parent), find(i, train_parent))] for i in xrange(n)]
    print ' '.join(map(str, ans_list))


if __name__ == "__main__":
    main()