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:
class UnionFind:
    def __init__(self, n: int):
        self.__n = n
        self.__par = list(range(self.__n))
        self.__size = [1 for _ in range(self.__n)]

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

    def merge(self, x: int, y: int) -> bool:
        rx, ry = self.root(x), self.root(y)
        if rx == ry: return False

        if self.__size[rx] < self.__size[ry]:
            rx, ry = ry, rx

        self.__size[rx] += self.__size[ry]
        self.__par[ry] = rx
        return True

    def check(self, x: int, y: int) -> bool:
        return self.root(x) == self.root(y)

    def size(self, x: int) -> int:
        return self.__size[self.root(x)]


from collections import defaultdict

N, K, L = map(int, input().split())
rail_uf = UnionFind(N + 1)
road_uf = UnionFind(N + 1)

for _ in range(K):
    p, q = map(int, input().split())
    rail_uf.merge(p, q)

for _ in range(L):
    r, s = map(int, input().split())
    road_uf.merge(r, s)

d = defaultdict(int)
for i in range(1, N + 1):
    tup = (rail_uf.root(i), road_uf.root(i))
    d[tup] += 1

ans = []
for i in range(1, N + 1):
    tup = (rail_uf.root(i), road_uf.root(i))
    ans.append(str(d[tup]))

print(" ".join(ans))

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
def input(): return sys.stdin.readline().rstrip()

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

    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 same(self, x, y):
        return self.find(x) == self.find(y)
    
    def size(self, x):
        return -self.parents[self.find(x)]

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

    for _ in range(K):
        p, q = map(int, input().split())
        road.union(p, q)
    
    for _ in range(L):
        r, s = map(int, input().split())
        train.union(r, s)
    
    ans = []
    counter = defaultdict(int)
    for i in range(1, N + 1):
        root = (road.find(i), train.find(i))
        ans.append(root)
        counter[root] += 1
    for i in range(1, N + 1):
        root = (road.find(i), train.find(i))
        print(counter[root])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#union-findの勉強
import sys
def find(x,par):
  #根そのものならそれを出力、そうじゃなければ上を探す
  if par[x]==x:
    return x
  else:
    return find(par[x],par)

def union(x,y,par,rank):
  x=find(x,par)
  y=find(y,par)

  if x!=y:
    #rankは属する根の番号
    if rank[x]<rank[y]:
      par[x]=y
    else:
      par[y]=x
      if rank[x]==rank[y]:
        rank[x]+=1

def same(x,y,par):
  return find(x,par)==find(y,par)

n,k,l=map(int, input().split())    
apar=[]
bpar=[]
arank=[0]*n
brank=[0]*n

for i in range(n):
  apar.append(i)
  bpar.append(i)

for i in range(k):
  p,q = map(int, input().split())
  union(p-1,q-1,apar,arank)

for i in range(l):
  p,q = map(int, input().split())
  union(p-1,q-1,bpar,brank)

#apar,bparは、次元の数
  
num=[]
d={}
for i in range(n):
  #Nが10**5オーダーなので、とりあえず10**6離してラベリング
  num.append(find(i,apar)+find(i,bpar)*10**6)
  #辞書になければ項目＋、あったら数を増やす
  if num[-1] in d:
    d[num[-1]]+=1
  else:
    d[num[-1]]=1
        
res=''
for i in range(n):
  #最初だけ空白は入れない
  if i!=0:
    res+=' '
  #Nの順番に、鉄道・道路の2つの分野で次元が両方同じだったら手段が2通りになる
  res+=str(d[num[i]])
print(res)

Submission status: Accepted

Solution code:
import sys

#UnionFine　ネットの解答

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

def union(x,y,par,rank):
    x = find(x,par)
    y = find(y,par)

    if x != y:
        #xとyの属している集合が異なる場合
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

def same(x,y,par):
    return find(x,par) == find(y,par)

