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,n):
    self.n=n
    self.parents=[-1]*n
  def find(self,x):
    if self.parents[x]<0:
      return x
    else:
      self.parents[x]=self.find(self.parents[x])
      return self.parents[x]
  def unite(self,x,y):
    x=self.find(x)
    y=self.find(y)
    if x==y:
      return
    if self.parents[x]>self.parents[y]:
      x,y=y,x
    self.parents[x]+=self.parents[y]
    self.parents[y]=x
  def size(self,x):
    return -size.parents[self.find(x)]
  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]
  def roots(self):
    return [i for i,x in enumerate(self.parents) if x<0]
  def group_count(self):
    return len(self.roots())
  def all_group_members(self):
    return {r:self.members(r) for r in self.roots()}
n,k,l=map(int,input().split())
uf1=UnionFind(n)
for _ in range(k):
  u,v=map(int,input().split())
  uf1.unite(u-1,v-1)
uf2=UnionFind(n)
for _ in range(l):
  u,v=map(int,input().split())
  uf2.unite(u-1,v-1)
d=defaultdict(int)
for i in range(n):
  d[(uf1.find(i),uf2.find(i))]+=1
ans=[d[(uf1.find(i),uf2.find(i))] for i in range(n)]
print(*ans)

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.group_count = n

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

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

        if x == y:
            return

        self.group_count -= 1

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

    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]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

def int_(num_str):
    return int(num_str) - 1


N, K, L = map(int, input().split())
uf1 = UnionFind(N)
for _ in range(K):
    p, q = map(int_, input().split())
    uf1.union(p, q)
uf2 = UnionFind(N)
for _ in range(L):
    r, s = map(int_, input().split())
    uf2.union(r, s)
from collections import Counter
pair = [(uf1.find(i), uf2.find(i)) for i in range(N)]
ans = Counter(pair)
print(*[ans[p] for p in pair])

Solution (Python):
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class UnionFind:
    def __init__(self, n):
        self.state = [-1] * n
        
        
        

    def root(self, u):
        v = self.state[u]
        if v < 0: return u
        self.state[u] = res = self.root(v)
        return res

    def merge(self, u, v):
        ru = self.root(u)
        rv = self.root(v)
        if ru == rv: return
        du = self.state[ru]
        dv = self.state[rv]
        if du > dv: ru, rv = rv, ru
        if du == dv: self.state[ru] -= 1
        self.state[rv] = ru
        
        
        
        return

def main():
    n,k,l=MI()
    road=UnionFind(n)
    train=UnionFind(n)
    for _ in range(k):
        u,v=MI1()
        road.merge(u,v)
    for _ in range(l):
        u,v=MI1()
        train.merge(u,v)
    cnt=defaultdict(int)
    for u in range(n):
        cnt[road.root(u),train.root(u)]+=1
    ans=[cnt[road.root(u),train.root(u)] for u in range(n)]
    print(*ans)

main()

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        root = x
        while self.parents[root] != root:
            root = self.parents[root]
        while self.parents[x] != root:
            parent = self.parents[x]
            self.parents[x] = root
            x = parent
        return root

    def unite(self, x, y):
        xroot = self.find(x)
        yroot = self.find(y)
        if xroot == yroot:
            return
        xrank = self.rank[xroot]
        yrank = self.rank[yroot]
        if xrank < yrank:
            self.parents[xroot] = yroot
            self.size[yroot] += self.size[xroot]
        elif xrank == yrank:
            self.parents[yroot] = xroot
            self.rank[yroot] += 1
            self.size[xroot] += self.size[yroot]
        else:
            self.parents[yroot] = xroot
            self.size[xroot] += self.size[yroot]

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

    def roots(self):
        return [i for i in range(N) if self.rank[i] == 0]

from collections import defaultdict

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

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

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

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

D = defaultdict(int)

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

res = []

for i in range(N):
    res.append(D[(uf1.find(i), uf2.find(i))])

print(' '.join(map(str, res)))

