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: Wrong Answer

Solution code:
#unionfind
class UF:
    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 show(self):
        print(self.table)
    def data(self):
        res={}
        n=len(self.table)
        for i in range(n):
            res.update({i:[i] if self.table[i]<0 else [self.table[i]]})
        for i in range(n):
            res[res[i][0]]+=[i]
        for i in range(n):
            if len(res[i])==1:
                del res[i]
            else:
                del res[i][0]
        return list(res.values())

n,k,l=map(int,input().split())
pq=[list(map(int,input().split())) for _ in range(k)]
rs=[list(map(int,input().split())) for _ in range(l)]
auf=UF(n)
buf=UF(n)
for p,q in pq:
    auf.union(p-1,q-1)
for r,s in rs:
    buf.union(r-1,s-1)
ta=auf.data()
tb=buf.data()
ar=[0 for i in range(n)]
br=[0 for i in range(n)]
for i in range(len(ta)):
    for t in ta[i]:
        ar[t]=i
for i in range(len(tb)):
    for t in tb[i]:
        br[t]=i
print(1)

Submission status: Wrong Answer

Solution code:
#unionfind
class UF:
    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 show(self):
        print(self.table)
    def data(self):
        res={}
        n=len(self.table)
        for i in range(n):
            res.update({i:[i] if self.table[i]<0 else [self.table[i]]})
        for i in range(n):
            res[res[i][0]]+=[i]
        for i in range(n):
            if len(res[i])==1:
                del res[i]
            else:
                del res[i][0]
        return list(res.values())

n,k,l=map(int,input().split())
pq=[list(map(int,input().split())) for _ in range(k)]
rs=[list(map(int,input().split())) for _ in range(l)]
auf=UF(n)
buf=UF(n)
for p,q in pq:
    auf.union(p-1,q-1)
for r,s in rs:
    buf.union(r-1,s-1)
ta=auf.data()
tb=buf.data()
ar=[0 for i in range(n)]
br=[0 for i in range(n)]
for i in range(len(ta)):
    for t in ta[i]:
        ar[t]=i
for i in range(len(tb)):
    for t in tb[i]:
        br[t]=i
x=[[ar[i],br[i]] for i in range(n)]
res={}
for i in range(n):
    res[str(x[i])]=0
for i in range(n):
    res[str(x[i])]+=1
print(1)

Submission status: Wrong Answer

Solution code:
NKL = [int(_) for _ in input().split()]
pq = [[int(_) - 1 for _ in input().split()] for _ in range(NKL[1])]
rs = [[int(_) - 1 for _ in input().split()] for _ in range(NKL[2])]
 
road = [0] * NKL[0]
road_num = 0
train = [0] * NKL[0]
train_num = 0
for y in pq:
    if road[y[0]] == 0 and road[y[1]] == 0:
        road_num += 1
        road[y[0]] = road_num
        road[y[1]] = road_num
    elif road[y[0]] == 0:
        road[y[0]] = road[y[1]]
    elif road[y[1]] == 0:
        road[y[1]] = road[y[0]]
    else:
        road = [y[0] if _ == y[1] else _ for _ in road]
for y in rs:
    if train[y[0]] == 0 and train[y[1]] == 0:
        train_num += 1
        train[y[0]] = train_num
        train[y[1]] = train_num
    elif train[y[0]] == 0:
        train[y[0]] = train[y[1]]
    elif train[y[1]] == 0:
        train[y[1]] = train[y[0]]
    else:
        train = [y[0] if _ == y[1] else _ for _ in train]
ans = [0] * NKL[0]
for i in range(NKL[0]):
    t = 0
    for j in range(NKL[0]):
        if i == j or (road[i] == road[j] and train[i] and train[j] and road[i] * road[j] > 0):
            t += 1
    ans[i] = t
