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



Sample input:
4 3 1
1 2
2 3
3 4
2 3


Sample output:
1 2 2 1

Submission status: Accepted

Solution code:
from collections import Counter


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

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return 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
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1


def main():
    n, k, l = map(int, input().split())
    a = UnionFind(n)
    b = UnionFind(n)
    for _ in range(k):
        p, q = map(int, input().split())
        a.union(p-1, q-1)
    for _ in range(l):
        r, s = map(int, input().split())
        b.union(r-1, s-1)
    d = Counter((a._root(i), b._root(i)) for i in range(n))
    print(*(d[(a._root(i), b._root(i))] for i in range(n)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFindTree:
    def __init__(self, n):
        self.nodes = [-1] * n #根にサイズを負の値で格納する。
    def find(self, i):
        if self.nodes[i] < 0: #値が負の場合は根
            return i
        else:
            self.nodes[i] = self.find(self.nodes[i]) #縮約
            return self.nodes[i]

    def union(self, i, j):
        i = self.find(i)
        j = self.find(j)
        if i == j:
            return
        if self.nodes[i] > self.nodes[j]: #サイズ比較してiの方がサイズが大きいようにする
            i, j = j, i
        self.nodes[i] += self.nodes[j] #大きい方に小さい方を統合しサイズを登録する。
        self.nodes[j] = i # jの親はi
    
    def size(self, i): # 所属する集合の大きさを返す
        i = self.find(i)
        return -self.nodes[i]


n, k, l = map(int, input().split())
roads = UnionFindTree(n)
railways = UnionFindTree(n)
ans = []
for _ in range(k):
    a, b = map(lambda x : int(x) - 1, input().split())
    roads.union(a, b)
    
for _ in range(l):
    a, b = map(lambda x : int(x) - 1, input().split())
    railways.union(a, b)

counter = dict()
for i in range(n):
    p = (roads.find(i), railways.find(i))
    if not p in counter:
        counter[p] = 1
    else:
        counter[p] += 1

ans = [counter[(roads.find(i), railways.find(i))] for i in range(n)]
print(" ".join(map(str, ans)))

Submission status: Accepted

Solution code:
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########
class UnionFind():
    def __init__(self,num):
        self.n = num         #class内変数nに、外部から入力した値numを代入
        self.parents = [-1 for i in range(self.n)]
          #parentsは要素の親(1こ上のやつ)番号0~n-1を格納、自分が最親なら-(要素数)を格納(初期値は-1)

    #xの最親は誰？
    def find(self,x):
        if self.parents[x]<0:
            return x
        else:
            self.parents[x]=self.find(self.parents[x]) #再帰して1番上までいってる
                #調べながらparentsの値を更新してる！（経路圧縮）
            return self.parents[x]

    #結合せよ
    #xの親とyの親をくっつける
    def union(self,x,y):
        xx=self.find(x)  #xxはxの最親
        yy=self.find(y)  #yyはyの最親
        if xx==yy:
            return     #同じ屋根の下にあった場合は何もしない
        else:
            size_xx=abs(self.parents[xx]) #xが含まれる木のサイズ
            size_yy=abs(self.parents[yy]) #yが含まれる木のサイズ
            if size_xx>size_yy:
                xx,yy=yy,xx  #yyの方が大きい木、ってことにする

            self.parents[yy]+=self.parents[xx] #大きい木のサイズ更新
            self.parents[xx]=yy   #サイズが小さい木を大きい木に接ぐ

    #xの属する木の大きさ（まあunionでも使ったけど）
    def size(self,x):
        xx=self.find(x)
        return abs(self.parents[xx])

    #xとyはこの空の続く場所にいますか　いつものように笑顔でいてくれますか　今はただそれを願い続ける
    def same(self,x,y):
        return 1 if self.find(x)==self.find(y) else 0

    #xと　同じ木にいる　メンバーは？
    def members(self,x):
        xx=self.find(x)
        return [i for i in range(self.n) if self.find(i)==xx]
             #ifの条件式に漏れたら無視

    #最親だけを並べあげる
    def roots(self):
        return [i for i,x in enumerate(self.parents) if x < 0]
        #いやこれは天才すぎる、basisのenumerate.py参照

    #すべての最親について、メンバーを辞書で
    def all_group_members(self):
        return {r:self.members(r) for r in self.roots()}

    #グループ分けどうなりましたか、２重リストで
    def state_grouping(self):
        return list(self.all_group_members().values())

n,k,l=map(int,input().split())
uf=UnionFind(n)
uf2=UnionFind(n)
for i in range(k):
    p,q=map(int,input().split())
    p-=1;q-=1
    uf.union(p,q)
for i in range(l):
    p,q=map(int,input().split())
    p-=1;q-=1
    if 1:
        uf2.union(p,q)

C= Counter( [ ( uf.find(i),uf2.find(i) ) for i in range(n)] )
ANS=[0]*n 
for i in range(n):
    ANS[i]= C[(uf.find(i),uf2.find(i))]
print(*ANS)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.par = [-1]*n 
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)      
        if x==y:
            return        
        if self.par[x] > self.par[y]:
            x, y = y, x       
        self.par[x] += self.par[y]
        self.par[y] = x

N, K, L = map(int, input().split())
Uni_1 = UnionFind(N)
Uni_2 = UnionFind(N)
D = {}
for _ in range(K):
  p,q = map(int, input().split())
  Uni_1.union(p-1, q-1)
for _ in range(L):
  p,q = map(int, input().split())
  Uni_2.union(p-1, q-1)
for i in range(N):
  k = (Uni_1.find(i), Uni_2.find(i))
  if k in D.keys():
    D[k] += 1
  else:
    D[k] = 1
for i in range(N):
  print(D[(Uni_1.find(i), Uni_2.find(i))], end=" ")

Submission status: Accepted

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

def fp(x, parentList): #findParent
    if parentList[x] == x:
        return x
    else:
        parentList[x] = fp(parentList[x], parentList)
        return parentList[x]

#各ノードのparentをリストで表現(連結前は自身がparent)
road = [i for i in range(N)]
rail = [i for i in range(N)]

for _ in range(K):
    p, q = map(int, input().split())
    par_p, par_q = fp(p-1, road), fp(q-1, road) #p, qのparent 
    #連結する際、若い番号をparentとする
    if par_p < par_q:
        road[par_q] = par_p
    else:
        road[par_p] = par_q

#railについても同様
for _ in range(L):
    s, t = map(int, input().split())
    par_s, par_t = fp(s-1, rail), fp(t-1, rail)
    if par_s < par_t:
        rail[par_t] = par_s
    else:
        rail[par_s] = par_t

#連結成分の要素をカウント
cnt = {}
for i in range(N):
    key = (fp(i,road),fp(i,rail))
    if key in cnt:
        cnt[key] += 1
    else:
        cnt[key] = 1
#出力
for i in range(N):
    key = (fp(i,road),fp(i,rail))
    ans = cnt[key]
    print(ans, end=" ")

Submission status: Accepted

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

def root(x):
  while 0<=p[x]:
    x = p[x]
  return x

def unite(x,y):
  x = root(x)
  y = root(y)
  if x==y:
    return
  if x>y:
    x,y=y,x
  p[x]+=p[y]
  p[y]=x

def g(x):
  global p
  p=N*[-1]
  for _ in range(x):
    a,b = map(int,input().split())
    unite(a-1,b-1)
  return [root(n) for n in range(N)]

z = [*zip(g(K),g(L))]
C = Counter(z)
print(*[C[t] for t in z])

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

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

N, K, L = mapint()
uf_road = UnionFind(N)
for _ in range(K):
    x, y = mapint()
    uf_road.union(x-1, y-1)

uf_rail = UnionFind(N)
for _ in range(L):
    x, y = mapint()
    uf_rail.union(x-1, y-1)
from collections import Counter
lis = []
for i in range(N):
    road = uf_road.find(i)
    rail = uf_rail.find(i)
    lis.append(road*(10**6)+rail)
c = Counter(lis)
ans = []
for i in range(N):
    road = uf_road.find(i)
    rail = uf_rail.find(i)
    ans.append(str(c[(road*(10**6)+rail)]))
print(' '.join(ans))

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

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

N, K, L = mapint()
uf_road = UnionFind(N)
for _ in range(K):
    x, y = mapint()
    uf_road.union(x-1, y-1)

uf_rail = UnionFind(N)
for _ in range(L):
    x, y = mapint()
    uf_rail.union(x-1, y-1)
from collections import Counter
lis = []
for i in range(N):
    road = uf_road.find(i)
    rail = uf_rail.find(i)
    lis.append((road, rail))
c = Counter(lis)

ans = []
for i in range(N):
    road = uf_road.find(i)
    rail = uf_rail.find(i)
    ans.append(str(c[(road, rail)]))
print(' '.join(ans))

Submission status: Accepted

Solution code:
class UnionFind:
  def __init__(self, N):
    self.par=[i for i in range(N)]
    self.rank=[0 for _ in range(N)]
    self.size=[1 for _ in range(N)]
    
  def unite(self, x, y):
    x=self.getroot(x)
    y=self.getroot(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 united(self, x, y):
    return self.getroot(x)==self.getroot(y)
      
  def getroot(self, x):
    if self.par[x]==x:
      return x
    else:
      self.par[x]=self.getroot(self.par[x])
      return self.par[x]

  def getsize(self, x):
    return self.size[self.getroot(x)]
  
from collections import defaultdict

N, K, L=map(int, input().split())
UF1=UnionFind(N+1)
UF2=UnionFind(N+1)
for _ in range(K):
  p, q=map(int, input().split())
  UF1.unite(p, q)
  
for _ in range(L):
  r, s=map(int, input().split())
  UF2.unite(r, s)
  
nums=defaultdict(int)
for i in range(1, N+1):
  nums[str(UF1.getroot(i))+'_'+str(UF2.getroot(i))]+=1
  
for i in range(1, N+1):
  print(nums[str(UF1.getroot(i))+'_'+str(UF2.getroot(i))])

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k,l = list(map(int, input().split()))
from collections import defaultdict
ns0 = defaultdict(list)
ns1 = defaultdict(list)
for i in range(k):
    p,q = map(int, input().split())
    p-=1;q-=1
    ns0[p].append(q)
    ns0[q].append(p)
for i in range(l):
    p,q = map(int, input().split())
    p-=1;q-=1
    ns1[p].append(q)
    ns1[q].append(p)
def sub(ns):
    seen = [None]*n
    num = 1
    for i in range(n):
        if seen[i] is not None:
            continue
        q = [i]
        seen[i] = num
        while q:
            u = q.pop()
            for v in ns[u]:
                if seen[v] is not None:
                    continue
                seen[v] = num
                q.append(v)
        num += 1
    return seen

s1 = sub(ns0)
s2 = sub(ns1)

import gc
del ns0, ns1
gc.collect()

from collections import Counter
c = Counter([(s1[i], s2[i]) for i in range(n)])
ans = [(c[s1[i],s2[i]]) for i in range(n)]
write(" ".join(map(str, ans)))

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k,l = list(map(int, input().split()))
from collections import defaultdict
ns0 = defaultdict(list)
ns1 = defaultdict(list)
for i in range(k):
    p,q = map(int, input().split())
    p-=1;q-=1
    ns0[p].append(q)
    ns0[q].append(p)
for i in range(l):
    p,q = map(int, input().split())
    p-=1;q-=1
    ns1[p].append(q)
    ns1[q].append(p)
def sub(ns):
    seen = [None]*n
    num = 1
    for i in range(n):
        if seen[i] is not None:
            continue
        q = [i]
        seen[i] = num
        while q:
            u = q.pop()
            for v in ns[u]:
                if seen[v] is not None:
                    continue
                seen[v] = num
                q.append(v)
        num += 1
    return seen

s1 = sub(ns0)
s2 = sub(ns1)

import gc
del ns0, ns1
gc.collect()

d1 = [None]*(max(s1)+1)
d2 = [None]*(max(s2)+1)
def update(d,ind,i):
    if d[ind] is None:
        d[ind] = set([i])
    else:
        d[ind].add(i)
for i in range(n):
    update(d1,s1[i],i)
    update(d2,s2[i],i)
#     d1[s1[i]].add(i)
#     d2[s2[i]].add(i)
d = {}
ans = [None]*n
for i in range(n):
    u,v = s1.pop(), s2.pop()
    if (u,v) not in d:
        d[u,v] = len(d1[u] & d2[v])
    ans[-(i+1)] = d[u,v]
write(" ".join(map(str, ans)))

Submission status: Accepted

Solution code:
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())
pq = [list(map(int, input().split())) for i in range(k)]
rs = [list(map(int, input().split())) for i in range(l)]

uf_pq = UnionFind(n)
uf_rs = UnionFind(n)

for p in pq:
  x, y = p
  uf_pq.unite(x-1, y-1)
  
for r in rs:
  x, y = r
  uf_rs.unite(x-1, y-1)
  
pairs = []
for i in range(n):
  pairs.append((uf_pq.find(i), uf_rs.find(i)))
  
count = Counter(pairs)

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

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import Counter, deque, defaultdict

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

    edge1 = defaultdict(list)

    for _ in range(k):
        p, q = map(int, readline().split())
        edge1[p - 1].append(q - 1)
        edge1[q - 1].append(p - 1)

    a = [-1] * n
    que = deque()

    for i in range(n):
        if a[i] == -1:
            que.append(i)
            a[i] = i
            while que:
                cur = que.popleft()
                for nx in edge1[cur]:
                    if a[nx] == -1:
                        a[nx] = i
                        que.append(nx)

    edge2 = defaultdict(list)

    for _ in range(l):
        r, s = map(int, readline().split())
        edge2[r - 1].append(s - 1)
        edge2[s - 1].append(r - 1)

    b = [-1] * n
    que = deque()

    for i in range(n):
        if b[i] == -1:
            que.append(i)
            b[i] = i
            while que:
                cur = que.popleft()
                for nx in edge2[cur]:
                    if b[nx] == -1:
                        b[nx] = i
                        que.append(nx)

    c = Counter()
    for i in range(n):
        c[(a[i], b[i])] += 1

    res = [0] * n
    for i in range(n):
        res[i] = c[(a[i], b[i])]

    print(*res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]
        self.rank = [0 for i in range(n)]

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

    def unite(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if (root_x == root_y):
            return
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x

        elif self.rank[root_y] > self.rank[root_x]:
            self.parent[root_x] = root_y

        else:
            self.parent[root_x] = root_y
            self.rank[root_y] += 1

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

    def memsInGroup(self, x):
        """
        O(N)かかります
        """
        root = self.find(x)
        return [i for i in range(N) if root == self.find(i)]

    def sizeOfGroup(self, x):
        return len(self.memsInGroup(x))

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

road = UnionFind(N)
train = UnionFind(N)

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

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

pair = [(road.find(i), train.find(i)) for i in range(N)]
# print(pair)
c = Counter(pair)
# print(c)
ans = [c[i] for i in pair]
# print(ans)
print(*ans)

Submission status: Accepted

Solution code:
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(self, x):
    if(self.root[x] < 0):
      return x
    else:
      self.root[x] = self.find(self.root[x])
      return self.root[x]
  def unite(self, x, y):
    x = self.find(x)
    y = self.find(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 same(self, x, y):
    return self.find(x) == self.find(y)
n,k,l=map(int,input().split())
e=[[i]for i in range(n+1)]
ur=UnionFind(n)
ut=UnionFind(n)
for i in range(k):
  a,b=map(int,input().split())
  ur.unite(a,b)
for _ in range(l):
  a,b=map(int,input().split())
  ut.unite(a,b)
pair=[(ur.find(i),ut.find(i)) for i in range(1,n+1)]
c=Counter(pair)
ans=[c[i] for i in pair]
print(*ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter


class UnionFindTree:
    def __init__(self, n: int) -> None:
        self.par = list(range(n))
        self.rank = [0] * n

    def find(self, x: int) -> int:
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x: int, y: int) -> None:
        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: int, y: int) -> bool:
        return self.find(x) == self.find(y)


def resolve(in_, out):
    N, K, L = map(int, next(in_).split())

    k = UnionFindTree(N + 1)
    l = UnionFindTree(N + 1)
    for _ in range(K):
        p, q = map(int, next(in_).split())
        k.unite(p, q)
    for _ in range(L):
        p, q = map(int, next(in_).split())
        l.unite(p, q)
   
    d = Counter((k.find(i), l.find(i)) for i in range(1, N + 1))

    ans = ' '.join(str(d[(k.find(i), l.find(i))]) for i in range(1, N + 1))
    print(ans)


def main():
    resolve(sys.stdin.buffer, sys.stdout)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
n, k, l = map(int, input().split())
def find(x, par):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x], par)
        return par[x]