Solution (Python):
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 find2(x):
    if pa[x] < 0:
        return x
    else:
        pa[x] = find2(pa[x])
        return pa[x]

  import sys
  input = sys.stdin.readline

  n,k,l = [int(i) for i in input().split()]
  par = [-1]*n
  pa = [-1]*n
  ans = [0]*n

  for i in range(k):
    p,q = [int(i) for i in input().split()]
    unite(p-1,q-1)

  def unite2(x,y):
      x = find2(x)
      y = find2(y)
      if x == y:
          return False
      else:
          if pa[x] > pa[y]:
              x,y = y,x
          pa[x] += pa[y]
          pa[y] = x
          return True

  for i in range(l):
    r,s = [int(i) for i in input().split()]
    unite2(r-1,s-1)

  dic = {}
  chk = []
  for i in range(n):
      p1 = find(i)
      p2 = find2(i)
      chk.append((p1,p2))
      if (p1,p2) in dic:
          dic[(p1,p2)] += 1
      else: 
          dic[(p1,p2)] = 1
  print(' '.join([str(dic[chk[i]]) for i in range(n)]))
  
if __name__ == '__main__':
    main()

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    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]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())
import sys
input=sys.stdin.readline
n,k,l = map(int, input().split())
uf_road = UnionFind(n)
uf_train = UnionFind(n)
for i in range(k):
    p,q=list(map(int, input().split()))
    uf_road.union(p-1, q-1)
for i in range(l):
    p,q=list(map(int, input().split()))
    uf_train.union(p-1, q-1)

from collections import defaultdict
d = defaultdict(int)
for i in range(n):
    d[uf_road.find(i), uf_train.find(i)] += 1
print(*(d[uf_road.find(i), uf_train.find(i)] for i in range(n)))

Solution (Python):
import sys
from collections import defaultdict


def input(): return sys.stdin.readline().rstrip()


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.root(x)]

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

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

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():

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

    for _ in range(K):
        a, b = map(int, input().split())
        highway.unite(a - 1, b - 1)

    for _ in range(L):
        a, b = map(int, input().split())
        railroad.unite(a - 1, b - 1)

    d = defaultdict(int)
    for i in range(N):
        d[highway.root(i), railroad.root(i)] += 1
    print(*(d[highway.root(i), railroad.root(i)] for i in range(N)))


if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter
N,K,L=map(int,input().split())
drive = [-1] * N;train = [-1] * N
def find(List,x):
  if List[x] < 0:
    return x
  List[x] = find(List,List[x])
  return List[x]
def unite(List,x,y):
  if find(List,x) != find(List,y):
    List[find(List,y)] = find(List,x)
for i in range(K+L):
  a, b = map(int,input().split())
  unite(drive if i < K else train,a-1, b-1)
pair = [(find(drive,i), find(train,i)) for i in range(N)]
c =Counter(pair)
print(*[c[pair[i]] for i in range(N)])

Solution (Python):
import collections
class UnionFind:
    def __init__(self,n):
        super().__init__()
        self.par = [-1]*n
        self.rank = [0]*n
        self.tsize = [1]*n

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

        elif self.rank[x_r]<self.rank[y_r]:
            self.par[x_r] = y_r

        elif x_r != y_r:
            self.par[y_r] = x_r
            self.rank[x_r] += 1

        if x_r != y_r:
            size = self.tsize[x_r]+self.tsize[y_r]
            self.tsize[x_r] = size
            self.tsize[y_r] = size

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

    def size(self,x):
        return self.tsize[self.root(x)]

def main():
    n,k,l = tuple([int(t)for t in input().split()])

    uf_k = UnionFind(n)
    uf_l = UnionFind(n)


    pq = [[int(t)-1 for t in input().split()]for _ in [0]*k]
    for p,q in pq:
        uf_k.unite(p,q)

    rs = [[int(t)-1 for t in input().split()]for _ in [0]*l]
    for r,s in rs:
        uf_l.unite(r,s)

    pair = []
    for i in range(n):
        pair.append((uf_k.root(i),uf_l.root(i)))
    counter = collections.Counter(pair)
    
    ans = []
    for a in pair:
        ans.append(counter[a])
    print(*ans)
    
if __name__ == "__main__":
    main()

Solution (Python):
import collections
class UnionFind:
    def __init__(self,n):
        super().__init__()
        self.par = [-1]*n
        self.rank = [0]*n
        self.tsize = [1]*n

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

        elif self.rank[x_r]<self.rank[y_r]:
            self.par[x_r] = y_r

        elif x_r != y_r:
            self.par[y_r] = x_r
            self.rank[x_r] += 1

        if x_r != y_r:
            size = self.tsize[x_r]+self.tsize[y_r]
            self.tsize[x_r] = size
            self.tsize[y_r] = size

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

    def size(self,x):
        return self.tsize[self.root(x)]