print(' '.join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
NKL = [int(_) for _ in input().split()]
pq = [[int(_) - 1 for _ in input().split()] for _ in range(NKL[1])]
rs = [[int(_) - 1 for _ in input().split()] for _ in range(NKL[2])]

road = [0] * NKL[0]
road_num = 0
train = [0] * NKL[0]
train_num = 0
for y in pq:
    if road[y[0]] == 0 and road[y[1]] == 0:
        road_num += 1
        road[y[0]] = road_num
        road[y[1]] = road_num
    elif road[y[0]] == 0:
        road[y[0]] = road[y[1]]
    elif road[y[1]] == 0:
        road[y[1]] = road[y[0]]
    else:
        road = [y[0] if _ == y[1] else _ for _ in road]
for y in rs:
    if train[y[0]] == 0 and train[y[1]] == 0:
        train_num += 1
        train[y[0]] = train_num
        train[y[1]] = train_num
    elif train[y[0]] == 0:
        train[y[0]] = train[y[1]]
    elif train[y[1]] == 0:
        train[y[1]] = train[y[0]]
    else:
        train = [y[0] if _ == y[1] else _ for _ in train]
for i in range(NKL[0]):
    t = 0
    for j in range(NKL[0]):
        if i == j or (road[i] == road[j] and train[i] and train[j] and road[i] * road[j] > 0):
            t += 1
    print(t, end=' ')

Submission status: Wrong Answer

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)
        for p,q in a:
            #if p > q :
            #   p,q = q,p
            thisroot = max(aT[q],aT[p],q) #試しにデカい方に合わせる
            if p <= aT[q] < thisroot:  #2個づつ来るからこんなんでいいだろ
                aT[aT[q]] = thisroot
            if p <= aT[p] < thisroot:
                aT[aT[p]] = thisroot
            aT[q] = thisroot
            aT[p] = thisroot
        return aT
    def getRoot(a,i):
        if a[i] == i or a[i] == 0:
            if a[i] == 0 : a[i] = i
            return i
        elif i < a[i] :
            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: Wrong Answer

Solution code:
#! /usr/bin/python3
# 連結 / Connectivity
"""
全ての都市について、その都市と道路・鉄道の
どちらでも連結している都市の数を求めてください。

※経由を考えていなかったため中止。
"""

test_mode = True

p_q = []
r_s = []

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

connections = [1 for _ in range(N)]
# 各都市が、両方で連結している都市数。i番目の要素がi番目の都市に対応。

for _ in range(K):
    p_q.append(list(map(int, input().split())))

for _ in range(L):
    r_s.append(list(map(int, input().split())))

if test_mode:
    print('p_q :', p_q)
    print('r_s :', r_s)


def main():
    """
    p,q の組み合わせが r,s と一致したら、
    connections の対応する都市の要素に+1
    """
    for n in range(K):
        for m in range(L):
            if test_mode:
                print('n, m =', n, m)
            if p_q[n] == r_s[m]:
                if test_mode:
                    print('connected')
                connections[p_q[n-1][0]] += 1
                connections[p_q[n-1][1]] += 1

    for num in connections:
        print(num, end=' ')
    print()


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def Parent(i, A = list):
    if i == A[i]:
        return i
    else:
        return Parent(A[i], A)

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

#数字の小さい方を親ノードとする
Road = [int(_) for _ in range(N)]
Rail = [int(_) for _ in range(N)]
for i in range(K):
    p, q = map(int, input().split())
    p, q = p-1, q-1
    Road[max(Road[p],Road[q])] = Road[min(Road[p], Road[q])]
for i in range(L):
    r, s = map(int, input().split())
    r, s = r-1, s-1
    Rail[max(Rail[r],Rail[s])] = Rail[min(Rail[r],Rail[s])]

Parents, Count = [], {}
for i in range(N):
    roadP, railP = Parent(i, Road), Parent(i, Rail)
    Parents.append((roadP, railP))
    if (roadP, railP) in Count:
        Count[(roadP, railP)] += 1
    else:
        Count[(roadP, railP)] = 1

Ans = []
for i in range(N):
    Ans.append(Count[Parents[i]])
print(" ".join(map(str, Ans)))

Submission status: Wrong Answer

Solution code:
def Parent(i, A = list):
    if i == A[i]:
        return i
    else:
        return Parent(A[i], A)

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

#数字の小さい方を親ノードとする
Road = [int(_) for _ in range(N)]
Rail = [int(_) for _ in range(N)]
for i in range(K):
    p, q = map(int, input().split())
    p, q = p-1, q-1
    Road[max(p,q)] = Road[min(p, q)]