input = sys.stdin.readline
n, k, l = map(int, input().split())    
apar = []
bpar = []
arank = [0]*n
brank = [0]*n

for i in range(n):
    apar.append(i)
    bpar.append(i)


for i in range(k):
    p,q = map(int, input().split())
    union(p-1,q-1,apar,arank)

for i in range(l):
    p,q = map(int, input().split())
    union(p-1,q-1,bpar,brank)

num = []
d = {}
for i in range(n):
    num.append(find(i,apar)+find(i,bpar)*10**6)
    if num[-1] in d:
        d[num[-1]] += 1
    else:
        d[num[-1]] = 1

res = ''
for i in range(n):
    if i != 0:
        res += ' '

    res += str(d[num[i]])

print(res)

Submission status: Accepted

Solution code:
n,k,l=map(int,input().split())
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]
uf1=UnionFind(n)
uf2=UnionFind(n)
d=dict()
a,b=[0]*n,[0]*n
for i in range(k):
  p,q=map(int,input().split())
  uf1.union(p-1,q-1)
ans=[0]*n
for i in range(l):
  r,s=map(int,input().split())
  uf2.union(r-1,s-1)
for i in range(n):
  a[i]=uf1.find(i)
  b[i]=uf2.find(i)
  if (a[i],b[i]) not in d:
    d[(a[i],b[i])]=1
  else:
    d[(a[i],b[i])]+=1
for i in range(n):
  ans[i]=d[(a[i],b[i])]
print(*ans)

Submission status: Accepted

Solution code:
class UnionFind(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.size = [1]*size

    def find(self, x):
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.size[x] < self.size[y]:
            self.size[y] += self.size[x]
            self.parent[x] = y
        else:
            self.size[x] += self.size[y]
            self.parent[y] = x
    
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def sizeofset(self, x):
        return self.size[self.find(x)]

if __name__ == "__main__":
    N,K,L = map(int,input().split())
    uf_road = UnionFind(N)
    uf_rail = UnionFind(N)
    for _ in range(K):
        p,q = map(int,input().split())
        p -= 1
        q -= 1
        uf_road.unite(p,q)
    for _ in range(L):
        r,s = map(int,input().split())
        r -= 1
        s -= 1
        uf_rail.unite(r,s)
    roots = [None]*N
    for i in range(N):
        roots[i] = (uf_road.find(i), uf_rail.find(i))
    from collections import defaultdict
    d = defaultdict(int)
    for r in roots:
        d[r] += 1
    print(" ".join([str(d[roots[i]]) for i in range(N)]))

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from functools import *
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def Golf():
    *a,=map(int,open(0))
def S_():
    return input()
def IS():
    return input().split()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2)
    found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['YES','NO']

mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

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
    
    def __str__(self):
        rt=[i if j<0 else j for i,j in enumerate(self.table)]
        return str(rt)


show_flg=False
show_flg=True

ans=0

n,k,l=LI()

ufr=UnionFind(n)
ufh=UnionFind(n)

for i in range(k):
    a,b=LI_()
    ufh.union(a,b)

for i in range(l):
    a,b=LI_()
    ufr.union(a,b)

con=[0]*n
cnt=defaultdict(int)
for i in range(n):
    con[i]=ufr._root(i)*10**5+ufh._root(i)
    cnt[con[i]]+=1
for i in range(n):
    print(cnt[con[i]])

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline
n,k,l = map(int,input().split())
road = [list(map(int,input().split())) for i in range(k)]
train = [list(map(int,input().split())) for i in range(l)]
rg = [[] for i in range(n+1)]
rv = [0 for i in range(n+1)]
tg = [[] for i in range(n+1)]
tv = [0 for i in range(n+1)]
def connect(road,rg,rv):
  for a,b in road:
    rg[a].append(b)
    rg[b].append(a)
  cnt = 0
  for i in range(1,n+1):
    if rv[i] == 0:
      cnt += 1
      stack = [i]
      while stack:
        x = stack.pop()
        rv[x] = cnt
        for y in rg[x]:
          if rv[y] == 0:
            stack.append(y)
            rv[y] = cnt