def unite(x, y, par):
    p = find(x, par)
    q = find(y, par)
    if p == q:
        return None
    if p > q:
        p, q = q, p
    par[p] += par[q]
    par[q] = p
def same(x, y):
    return find(x) == find(y)
def size(x):
    return -par[find(x)]
road_par = [-1 for i in range(n + 1)]
train_par = [-1 for i in range(n + 1)]
for i in range(k):
    p, q = map(int, input().split())
    unite(p, q, road_par)
for i in range(l):
    r, s = map(int, input().split())
    unite(r, s, train_par)
ans = []
for i in range(n):
    ans.append((find(i + 1, road_par), find(i + 1, train_par)))
c = Counter(ans)
for i in ans:
    print(c[i], end=" ")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys 
from collections import defaultdict
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

#Union Find

#xの根を求める
def find(x,par):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x],par)
        return par[x]
#xとyの属する集合の併合
def union(x,y,par):
    x = find(x,par)
    y = find(y,par)
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y] #xにyの個数くっつける 
        par[y] = x #yをxにくっつける
        return True

#xとyが同じ集合に属するかの判定
def same(x,y,par):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

N,K,L = map(int,readline().split())
par_road = [-1]*(N+1)
par_rail = [-1]*(N+1)


for i in range(K):
    x,y = map(int,readline().split())
    union(x,y,par_road)
    