for i in range(L):
    r, s = map(int, input().split())
    r, s = r-1, s-1
    Rail[max(r, s)] = Rail[min(r,s)]

Parents, Count = [], {}
for i in range(N):
    roadP, railP = Parent(i, Road), Parent(i, Rail)
    Parents.append((roadP, railP))
    if (roadP, railP) in Count:
        Count[(roadP, railP)] += 1
    else:
        Count[(roadP, railP)] = 1

Ans = []
for i in range(N):
    Ans.append(Count[Parents[i]])
print(" ".join(map(str, Ans)))

Submission status: Wrong Answer

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

road = [set([x]) for x in range(N)]
rail = [set([x]) for x in range(N)]

for k in range(K):
	p, q = [int(x) for x in input().split()]
	road[p-1] = road[p-1] | road[q-1]
	road[q-1] = road[p-1] | road[q-1]

for l in range(L):
	r, s = [int(x) for x in input().split()]
	rail[r-1] = rail[r-1] | rail[s-1]
	rail[s-1] = rail[r-1] | rail[s-1]

print(' '.join(map(str, [len(road[n].intersection(rail[n])) for n in range(N)])))

Submission status: Wrong Answer

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

road = [set([x]) for x in range(N)]

rail = [set([x]) for x in range(N)]

for k in range(K):
	p, q = [int(x) for x in input().split()]
	road[p-1].add(p-1)
	road[p-1].add(q-1)
	road[q-1].add(q-1)
	road[q-1].add(p-1)

for l in range(L):
	r, s = [int(x) for x in input().split()]
	rail[r-1].add(r-1)
	rail[r-1].add(s-1)
	rail[s-1].add(s-1)
	rail[s-1].add(r-1)

print(' '.join(map(str, [len(road[n].intersection(rail[n])) for n in range(N)])))

Submission status: Wrong Answer

Solution code:
from collections import Counter
def find(x, A):
    p = A[x]
    if p == x:
        return x
    a = find(p, A)
    A[x] = a
    find(a,A)
    return a

N, K, L = map( int, input().split())
V = [ i for i in range(N)]
W = [ i for i in range(N)]
for _ in range(K):
    p, q = map( int, input().split())
    p, q = p-1, q-1
    bp, bq = find(p,V), find(q,V)
    V[q] = bp
    V[bq] = bp

for _ in range(L):
    r, s = map( int, input().split())
    r, s = r-1, s-1
    br, bs = find(r,W), find(s,W)
    W[s] = br
    W[bs] = br

for i in range(N):
    find(V[i], V)
    find(W[i], W)
ans = 0
VW = [ (V[i], W[i]) for i in range(N)]
CVW = Counter(VW)
ANS = [0]*N
for i in range(N):
    ANS[i] = CVW[(V[i],W[i])]

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

Submission status: Wrong Answer

Solution code:
from collections import Counter
def find(x, A):
    p = A[x]
    if p == x:
        return x
    a = find(p, A)
    A[x] = a
    return a

N, K, L = map( int, input().split())
V = [ i for i in range(N)]
W = [ i for i in range(N)]
for _ in range(K):
    p, q = map( int, input().split())
    p, q = p-1, q-1
    bp, bq = find(p,V), find(q,V)
    V[q] = bp
    V[bq] = bp

for _ in range(L):
    r, s = map( int, input().split())
    r, s = r-1, s-1
    br, bs = find(r,W), find(s,W)
    W[s] = br
    W[bs] = br

for i in range(N):
    find(V[i], V)
    find(W[i], W)
ans = 0
VW = [ (V[i], W[i]) for i in range(N)]
CVW = Counter(VW)
ANS = [0]*N
for i in range(N):
    ANS[i] = CVW[(V[i],W[i])]

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

Submission status: Wrong Answer

Solution code:
from itertools import product
from collections import defaultdict as dd

class UFT(object):
  def __init__(self,n):
    self.parent={i:i for i in range(1,n+1)}
    self.height={i:0 for i in range(1,n+1)}
  def find(self,a):
    if self.parent[a]==a:
      return a
    else:
      self.parent[a]=self.find(self.parent[a])
      return self.parent[a]
  def unite(self,a,b):
    a=self.find(a)
    b=self.find(b)
    if self.height[a]>self.height[b]:
      self.parent[b]=a
    else:
      if self.height[a]==self.height[b]:
        self.height[b]+=1
      self.parent[a]=b
  def isunited(self,a,b):
    return self.find(a)==self.find(b)