connect(road,rg,rv)
connect(train,tg,tv)
condc = defaultdict(list)
for i in range(1,n+1):
  cr = rv[i]
  ct = tv[i]
  condc[(cr,ct)].append(i)
ans = []
for i in range(1,n+1):
  cr = rv[i]
  ct = tv[i]
  ans.append(len(condc[(cr,ct)]))
print(*ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n,k,l = map(int,input().split())
road = [list(map(int,input().split())) for i in range(k)]
train = [list(map(int,input().split())) for i in range(l)]
rg = [[] for i in range(n+1)]
rv = [0 for i in range(n+1)]
tg = [[] for i in range(n+1)]
tv = [0 for i in range(n+1)]
def connect(road,rg,rv,):
  for a,b in road:
    rg[a].append(b)
    rg[b].append(a)
  cnt = 0
  for i in range(1,n+1):
    if rv[i] == 0:
      cnt += 1
      stack = [i]
      while stack:
        x = stack.pop()
        rv[x] = cnt
        for y in rg[x]:
          if rv[y] == 0:
            stack.append(y)
            rv[y] = cnt
connect(road,rg,rv)
connect(train,tg,tv)
condc = defaultdict(list)
for i in range(1,n+1):
  cr = rv[i]
  ct = tv[i]
  condc[(cr,ct)].append(i)
ans = []
for i in range(1,n+1):
  cr = rv[i]
  ct = tv[i]
  ans.append(len(condc[(cr,ct)]))
print(*ans)

Submission status: Accepted

Solution code:
from collections import Counter
n,k,l=map(int,input().split())
#union-find
par1=[-1]*(n+1)
par2=[-1]*(n+1)

def find1(x):
    if par1[x]<0:
        return x
    else:
        par1[x]=find1(par1[x])
        return par1[x]
def find2(x):
    if par2[x]<0:
        return x
    else:
        par2[x]=find2(par2[x])
        return par2[x]
def size1(x):
    return -par1[find1(x)]
def size2(x):
    return -par2[find2(x)]
def unite1(x,y):
    if find1(x)==find1(y):
        return False
    else:
        if size1(x)<size1(y):
            x,y=y,x
        X=find1(x)
        Y=find1(y)
        par1[X]-=size1(Y)
        par1[Y]=X
        return True
def unite2(x,y):
    if find2(x)==find2(y):
        return False
    else:
        if size2(x)<size2(y):
            x,y=y,x
        X=find2(x)
        Y=find2(y)
        par2[X]-=size2(Y)
        par2[Y]=X
        return True
def is_same1(x,y):
    return find1(x)==find1(y)
def is_same2(x,y):
    return find2(x)==find2(y)

for _ in range(k):
    p,q=map(int,input().split())
    unite1(p,q)
for _ in range(l):
    r,s=map(int,input().split())
    unite2(r,s)
L=[]
for i in range(1,n+1):
    L.append((find1(i),find2(i)))
kazu=Counter(L)
ans=[0]*(n)
for i in range(n):
    ans[i]=kazu[L[i]]
print(*ans, sep=' ')

Submission status: Accepted

Solution code:
N, K, L = [int(x) for x in input().split()]
K_lst = [[int(x) for x in input().split()] for i in range(K)]
L_lst = [[int(x) for x in input().split()] for i in range(L)]

ar = [int(i) for i in range(N + 1)]
br = [int(i) for i in range(N + 1)]

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

def union(x, y, array):
    x = find(x, array)
    y = find(y, array)

    if x == y:
        return
    if x > y:
        x, y = y, x
    array[y] = x

for i in K_lst:
    u, v = i
    union(u, v, ar)
for i in L_lst:
    u, v = i
    union(u, v, br)
for i in range(1, N + 1):
    find(i, ar)
    find(i, br)
dict = {}
for i in range(1, N + 1):
    a = ar[i]
    b = br[i]
    if not (a, b) in dict.keys():
        dict[(a, b)] = 1
    else:
        dict[(a, b)] += 1
a_lst = [0] * N
for i in range(N):
    a = ar[i + 1]
    b = br[i + 1]
    a_lst[i] = dict[(a, b)]
print(*a_lst)

Submission status: Accepted

Solution code:
from collections import*

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

    def find(self, x):
        if self.parents[x] < 0:
            return x
        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

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

road = UnionFind(N)
rail = UnionFind(N)

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

d = defaultdict(int)

for i in range(N):
    d[(road.find(i), rail.find(i))] += 1
print(*[d[(road.find(i), rail.find(i))] for i in range(N)])

Submission status: Accepted

Solution code:
#Union-Find木の構築
import sys
def 解():
    iN,iK,iL = [int(_) for _ in input().split()]
    aD = [[int(_) for _ in sLine.split()] for sLine in sys.stdin.readlines()]

    def buildTree(a):
        #aT = [0]*(iN+1)
        aT = list(range(iN+1))
        for p,q in a:
            rp = getRoot(aT,p)
            rq = getRoot(aT,q)
            thisRoot = max(rp,rq,q) #みんな小さい方に合わせてるのでデカい方に合>わせてみる
            aT[p] = thisRoot
            aT[q] = thisRoot
            aT[rp] = thisRoot #これで Union してるつもり
            aT[rq] = thisRoot
        return aT
    def getRoot(a,i): #find
        #if a[i] == i or a[i] == 0:
        #   if a[i] == 0 : a[i] = i
        if a[i] == i :
            return i
    #   elif i < a[i] :
        else :
            a[i] = getRoot(a,a[i])
            return a[i]
    #   else:
    #       print("! ",i,a[i])

    aT道 = buildTree(aD[0:iK])
    aT鉄道 = buildTree(aD[iK:])
    aRet = []
    dRet = {}
    for i in range(1,iN+1):
        # いやはやこんなもんもキーになるのか。
        Comb = (getRoot(aT道,i), getRoot(aT鉄道,i))
        aRet.append(Comb)
        if Comb in dRet:
            dRet[Comb] += 1
        else:
            dRet[Comb] = 1
    print(" ".join([str(dRet[_]) for _ in aRet]))

解()

Submission status: Accepted

Solution code:
from collections import deque

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

graphs = [[[] for _ in range(n)], [[] for _ in range(n)]]
cands = [set(), set()]
for _ in range(k):
    x, y = map(int, input().split())
    graphs[0][x - 1].append(y - 1)
    graphs[0][y - 1].append(x - 1)
    cands[0].add(x - 1)
for _ in range(l):
    x, y = map(int, input().split())
    graphs[1][x - 1].append(y - 1)
    graphs[1][y - 1].append(x - 1)
    cands[1].add(x - 1)

groups = [[], []]
groups_inv = [[-1] * n, [-1] * n]
def dfs(start, case, num):
    q = deque()
    q.append(start)
    used = {start}
    groups[case].append(used)
    groups_inv[case][start] = num
    while q:
        node = q.popleft()
        for to in graphs[case][node]:
            if to in used:
                continue
            q.append(to)
            used.add(to)
            groups_inv[case][to] = num

for i in range(2):
    count = 0
    for node in cands[i]:
        if groups_inv[i][node] == -1:
            dfs(node, i, count)
            count += 1

ret = [-1] * n
for i in range(n):
    if groups_inv[0][i] == -1 or groups_inv[1][i] == -1:
        ret[i] = 1
    elif ret[i] == -1:
        cities = groups[0][groups_inv[0][i]] & groups[1][groups_inv[1][i]]
        for city in cities:
            ret[city] = len(cities)
print(*ret)

Submission status: Accepted

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue
#import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys

sys.setrecursionlimit(100000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)




def main(): #startline--------------------------------------------
    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)]
    un1 = UnionFind(n)
    un2 = UnionFind(n)
    for i in range(k):
        un1.union(pq[i][0]-1,pq[i][1]-1)
    for i in range(l):
        un2.union(rs[i][0]-1,rs[i][1]-1)
    d = defaultdict(int)
    anslist = []
    for i in range(n):
        d[un1.findroot(i),un2.findroot(i)] += 1
    for i in range(n):
        anslist.append(d[un1.findroot(i),un2.findroot(i)])
    print(*anslist,sep = " ")
