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.uf = [-1]*n

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

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

    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return 
        if self.uf[x] > self.uf[y]:
            x,y = y,x
        self.uf[x] += self.uf[y]
        self.uf[y] = x

    def size(self,x):
        x = self.find(x)
        return -self.uf[x]

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


gp = Unionfind(n)
gr = Unionfind(n)

for i in range(k):
    a,b = map(int,input().split())
    gp.union(a-1,b-1)
for i in range(l):
    a,b = map(int,input().split())
    gr.union(a-1,b-1)

l = []
dic = {}
for i in range(n):
    a = gp.find(i) 
    b = gr.find(i)
    s = (a,b)
    l.append(s)
    if s in dic:
        dic[s] += 1
    else:
        dic[s] = 1
ans = []
for i in range(n):
    ans.append(dic[l[i]])
print(*ans)

Solution (Python):
class Unionfind:
    
    def __init__(self,n):
        self.uf = [-1]*n

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

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

    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return 
        if self.uf[x] > self.uf[y]:
            x,y = y,x
        self.uf[x] += self.uf[y]
        self.uf[y] = x

    def size(self,x):
        x = self.find(x)
        return -self.uf[x]

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


gp = Unionfind(n)
gr = Unionfind(n)

for i in range(k):
    a,b = map(int,input().split())
    gp.union(a-1,b-1)
for i in range(l):
    a,b = map(int,input().split())
    gr.union(a-1,b-1)

l = []
dic = {}
for i in range(n):
    a = gp.find(i) 
    b = gr.find(i)
    if a < 0:
        a = i
    if b < 0:
        b = i
    s = (a,b)
    l.append(s)
    if s in dic:
        dic[s] += 1
    else:
        dic[s] = 1
ans = []
for i in range(n):
    ans.append(dic[l[i]])
print(*ans)

Solution (Python):
from collections import deque

n,k,l = map(int,input().split())
ep = [[] for i in range(n)]
er = [[] for i in range(n)]

gp = [-1]*n
gr = [-1]*n

for i in range(k):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    ep[a].append(b)
    ep[b].append(a)
for i in range(l):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    er[a].append(b)
    er[b].append(a)

def dfs(e,g):
    count = 0
    for i in range(n):
        if g[i] == -1:
            g[i] = count

            q = deque([])
            q.append(i)
            while q:
                now = q.pop()

                for nex in e[now]:
                    if g[nex] == -1:
                        g[nex] = g[now]
                        q.append(nex)
            count += 1

    return g
gp = dfs(ep,gp)
gr = dfs(er,gr)
l = []
dic = {}
for i in range(n):
    s = (gp[i],gr[i])
    l.append(s)
    if s in dic:
        dic[s] += 1
    else:
        dic[s] = 1
ans = []
for i in range(n):
    ans.append(dic[l[i]])
print(*ans)

Solution (Python):
from collections import deque

n,k,l = map(int,input().split())
ep = [[] for i in range(n)]
er = [[] for i in range(n)]

gp = [-1]*n
gr = [-1]*n

for i in range(k):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    ep[a].append(b)
    ep[b].append(a)
for i in range(l):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    er[a].append(b)
    er[b].append(a)

def dfs(e,g):
    count = 0
    for i in range(n):
        if g[i] == -1:
            g[i] = count

            q = deque([])
            q.append(i)
            while q:
                now = q.pop()

                for nex in e[now]:
                    if g[nex] == -1:
                        g[nex] = g[now]
                        q.append(nex)
            count += 1

    return g
gp = dfs(ep,gp)
gr = dfs(er,gr)
l = []
dic = {}
for i in range(n):
    s = (gp[i],gr[i])
    l.append(s)
    if s in dic:
        dic[s] += 1
    else:
        dic[s] = 1
ans = [0]*n

for i in range(n):
    ans[i] = dic[l[i]]
print(*ans)

Solution (Python):
from collections import deque

n,k,l = map(int,input().split())
ep = [[] for i in range(n)]
er = [[] for i in range(n)]

gp = [-1]*n
gr = [-1]*n