for i in range(L):
    x,y = map(int,readline().split())
    union(x,y,par_rail)
    
num = []
d = defaultdict(int)  
for i in range(1,N+1):
    id = find(i,par_road)+find(i,par_rail)*10**6
    num.append(id)
    d[id] += 1

print(' '.join(str(d[n]) for n in num))

Submission status: Accepted

Solution code:
from collections import Counter
class UnionFind:
    def __init__(self,N):
        self.par=[i for i in range(N)]
        self.siz=[1 for _ in range(N)]
        self.rank=[0 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,a,b):
        a=self.find(a)
        b=self.find(b)
        if a==b:
            return 0
        else:
            if self.rank[a]>self.rank[b]:
                self.par[b]=a
                self.siz[a]+=self.siz[b]
            else:
                self.par[a]=b
                self.siz[b]+=self.siz[a]
                if self.rank[a]==self.rank[b]:
                    self.rank[b]+=1
    def size(self,a):
        return self.siz[self.find(a)]
    def same(self,a,b):
        return self.find(a)==self.find(b)

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

for i in range(K):
    p,q=map(lambda x:int(x)-1,input().split())
    road.union(p,q)
for i in range(L):
    r,s=map(lambda x:int(x)-1,input().split())
    train.union(r,s)
li=[(road.find(i),train.find(i)) for i in range(N)]
c=Counter(li)
ans=[c[li[i]] for i in range(N)]
print(*ans)