n,k,l=map(int,input().split())
uk=UFT(n)
ul=UFT(n)
dc=dd(int)

for _ in range(k):
  a,b=map(int,input().split())
  uk.unite(a,b)

for _ in range(l):
  a,b=map(int,input().split())
  ul.unite(a,b)
  
for i in range(1,n+1):
  dc[(uk.parent[i],ul.parent[i])]+=1

print(" ".join(map(str,(dc[(uk.parent[i],ul.parent[i])] for i in range(1,n+1)))))

Submission status: Wrong Answer

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


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

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


uf1 = UnionFind(n)
uf2 = UnionFind(n)

rec = set()
for i in range(k):
    p, q = map(int, input().split())
    uf1.unite(p - 1, q - 1)
    rec.add((p - 1, q - 1))

num = [1] * n
for i in range(l):
    r, s = map(int, input().split())
    uf2.unite(r - 1, s - 1)
    if (r - 1, s - 1) not in rec:
        rec.add((r - 1, s - 1))

rec = list(rec)
for a, b in rec:
    if uf1.same(a, b) and uf2.same(a, b):
        num[a] += 1
        num[b] += 1


print(" ".join(map(str, num)))

Submission status: Wrong Answer

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


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

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


uf1 = UnionFind(n)
uf2 = UnionFind(n)

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

num = [1] * n
for i in range(l):
    r, s = map(int, input().split())
    uf2.unite(r - 1, s - 1)
    if uf1.same(r - 1, s - 1):
        num[r - 1] += 1
        num[s - 1] += 1

print(" ".join(map(str, num)))

Submission status: Wrong Answer

Solution code:
from collections import Counter
class UnionFind:
    #Union Find木のクラス

    def __init__(self, n):
        #親要素のノード番号を格納。par[x] == xのときそのノードはroot
        self.par = [i for i in range(n)]
        #木の高さ（初期状態では0）
        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 same(x, y):
        # xとyが同じ集合に属するかを判定
        return self.find(x) == self.find(y)

    def union(self, x, y):
        #併合する
        #まず根を探す
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


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

for i in range(K):
    pi, qi = map(lambda x: int(x) - 1, input().split())
    road.union(pi, qi)

for i in range(L):
    ri, si = map(lambda x: int(x) - 1, input().split())
    rail.union(ri, si)


road_and_rail = [(road.par[i], rail.par[i]) for i in range(N)]
count = Counter(road_and_rail)

ans = []
for i in range(N):
    ans.append(str(count.get(road_and_rail[i])))
print(' '.join(ans))

Submission status: Wrong Answer

Solution code:
n,k,l=map(int,input().split())
ro1=[[] for i in range(n)]
ra1=[[] for i in range(n)]
ro2=[i for i in range(n)]
ra2=[i for i in range(n)]
pair=[]
con=[1 for i in range(n)]
for i in range(k):
    p,q=map(int,input().split()) 
    ro1[p-1].append(q-1)
    ro1[q-1].append(p-1)
for i in range(l):
    r,s=map(int,input().split()) 
    ra1[r-1].append(s-1)
    ra1[s-1].append(r-1)
    
#どうやって解説の言うar[i]=ar[j]を実現するか
def drawro(num):
    for i in ro1[num]:
        if ro2[i]==ro2[num]:
            return
        else:
            ro2[i]=ro2[num]
        drawro(i)
    return   

def drawra(num):
    for i in ra1[num]:
        if ra2[i]==ra2[num]:
            return
        else:
            ra2[i]=ra2[num]
        drawro(i)
    return   

for i in range(n):
    drawro(i)
    drawra(i)
for i in range(n):
    pair.append(ro2[i]*10+ra2[i])
for i in set(pair):
    a=[]
    for k in range(n):
        if i==pair[k]:
            a.append(k)
    for j in a:
        con[j]+=len(a)-1
for i in range(n):
    print(con[i],end=" ")