def main():
    n,k,l = tuple([int(t)for t in input().split()])

    uf_k = UnionFind(n)
    uf_l = UnionFind(n)


    pq = [[int(t)-1 for t in input().split()]for _ in [0]*k]
    for p,q in pq:
        uf_k.unite(p,q)

    rs = [[int(t)-1 for t in input().split()]for _ in [0]*l]
    for r,s in rs:
        uf_l.unite(r,s)

    pair = []
    for i in range(n):
        pair.append((uf_k.root(i),uf_l.root(i)))
    counter = collections.Counter(pair)
    
    ans = []
    for a in pair:
        ans.append(counter[a])
    print(*ans)
    
if __name__ == "__main__":
    main()

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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

    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]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N, K, L = list(map(int, input().split()))
uf_road = UnionFind(N)
uf_train = UnionFind(N)

for i in range(K):
    node1, node2 = map(int, input().split())
    uf_road.union(node1 - 1, node2 - 1)

for i in range(L):
    node1, node2 = map(int, input().split())
    uf_train.union(node1 - 1, node2 - 1)



d = defaultdict(int)
for i in range(N):
    d[uf_road.find(i), uf_train.find(i)] += 1
print(*(d[uf_road.find(i), uf_train.find(i)] for i in range(N)))

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


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

    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]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


n, k, l = map(int, input().split())
uf_k = UnionFind(n)
uf_l = UnionFind(n)
for i in range(k):
    p, q = map(int, input().split())
    uf_k.union(p - 1, q - 1)
for i in range(l):
    r, s = map(int, input().split())
    uf_l.union(r - 1, s - 1)
d = defaultdict(int)
for i in range(n):
    d[uf_k.find(i), uf_l.find(i)] += 1
print(*(d[uf_k.find(i), uf_l.find(i)] for i in range(n)))

Solution (Python):

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 
    if self.root[x] > self.root[y]:
      x, y = y, x
    self.root[x] += self.root[y]
    self.root[y] = x 
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)
  def Count(self, x): 
    return -self.root[self.Find_Root(x)]
  def Members(self, x): 
    return [i for i in range(self.n) if self.Find_Root(i)==self.Find_Root(x)]
  def Roots(self): 
    return [i for i, x in enumerate(self.root) if x < 0]
  def Group_Count(self): 
    return len(self.Roots())

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

uf_road = UnionFind(n)
uf_train = UnionFind(n)

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

for _ in range(l):
  r, s = map(lambda x:int(x)-1, input().split())
  uf_train.Unite(r, s)

root_road = [0]*n 
root_train = [0]*n 

for i in range(n):
  root_road[i] = uf_road.Find_Root(i)
  root_train[i] = uf_train.Find_Root(i)

from collections import defaultdict
pair = defaultdict(int)
for i in range(n):
  pair[(root_road[i], root_train[i])] += 1 

for i in range(n):
  print(pair[(root_road[i], root_train[i])], end=" ")

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

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

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

    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]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def renketu(n , k , l , pqli , rsli):

    from collections import defaultdict

    ans = []
    pquf = UnionFind(n)
    rsuf = UnionFind(n)

    [pquf.unite(p - 1 , q - 1) for q , p in pqli]
    [rsuf.unite(r - 1 , s - 1) for r , s in rsli]

    ansdict = defaultdict(int)

    for i in range(n):
        ansdict[(pquf.find(i) , rsuf.find(i))] += 1

    for i in range(n):
        ans.append(ansdict[(pquf.find(i) , rsuf.find(i))])

    return ans