Submission status: Accepted

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy


class UnionFind:

    def __init__(self, n: int):
        self._n = n
        self._parents = [i for i in range(n)]
        self._size = [1 for _ in range(n)]

    def unite(self, x: int, y: int) -> None:
        px = self.find(x)
        py = self.find(y)

        # 一致していないときはリンクをつける
        if px != py:
            self._link(px, py)

    def _link(self, x: int, y: int):
        if self._size[x] < self._size[y]:
            self._parents[x] = y
            self._size[y] += self._size[x]
        else:
            self._parents[y] = x
            self._size[x] += self._size[y]

    def same(self, x: int, y: int) -> bool:
        px = self.find(x)
        py = self.find(y)
        return px == py

    def find(self, x: int) -> int:
        if self._parents[x] == x:
            return x

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

    def size(self, x: int):
        return self._size[self.find(self._parents[x])]

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

road = UnionFind(N + 1)
rail = UnionFind(N + 1)
share = UnionFind(N + 1)

roads = [list(map(int, input().split())) for _ in range(K)]
rails = [list(map(int, input().split())) for _ in range(L)]

for i in range(K):
    p, q = roads[i]
    road.unite(p, q)

for i in range(L):
    r, s = rails[i]
    rail.unite(r, s)

m = {}

for i in range(1, N + 1):
    cnt = m.get((road.find(i), rail.find(i)), 0)
    m[(road.find(i), rail.find(i))] = cnt + 1