if __name__ == "__main__":
    main() #endline===============================================

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

def unite(par, i, j):
    j = get_par(par, j)
    par[j] = get_par(par, i)

def get_par(par, p):
    while par[p] != p:
        p = par[p]
    return par[p]

n,k,l = map(int, input().split())
pq = []
road = [i for i in range(n+1)]
rail = [i for i in range(n+1)]
for i in range(k):
    p,q = map(int,input().split())
    pq.append((p,q))
    aa = get_par(road, p)
    bb = get_par(road, q)
    if aa == bb:
        continue
    # unite
    if aa < bb:
        road[bb] = aa
    else:
        road[aa] = bb

rs = []
for i in range(l):
    p,q = map(int,input().split())
    rs.append((p,q))
    aa = get_par(rail, p)
    bb = get_par(rail, q)
    if aa == bb:
        continue
    # unite
    if aa < bb:
        rail[bb] = aa
    else:
        rail[aa] = bb

ans = [(road[get_par(road, i)], rail[get_par(rail, i)]) for i in range(1,n+1)]
from collections import Counter
c = Counter(ans)
print(*[c[(road[get_par(road, i)], rail[get_par(rail, i)])] for i in range(1,n+1)])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)


def unite(par, i, j):
    j = get_par(par, j)
    par[j] = get_par(par, i)