for i in range(k):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    ep[a].append(b)
    ep[b].append(a)
for i in range(l):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    er[a].append(b)
    er[b].append(a)

def dfs(e,g):
    count = 0
    for i in range(n):
        if g[i] == -1:
            g[i] = count

            q = deque([])
            q.append(i)
            while q:
                now = q.pop()

                for nex in e[now]:
                    if g[nex] == -1:
                        g[nex] = g[now]
                        q.append(nex)
            count += 1

    return g
gp = dfs(ep,gp)
gr = dfs(er,gr)
l = []
dic = {}
for i in range(n):
    s = (gp[i],gr[i])
    l.append(s)
    if s in dic:
        dic[s] += 1
    else:
        dic[s] = 1
ans = [0]*n

for i in range(n):
    ans[i] = dic[l[i]]
print(*ans)

Solution (Python):
import sys
import itertools

import time

sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

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

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

    def is_same(self, x, y):
        return self.link[x] == self.link[y]

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

        if self.size[x] < self.size[y]:
            x, y = y, x
        self.link[y] = x
        self.size[x] += self.size[y]
    
    def get_size(self, x):
        x = self.find(x)
        return self.size[x]



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

u1 = UnionFind(n)
u2 = UnionFind(n)


for i in range(k):
    p, q = map(lambda x: int(x) - 1, readline().split())
    u1.unite(p, q)

for i in range(l):
    r, s = map(lambda x: int(x) - 1, readline().split())
    u2.unite(r, s)

c = defaultdict(int)

for i in range(n):
    c[(u1.find(i), u2.find(i))] += 1

for i in range(n):
    print(c[u1.find(i), u2.find(i)])

Solution (Python):
from collections import defaultdict
import sys
sys.setrecursionlimit(10**9)
input=sys.stdin.readline
N,K,L=map(int,input().split())

def get_par(x):
  if x == par_list[x]:
    return x
  else:
    par_list[x] = get_par(par_list[x])
    return par_list[x]
def merge(x,y):
  par_x = get_par(x)
  par_y = get_par(y)
  if par_x != par_y:
    par_list[par_y] = par_x
def is_same(x,y):
  return get_par(x) == get_par(y)

par_list=list(range(N+1))
for _ in range(K):
  p,q=map(int,input().split())
  merge(p,q)
for i in range(1,N+1):
  par_list[i]=get_par(i)
par_list_road=par_list[:]
  
par_list=list(range(N+1))
for _ in range(L):
  r,s=map(int,input().split())
  merge(r,s)
for i in range(1,N+1):
  par_list[i]=get_par(i)
par_list_rail=par_list[:]



answer_dic=defaultdict(int)
for i in range(1,N+1):
  road_i=par_list_road[i]
  rail_i=par_list_rail[i]
  answer_dic[(road_i,rail_i)]+=1
  
answer_list=[]
for i in range(1,N+1):
  road_i=par_list_road[i]
  rail_i=par_list_rail[i]
  answer_list.append(answer_dic[(road_i,rail_i)])
  
print(*answer_list)

Solution (Python):

import sys
from collections import Counter
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,K,L=map(int,input().split())
    class UnionFind:
        def __init__(self,n):
            self.par=[i for i in range(n)]
            self.siz=[1]*n
            
        def root(self,x):
            while self.par[x]!=x:
                self.par[x]=self.par[self.par[x]]
                x=self.par[x]
            return x
        
        def unite(self,x,y):
            x=self.root(x)
            y=self.root(y)
            if x==y:
                return False
            if self.siz[x]<self.siz[y]:
                x,y=y,x
            self.siz[x]+=self.siz[y]
            self.par[y]=x
            return True
        
        def is_same(self,x,y):
            return self.root(x)==self.root(y)
        
        def size(self,x):
            return self.siz[self.root(x)]
    d=UnionFind(N)
    t=UnionFind(N)
    for _ in range(K):
        p,q=map(int1,input().split())
        d.unite(p,q)
    for _ in range(L):
        r,s=map(int1,input().split())
        t.unite(r,s)
    l=[]
    for i in range(N):
        l.append((d.root(i),t.root(i)))
    c=Counter(l)
    for i in range(N):
        print(c[l[i]],end=' ')

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict


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

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

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

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