ans = [0] * N
for i in range(N):
    ans[i] = m[(road.find(i + 1), rail.find(i + 1))]

print(*ans)

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy

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

road = [[] for i in range(n+1)]
rail = [[] for i in range(n+1)]

for i in range(k):
    p, q = list(map(int, input().split()))
    road[p].append(q)
    road[q].append(p)

for i in range(l):
    r, s = list(map(int, input().split()))
    rail[r].append(s)
    rail[s].append(r)

seen = [0 for i in range(n+1)]

def dfs_stack(u, al, al_c, d):
    stack = deque([u])
    seen[u] = 1

    while len(stack) > 0:
        v = stack.pop()
        ###
        al_c[v] = d
        ###

        for w in al[v]:
            if seen[w] == 0:
                stack.append(w)
                seen[w] = 1

        if stack == []: break


road_c = [-1 for i in range(n+1)]
rail_c = [-1 for i in range(n+1)]

d = 0
for i in range(1,n+1):
    if seen[i] == 0:
        dfs_stack(i, road, road_c, d)
        d += 1

seen = [0 for i in range(n+1)]

d = 0
for i in range(1,n+1):
    if seen[i] == 0:
        dfs_stack(i, rail, rail_c, d)
        d += 1

dict = {}

for i in range(1, n+1):
    if (road_c[i], rail_c[i]) not in dict:
        dict[(road_c[i], rail_c[i])] = [i]
    else:
        dict[(road_c[i], rail_c[i])].append(i)