def get_par(par, p):
    while par[p] != p:
        p = par[p]
    return par[p]

n,k,l = map(int, input().split())
pq = []
road = [i for i in range(n+1)]
rcnt = [set([i]) for i in range(n+1)]
rail = [i for i in range(n+1)]
acnt = [set([i]) for i in range(n+1)]
for i in range(k):
    p,q = map(int,input().split())
    pq.append((p,q))
    aa = get_par(road, p)
    bb = get_par(road, q)
    if aa == bb:
        continue
    # unite
    if aa < bb:
        road[bb] = aa
        rcnt[aa] |= rcnt[bb]
    else:
        road[aa] = bb
        rcnt[bb] |= rcnt[aa]

rs = []
for i in range(l):
    p,q = map(int,input().split())
    rs.append((p,q))
    aa = get_par(rail, p)
    bb = get_par(rail, q)
    if aa == bb:
        continue
    # unite
    if aa < bb:
        rail[bb] = aa
        acnt[aa] |= acnt[bb]
        # acnt[aa] += acnt[bb]
    else:
        rail[aa] = bb
        acnt[bb] |= acnt[aa]

ans = [(road[get_par(road, i)], rail[get_par(rail, i)]) for i in range(1,n+1)]
from collections import Counter
c = Counter(ans)
print(*[c[(road[get_par(road, i)], rail[get_par(rail, i)])] for i in range(1,n+1)])
# print(acnt)
# print(rcnt)

Submission status: Accepted

Solution code:
from collections import*
import sys