N, K, L = map(int, input().split())
un1 = UnionFind(N)
for i in range(K):
    p, q = map(int, input().split())
    p -= 1
    q -= 1
    un1.unite(p, q)
un2 = UnionFind(N)
for i in range(L):
    r, s = map(int, input().split())
    r -= 1
    s -= 1
    un2.unite(r, s)
dic = defaultdict(int)
for i in range(N):
    a, b = un1.root(i), un2.root(i)
    k = str(a)+":"+str(b)
    dic[k] += 1

ans = [0]*N
for i in range(N):
    a, b = un1.root(i), un2.root(i)
    k = str(a)+":"+str(b)
    ans[i] = dic[k]
print(*ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict


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

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

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

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

N, K, L = map(int, input().split())
un1 = UnionFind(N)
for i in range(K):
    p, q = map(int, input().split())
    p -= 1
    q -= 1
    un1.unite(p, q)
un2 = UnionFind(N)
for i in range(L):
    r, s = map(int, input().split())
    r -= 1
    s -= 1
    un2.unite(r, s)
dic = defaultdict(int)
for i in range(N):
    a, b = un1.root(i), un2.root(i)
    k = str(a)+":"+str(b)
    dic[k] += 1

ans = [0]*N
for i in range(N):
    a, b = un1.root(i), un2.root(i)
    k = str(a)+":"+str(b)
    ans[i] = dic[k]
print(*ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict

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


G1 = [[] for i in range(N)]
for i in range(K):
    p, q = map(int, input().split())
    p -= 1
    q -= 1
    G1[p].append(q)
    G1[q].append(p)
gids = [0]*N
done = [False]*N
def dfs1(i, gid):
    gids[i] = gid
    done[i] = True
    for nex in G1[i]:
        if done[nex]: continue
        dfs1(nex, gid)
gid = 0
for i in range(N):
    if not done[i]:
        dfs1(i, gid)
        gid += 1


G = [[] for i in range(N)]
for i in range(L):
    r, s = map(int, input().split())
    r -= 1
    s -= 1
    G[r].append(s)
    G[s].append(r)
done = [False]*N
D = []
gids2 = [0]*N
def dfs(i, gid):
    D[gid][gids[i]] += 1
    done[i] = True
    gids2[i] = gid
    for nex in G[i]:
        if done[nex]: continue
        dfs(nex, gid)
gid = 0
for i in range(N):
    if not done[i]:
        D.append(defaultdict(int))
        dfs(i, gid)
        gid += 1


ans = [0]*N
for i in range(N):
    ans[i] = D[gids2[i]][gids[i]]
print(*ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict

N, K, L = map(int, input().split())
G1 = [[] for i in range(N)]
for i in range(K):
    p, q = map(int, input().split())
    p -= 1
    q -= 1
    G1[p].append(q)
    G1[q].append(p)
gids = [0]*N
done = [False]*N
def dfs1(i, gid):
    gids[i] = gid
    done[i] = True
    for nex in G1[i]:
        if done[nex]: continue
        dfs1(nex, gid)
gid = 0
for i in range(N):
    if not done[i]:
        dfs1(i, gid)
        gid += 1

G = [[] for i in range(N)]
for i in range(L):
    r, s = map(int, input().split())
    r -= 1
    s -= 1
    G[r].append(s)
    G[s].append(r)
done = [False]*N
D = []
gid = 0
def dfs(i, gid):
    D[gid][gids[i]] += 1
    done[i] = True
    for nex in G[i]:
        if done[nex]: continue
        dfs(nex, gid)
for i in range(N):
    if not done[i]:
        D.append(defaultdict(int))
        dfs(i, gid)
        gid += 1
ans = [0]*N
done = [False]*N
gid = 0
def dfs2(i, gid):
    done[i] = True
    ans[i] = D[gid][gids[i]]
    for nex in G[i]:
        if done[nex]: continue
        dfs2(nex, gid)
for i in range(N):
    if not done[i]:
        dfs2(i, gid)
        gid += 1
print(*ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict


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

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

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

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

N, K, L = map(int, input().split())
un = UnionFind(N)
for i in range(K):
    p, q = map(int, input().split())
    p -= 1
    q -= 1
    un.unite(p, q)
G = [[] for i in range(N)]
for i in range(L):
    r, s = map(int, input().split())
    r -= 1
    s -= 1
    G[r].append(s)
    G[s].append(r)
done = [False]*N
D = []
gid = 0
def dfs(i, gid):
    D[gid][un.root(i)] += 1
    done[i] = True
    for nex in G[i]:
        if done[nex]: continue
        dfs(nex, gid)
for i in range(N):
    if not done[i]:
        D.append(defaultdict(int))
        dfs(i, gid)
        gid += 1
ans = [0]*N
done = [False]*N
gid = 0
def dfs2(i, gid):
    done[i] = True
    ans[i] = D[gid][un.root(i)]
    for nex in G[i]:
        if done[nex]: continue
        dfs2(nex, gid)
for i in range(N):
    if not done[i]:
        dfs2(i, gid)
        gid += 1
print(*ans)

Solution (Python):
from collections import Counter


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

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

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

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return
        if self.parent[root_x] > self.parent[root_y]:
            root_x, root_y = root_y, root_x
        self.parent[root_x] += self.parent[root_y]
        self.parent[root_y] = root_x

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

    def members(self, x, is_set=False):
        root = self.find(x)
        res = [i for i in range(self.node) if self.find(i) == root]
        if is_set:
            return set(res)
        return res

    def all_root(self):
        return [idx for idx, val in enumerate(self.parent) if val < 0]


def main():
    cities, roads, railroads = map(int, input().split())
    uf_road = UnionFind(cities)
    uf_train = UnionFind(cities)
    for _ in range(roads):
        p, q = map(lambda x: int(x) - 1, input().split())
        uf_road.union(p, q)
    for _ in range(railroads):
        r, s = map(lambda x: int(x) - 1, input().split())
        uf_train.union(r, s)
    each_pair = []
    for i in range(cities):
        each_pair.append(tuple([uf_road.find(i), uf_train.find(i)]))
    pair_count = dict(Counter(each_pair))
    answer = [pair_count[each_pair[i]] for i in range(cities)]
    print(" ".join(map(str, answer)))


if __name__ == '__main__':
    main()

Solution (Python):

class UnionFind:
    def __init__(self, n):
        
        
        self.table = [-1] * n
 
    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 find(self, x, y):
        return self._root(x) == self._root(y)
 
    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2
 
 
if __name__ == '__main__':
    n,k,l=map(int,input().split())
    pq=UnionFind(n+1)
    rs=UnionFind(n+1)
    for i in range(k):
        p,q=map(int,input().split())
        pq.union(p,q)
    for i in range(l):
        r,s=map(int,input().split())
        rs.union(r,s)
    sameroot=[]
    for i in range(1,n+1):
        sameroot.append([pq._root(i),rs._root(i),i])
    sameroot.sort()
    sameroot.append([0,0,n+1])
    cnt=[0]*(n+1)
    bx,by=0,0
    samelist=[]
    for x,y,i in sameroot:
        if bx==x and by==y:
            samelist.append(i)
        else:
            k=len(samelist)
            if k>0:
                for j in samelist:
                    cnt[j]=k
            samelist=[i]
            bx,by=x,y
    print(' '.join(map(str,cnt[1:])))

Solution (Python):
from collections import Counter

class UnionFind:
    
    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n)]
        self.rank = [0] * n
    
    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    
    def unite(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
        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)

    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]


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

uf_road = UnionFind(N)
uf_train = UnionFind(N)

for road in roads:
    x, y = road
    uf_road.unite(x-1, y-1)

for train in trains:
    x, y = train
    uf_train.unite(x-1, y-1)

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

cnt = Counter(pairs)

ans = [cnt[pair] for pair in pairs]
print(*ans)

Solution (Python):
import sys
input = sys.stdin.buffer.readline
from collections import defaultdict
def main():
    def find(x):
        if par[x] < 0:
            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 False
        else:
            if par[x] > par[y]:
                x, y = y, x
            par[x] += par[y]
            par[y] = x
            return True
    def members(x):
        root = find(x)
        return [i for i in range(n) if find(i) == root]

    def find2(x):
        if par2[x] < 0:
            return x
        else:
            par2[x] = find2(par2[x])
            return par2[x]
    def unite2(x, y):
        x = find2(x)
        y = find2(y)
        if x == y:
            return False
        else:
            if par2[x] > par2[y]:
                x, y = y, x
            par2[x] += par2[y]
            par2[y] = x
            return True
    def members2(x):
        root2 = find2(x)
        return [i for i in range(n) if find2(i) == root2]

    n, k, l = map(int, input().split())
    par = [-1] * n
    par2 = [-1] * n
    for _ in range(k):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        unite(a, b)
    for _ in range(l):
        c, d = map(int, input().split())
        c -= 1
        d -= 1
        unite2(c, d)

    root_pairs = defaultdict(int)
    for i in range(n):
        root_pairs[find(i), find2(i)] += 1

    for i in range(n):
        print(root_pairs[find(i), find2(i)], end=' ')

if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter

def road_find(a):
    if Road[a] < 0:
        return a
    else:
        return road_find(Road[a])


def train_find(a):
    if Train[a] < 0:
        return a
    else:
        return train_find(Train[a])


def road_union(a, b):
    ag = road_find(a)
    bg = road_find(b)
    if ag == bg:
        return
    if Road[ag] > Road[bg]:
        ag, bg = bg, ag
    Road[ag] += Road[bg]
    Road[bg] = ag
    return


def train_union(a, b):
    ag = train_find(a)
    bg = train_find(b)
    if ag == bg:
        return
    if Train[ag] > Train[bg]:
        ag, bg = bg, ag
    Train[ag] += Train[bg]
    Train[bg] = ag
    return


N, K, L = map(int, input().split())
Road = [-1] * N
Train = [-1] * N

for road in range(K):
    p, q = map(int, input().split())
    p -= 1
    q -= 1
    road_union(p, q)

for train in range(L):
    p, q = map(int, input().split())
    p -= 1
    q -= 1
    train_union(p, q)

Ans = []
for i in range(N):
    Ans.append((road_find(i),train_find(i)))

Ans_C = Counter(Ans)

for i in range(N):
    print(Ans_C[(road_find(i),train_find(i))])

Solution (Python):
from collections import Counter

class UnionFind():
    
    
    def __init__(self, n):
        self.n = n
        
        
        self.root = [-1]*(n+1)
        
        self.rnk = [0]*(n+1)

    
    def find_root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            
            
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]
    
    def unite(self, x, y):
        
        x = self.find_root(x)
        y = self.find_root(y)
        
        if(x == y):
            return
        
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    def isSame(self, x, y):
        return self.find_root(x) == self.find_root(y)

    
    def size(self, x):
        return -self.root[self.find_root(x)]
        