Submission status: Wrong Answer

Solution code:
n,k,l=map(int,input().split())
ro1=[[] for i in range(n)]
ra1=[[] for i in range(n)]
ro2=[i for i in range(n)]
ra2=[i for i in range(n)]
pair=[]
con=[1 for i in range(n)]
for i in range(k):
    p,q=map(int,input().split()) 
    ro1[p-1].append(q-1)
for i in range(l):
    r,s=map(int,input().split()) 
    ra1[r-1].append(s-1)
for i in range(n):
    for j in ro1[i]:
        ro2[j]=ro2[i]
    for k in ra1[i]:
        ra2[k]=ra2[i]
for i in range(n):
    pair.append([ro2[i],ra2[i]])
pair.append([n,n])
for i in range(n-1):
    if pair[i]==pair[i+1]:
        con[i]+=1
        if pair[i+1]!=pair[i+2]:
            con[i+1]+=1
for i in range(n):
    print(con[i],end=" ")

Submission status: Wrong Answer

Solution code:
n,k,l=map(int,input().split())
br=[[0 for i in range(n)] for j in range(n)]
co=[1 for i in range(n)]
for i in range(k):
    p,q=map(int,input().split())
    br[p-1][q-1]=1
for i in range(l):
    r,s=map(int,input().split())
    if br[r-1][s-1]==1:
        co[r-1]+=1
        co[s-1]+=1
for i in range(n):
    print(co[i], end=" ")

Submission status: Wrong Answer

Solution code:
N, K, L = map(int, input().split())
G = [[[], []] for i in range(N)]
R = [[i, i] for i in range(N)]
def root(i, j):
  if R[i][j] != i:
    R[i][j] = root(R[i][j], j)
  return R[i][j]
for i in range(K):
  p, q = map(int, input().split())
  rp = root(p - 1, 0)
  rq = root(q - 1, 0)
  if rp != rq:
    R[rp][0] = min(rp, rq)
    R[rq][0] = min(rp, rq)
for i in range(L):
  r, s = map(int, input().split())
  rr = root(r - 1, 1)
  rs = root(s - 1, 1)
  if rr != rs:
    R[rr][1] = min(rr, rs)
    R[rs][1] = min(rr, rs)
U = [[[], []] for i in range(N)]
for i in range(N):
  R[i][0] = root(i, 0)
  R[i][1] = root(i, 1)
  U[R[i][0]][0].append(i)
  U[R[i][1]][1].append(i)
A = [1 for i in range(N)]
for i in range(N):
  if A[i] == 1:
    S = set(U[R[i][0]][0]) & set(U[R[i][1]][1])
    for s in S:
      A[s] = len(S)
ans = ''
for a in A:
  ans += ' ' + str(a)
print(A)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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


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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x

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


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

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


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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from heapq import heappop, heappush
from collections import Counter

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


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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x

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


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

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