class UnionFind(object):
    def __init__(self, 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
        return


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

ro_cl = UnionFind(n)
ra_cl = UnionFind(n)
d = defaultdict(int)

# =================================================================

# なぜかスライスを使うとエラーになる。原因不明。
# w = [list(map(int, input().split())) for i in range(k+l)]
# ro = w[:k]
# ra = w[l:]
# for p, q in ro:
#     ro_cl.union(p-1, q-1)
# for p, q in ra:
#     ra_cl.union(p-1, q-1)

# =================================================================

for i in range(k):
    p, q = map(int, input().split())
    ro_cl.union(p-1, q-1)
for i in range(l):
    p, q = map(int, input().split())
    ra_cl.union(p-1, q-1)

# =================================================================

for i in range(n):
    d[(ro_cl.find(i), ra_cl.find(i))] += 1
print(*[d[(ro_cl.find(i), ra_cl.find(i))]for i in range(n)])

Submission status: Accepted

Solution code:
from collections import*
import sys
input = sys.stdin.readline


class UnionFind(object):
    def __init__(self, n):
        # 親の番号を格納する。親だった場合は-(その集合のサイズ)
        # 作るときはParentsの値を全て-1にする
        # こうすると全てバラバラになる
        self.parents = [-1 for i in range(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
        return


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

ro_cl = UnionFind(n)
ra_cl = UnionFind(n)
d = defaultdict(int)

# =================================================================

# w = [list(map(int, input().split())) for i in range(k+l)]
# ro = w[:k]
# ra = w[l:]
# for p, q in ro:
#     ro_cl.union(p-1, q-1)
# for p, q in ra:
#     ra_cl.union(p-1, q-1)

# =================================================================

for i in range(k):
    p, q = map(int, input().split())
    ro_cl.union(p-1, q-1)
for i in range(l):
    p, q = map(int, input().split())
    ra_cl.union(p-1, q-1)

# =================================================================

for i in range(n):
    d[(ro_cl.find(i), ra_cl.find(i))] += 1
print(*[d[(ro_cl.find(i), ra_cl.find(i))]for i in range(n)])

Submission status: Accepted

Solution code:
from collections import*
import sys
input = sys.stdin.readline


class UnionFind(object):
    def __init__(self, n):
        # 親の番号を格納する。親だった場合は-(その集合のサイズ)
        # 作るときはParentsの値を全て-1にする
        # こうすると全てバラバラになる
        self.parents = [-1 for i in range(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
        return

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

ro_cl = UnionFind(n)
ra_cl = UnionFind(n)
d = defaultdict(int)

# =================================================================

# w = [list(map(int, input().split())) for i in range(k+l)]
# ro = w[:k]
# ra = w[l:]
# for p, q in ro:
#     ro_cl.union(p-1, q-1)
# for p, q in ra:
#     ra_cl.union(p-1, q-1)

# =================================================================

for i in range(k):
    p, q = map(int, input().split())
    ro_cl.union(p-1, q-1)
for i in range(l):
    p, q = map(int, input().split())
    ra_cl.union(p-1, q-1)

# =================================================================

for i in range(n):
    d[(ro_cl.find(i), ra_cl.find(i))] += 1
print(*[d[(ro_cl.find(i), ra_cl.find(i))]for i in range(n)])

Submission status: Accepted

Solution code:
from collections import*
import sys
input = sys.stdin.readline


class UnionFind(object):
    def __init__(self, n):
        # 親の番号を格納する。親だった場合は-(その集合のサイズ)
        # 作るときはParentsの値を全て-1にする
        # こうすると全てバラバラになる
        self.parents = [-1 for i in range(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
        return


# n, k, l = map(int, input().split())
# w = [list(map(int, input().split())) for i in range(k+l)]
# ro = w[:k]
# ra = w[l:]

# ro_cl = UnionFind(n)
# ra_cl = UnionFind(n)
# d = defaultdict(int)

# for p, q in ro:
#     ro_cl.union(p-1, q-1)
# for p, q in ra:
#     ra_cl.union(p-1, q-1)

# for i in range(n):
#     d[(ro_cl.find(i), ra_cl.find(i))] += 1
# print(*[d[(ro_cl.find(i), ra_cl.find(i))]for i in range(n)])

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