n,k,l = map(int,input().split())
fe = UnionFind(n)
bus = UnionFind(n)
for _ in range(k):
    p,q = map(int,input().split())
    fe.unite(p,q)
for _ in range(l):
    r,s = map(int,input().split())
    bus.unite(r,s)
cnt = Counter()
for i in range(1,n+1):
    cnt[fe.find_root(i),bus.find_root(i)] += 1

print(*[cnt[fe.find_root(i),bus.find_root(i)]for i in range(1,n+1)])

Solution (Python):

import sys
input = sys.stdin.readline
import numpy as np




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)




N,K,L = map(int,input().split())
PQ = [tuple(map(int,input().split())) for _ in range(K)]
RS = [tuple(map(int,input().split())) for _ in range(L)]


A = UnionFind(N)
for p,q in PQ:
    A.unite(p-1,q-1)
 

B = UnionFind(N)
for r,s in RS:
    B.unite(r-1,s-1)


from collections import defaultdict
dic = defaultdict(int)
for i in range(N):
    dic[A.find(i), B.find(i)] += 1
 
Ans = list(dic[A.find(i), B.find(i)] for i in range(N))
print(" ".join(map(str,Ans)))

Solution (Python):
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]
    def is_same(self, x, y):
        return self.find(x) == self.find(y)
    def get_size(self, x):
        x = self.find(x)
        return self.size[x]