c = Counter(zip(uf1.par, uf2.par))
for i in range(N):
    p1 = uf1.find(i)
    p2 = uf2.find(i)
    print(c[(p1, p2)])

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

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

    def union(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

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

for _ in range(K):
    p,q = map(int,input().split())
    ufa.union(p,q)
for _ in range(L):
    r,s = map(int,input().split())
    ufb.union(r,s)

pairs = {}
for i in range(1,N+1):
    key = (ufa.par[i],ufb.par[i])
    if  key in pairs.keys():
        pairs[key] +=1
    else:
        pairs[key] =1
ans = []
for i in range(1,N+1):
    ans.append(str(pairs[(ufa.par[i],ufb.par[i])]))
print(' '.join(ans))

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * (n+1)

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

    def union(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

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

for _ in range(K):
    p,q = map(int,input().split())
    ufa.union(p-1,q-1)
for _ in range(L):
    r,s = map(int,input().split())
    ufb.union(r-1,s-1)

pairs = {}
for i in range(N):
    key = (ufa.par[i],ufb.par[i])
    if  key in pairs.keys():
        pairs[key] +=1
    else:
        pairs[key] =1
ans = []
for i in range(N):
    ans.append(str(pairs[(ufa.par[i],ufb.par[i])]))
print(' '.join(ans))

Submission status: Wrong Answer

Solution code:
n, k, l = [int(i) for i in input().split()]
P = [[int(i) for i in input().split()] for j in range(k)]
R = [[int(i) for i in input().split()] for j in range(l)]

class UnionFind():
  def __init__(self, elements):
    self.elements = elements
    self._root = {}
    for e in self.elements:
      self._root[e] = e
    
  def union(self, x, y):
    x = self.root(x)
    y = self.root(y)
    if not x == y:
      self._root[x] = y
    
  def root(self, x):
    if not self._root[x] == x:
      self._root[x] = self.root(self._root[x])
    return self._root[x]
  
  def count(self):
    cnt = {}
    for e in self.elements:
      cnt[self.root(e)] += cnt.get(self.root(e), 0)
      
    for e in self.elements:
      yield cnt.get(e, 0)
      
  def get_union(self):
    union = {}
    for e in self.elements:
      if self.root(e) in union:
        union[self.root(e)].add(e)
      else:
        union[self.root(e)] = {e}
    return union
      
  
road = UnionFind(range(1, n+1))
rail = UnionFind(range(1, n+1))

for i in range(k):
  road.union(P[i][0], P[i][1])
  
for i in range(l):
  rail.union(R[i][0], R[i][1])

road.union = road.get_union()
rail.union = rail.get_union()

for e in range(1, n+1):
  print(len(road.union[road.root(e)] & rail.union[rail.root(e)]), end='')

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

class Unionfindtree:
    def __init__(self,number):
        self.par = [i for i in range(number)]
        self.rank = [0]*(number)

    def find(self,x):#親を探す
        if self.par[x] ==x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self,x,y):#x,yを繋げる
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return 
        if self.rank[px]<self.rank[py]:
            self.par[px]=py
        else:
            self.par[py]=px
        if self.rank[px]==self.rank[py]:
            self.rank[px] +=1
    
    def connect(self,x,y):#親が同じかみる
        return self.find(x)==self.find(y)

N,K,L = map(int,input().split())
load = Unionfindtree(N)
train = Unionfindtree(N)
for i in range(K):
    a,b = map(int,input().split())
    load.union(a-1,b-1)
for i in range(L):
    a,b = map(int,input().split())
    train.union(a-1,b-1)

ar = [(load.par[i],train.par[i]) for i in range(N)]

dd = defaultdict(int)
for s in ar:
    dd[s] += 1
ans =[]
for i in range(N):
    ans.append(dd[ar[i]])
print(' '.join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
from bisect import bisect
n,k,l = (int(i) for i in input().split())
def root(x):
	if par[x]!=x: par[x] = root(par[x])
	return par[x]
def unite(x,y):
	x2,y2 = root(x),root(y)
	if x2!=y2:
		if rank[x2]<rank[y2]: par[x2] = y2
		else: par[y2] = x2
		if rank[x2]==rank[y2]: rank[x2]+=1
r = [[int(i) for i in input().split()] for i in range(k)]
t = [[int(i) for i in input().split()] for i in range(l)]
x = [[0,0] for i in range(n+1)]
par,rank = [i for i in range(n+1)],[0 for i in range(n+1)]
for i,j in r: unite(i,j)
for i in range(1,n+1): x[i][0]=root(i)
par,rank = [i for i in range(n+1)],[0 for i in range(n+1)]
for i,j in t: unite(i,j)
for i in range(1,n+1): x[i][1]=root(i)
x,y = sorted(x),deepcopy(x)
for i in y[1:n-1]:
	print(bisect(x,i)-bisect(x,[i[0],i[1]-1]),end=" ")
print(bisect(x,y[-1])-bisect(x,[y[-1][0],y[-1][1]-1]))

Submission status: Wrong Answer

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

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def check(self, x, y):
        return self.find(x) == self.find(y)

P,Q = UnionFind(N),UnionFind(N)
for _ in range(K):
    x,y = map(int,input().split())
    P.unite(x,y)
for _ in range(L):
    x,y = map(int,input().split())
    Q.unite(x,y)

D = defaultdict(int)
for i in range(1,N+1):
    D[P.par[i],Q.par[i]] += 1

print(" ".join(map(str,list(D[P.par[i],Q.par[i]] for i in range(1,N+1)))))