def main():
    n, k, l = map(int, input().split())
    pqli = [list(map(int , input().split())) for i in range(k)]
    rsli = [list(map(int , input().split())) for i in range(l)]
    ans = renketu(n , k , l , pqli , rsli)

    print(*ans)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    
    def root(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]
    
    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)

        if x == y:
            return False
        
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

    def size(self, x):
        return -self.parents[self.root(x)]
    
    def members(self, x):
        x_root = self.root(x)
        return [i for i in range(self.n) if self.root(i) == x_root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    
    def group_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return "\n".join("{}: {}".format(r, self.members(r)) for r in self.roots())

def main():
    N, K, L = map(int, input().split())
    uf_road = UnionFind(N)
    uf_railway = UnionFind(N)
    pq = [tuple(map(int, input().split())) for i in range(K)]

    [uf_road.unite(p-1, q-1) for p, q in pq]

    rs = [tuple(map(int, input().split())) for i in range(L)]


    [uf_railway.unite(r-1, s-1) for r, s in rs]
    
    d = defaultdict(int)
    
    for i in range(N):
        d[(uf_road.root(i), uf_railway.root(i))] += 1
    
    for i in range(N):
        print(d[(uf_road.root(i), uf_railway.root(i))])
    
if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    
    def root(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]
    
    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)

        if x == y:
            return False
        
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

    def size(self, x):
        return -self.parents[self.root(x)]
    
    def members(self, x):
        x_root = self.root(x)
        return [i for i in range(self.n) if self.root(i) == x_root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    
    def group_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return "\n".join("{}: {}".format(r, self.members(r)) for r in self.roots())

def main():
    N, K, L = map(int, input().split())
    uf_road = UnionFind(N)
    uf_railway = UnionFind(N)
    pq = [tuple(map(int, input().split())) for i in range(K)]
    for p, q in pq:
        uf_road.unite(p-1, q-1)
    rs = [tuple(map(int, input().split())) for i in range(L)]
    for r, s in rs:
        uf_railway.unite(r-1, s-1)
    
    d = defaultdict(int)
    for i in range(N):
        d[(uf_road.root(i), uf_railway.root(i))] += 1
    
    for i in range(N):
        print(d[(uf_road.root(i), uf_railway.root(i))])
    
if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    
    def root(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]
    
    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)

        if x == y:
            return False
        
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

    def size(self, x):
        return -self.parents[self.root(x)]
    
    def members(self, x):
        x_root = self.root(x)
        return [i for i in range(self.n) if self.root(i) == x_root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    
    def group_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return "\n".join("{}: {}".format(r, self.members(r)) for r in self.roots())

def main():
    N, K, L = map(int, input().split())
    uf_road = UnionFind(N)
    uf_railway = UnionFind(N)
    pq = [tuple(map(int, input().split())) for i in range(K)]
    for p, q in pq:
        uf_road.unite(p-1, q-1)
    rs = [tuple(map(int, input().split())) for i in range(L)]
    for r, s in rs:
        uf_railway.unite(r-1, s-1)
    
    d = defaultdict(int)
    for i in range(N):
        d[(uf_road.root(i), uf_railway.root(i))] += 1
    
    for i in range(N):
        print(d[(uf_road.root(i), uf_railway.root(i))])
    
if __name__ == "__main__":
    main()

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

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            if self.parent[y] < self.parent[x]:
                x, y = y, x
            self.parent[x] += self.parent[y]
            self.parent[y] = x
            self._size -= 1

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

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

    def size(self, x):
        return -self.parent[self.root(x)]


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

uf_tree1 = UnionFind(N)
uf_tree2 = UnionFind(N)

for _ in range(K):
    p, q = map(int, input().split())
    p -= 1; q -= 1;
    uf_tree1.unite(p, q)

for _ in range(L):
    r, s = map(int, input().split())
    r -= 1; s -= 1;
    uf_tree2.unite(r, s)

d = {}
for i in range(N):
    pair = (uf_tree1.root(i), uf_tree2.root(i))
    d[pair] = d.get(pair, 0) + 1

for i in range(N):
    pair = (uf_tree1.root(i), uf_tree2.root(i))
    print(d[pair], end = "")
    print("\n" if i == N-1 else " ", end = "")

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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

    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]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    N, K, L = map(int,input().split())
    road = UnionFind(N)
    train = UnionFind(N)

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

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


    D = dict()
    P = [0]*N
    for k in range(N):
        t = (10**6)*(train.find(k)+1)+road.find(k)
        P[k] = t
        if t in D:
            D[t] += 1
        else:
            D[t] = 1
    ans = []
    for k in range(N):
        ans.append(D[P[k]])
    print(*ans)


if __name__ == '__main__':
    main()