import collections
N,K,L=map(int,input().split())
uf1=UnionFind(N)
for i in range(K):
  p,q=map(int,input().split())
  uf1.union(p-1,q-1)
uf2=UnionFind(N)
for j in range(L):
  r,s=map(int,input().split())
  uf2.union(r-1,s-1)
list=[]
for i in range(N):
  list.append((uf1.find(i),uf2.find(i)))
count=collections.Counter(list)
for i in range(N):
  ans=count[list[i]]
  if i==N-1:
    print(ans)
  else:
    print(ans,end=' ')

Solution (Python):
"""
道路でつながっているやつが鉄道でもつながっているかどうかを調べるにはどうすればいい？
普通に木ごとのサイズを求めておけばいいのか？

道路ネットワークを根ごとにグルーピングする。その中で、さらに鉄道の根ごとにグルーピングする。
でchooseでペア数を求めれば良い。

"""
import math
import sys
sys.setrecursionlimit(200000)
class UnionFind():
    def __init__(self,n):
        self.parents = [i for i in range(n+1)]

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

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

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

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


group = {}
for i in range(1,N+1):
    roadRoot = A.find(i)
    if roadRoot not in group:
        group[roadRoot] = {}
    railRoot = B.find(i)
    if railRoot not in group[roadRoot]:
        group[roadRoot][railRoot] = []
    group[roadRoot][railRoot].append(i)