ans = [0 for i in range(n+1)]

for dd in dict.items():
    for j in dd[1]:
        ans[j] = str(len(dd[1]))

print(' '.join(ans[1:]))

Submission status: Accepted

Solution code:
import collections

NO_OF_DIMENSIONS = 2
no_of_edges_by_dim = [None] * NO_OF_DIMENSIONS
n, no_of_edges_by_dim[0], no_of_edges_by_dim[1] = (int(x) for x in input().split())

graph_by_dimension = [[[] for _ in range(n + 1)] for _ in range(NO_OF_DIMENSIONS)]

for dimension, no_of_edges in enumerate(no_of_edges_by_dim):
    graph = graph_by_dimension[dimension]
    for _ in range(no_of_edges):
        p, q = (int(x) for x in input().split())
        graph[p].append(q)
        graph[q].append(p)

components_ids_by_vertex = [[None] * NO_OF_DIMENSIONS for _ in range(n + 1)]

def dfs(dimension_id, vertex_id, colour):
    stack = [vertex_id]
    while len(stack):
        vertex_id = stack.pop()
        components_ids_by_vertex[vertex_id][dimension_id] = colour
        for s in graph_by_dimension[dimension_id][vertex_id]:
            if not components_ids_by_vertex[s][dimension_id]:
                stack.append(s)

for i in range(NO_OF_DIMENSIONS):
    for j in range(1, n + 1):
        if not components_ids_by_vertex[j][i]:
            dfs(i, j, j)

components_ids_by_vertex = [tuple(x) for x in components_ids_by_vertex]

results = collections.Counter(components_ids_by_vertex)

for i in range(1, n + 1):
    print(results[components_ids_by_vertex[i]], end=' ')
print()