ans = [[]for _ in range(N)]
for i in group.items():
    for j in i[1].values():
        for k in j:
            ans[k-1] = str(len(j))

ans = " ".join(ans)
print(ans)

Solution (Python):
from collections import Counter
n,k,l=map(int,input().split())
city1=[i for i in range(n)]
city2=[i for i in range(n)]
def root(c,x):
  if x==c[x]:
    return x
  else:
    c[x]=root(c,c[x])
    return c[x]
def union(c,x,y):
  rx=root(c,x)
  ry=root(c,y)
  if rx>ry:
    c[rx]=ry
  else:
    c[ry]=rx
for i in range(k):
  a,b=map(int,input().split())
  union(city1,a-1,b-1)
for i in range(l):
  a,b=map(int,input().split())
  union(city2,a-1,b-1)
r=[]
for i in range(n):
  r.append((root(city1,i),root(city2,i)))
c=Counter(r)
for i in range(n):
  ans=c[r[i]]
  if i==n-1:
    print(ans)
  else:
    print(ans,end=' ')

Solution (Python):
from collections import Counter
n,k,l=map(int,input().split())
city1=[i for i in range(n)]
city2=[i for i in range(n)]
def root(c,x):
  if x==c[x]:
    return x
  else:
    return root(c,c[x])
def union(c,x,y):
  rx=root(c,x)
  ry=root(c,y)
  if rx>ry:
    c[rx]=ry
  else:
    c[ry]=rx
for i in range(k):
  a,b=map(int,input().split())
  union(city1,a-1,b-1)
for i in range(l):
  a,b=map(int,input().split())
  union(city2,a-1,b-1)
r=[]
for i in range(n):
  r.append((root(city1,i),root(city2,i)))
c=Counter(r)
for i in range(n):
  ans=c[r[i]]
  if i==n-1:
    print(ans)
  else:
    print(ans,end=' ')

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

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]
    def find(self, x):
        """
        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 と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]
    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)
    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]


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

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

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


for i in range(N):
    print(c[(uf1.find(i), uf2.find(i))])