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:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


class UF_tree:
    def __init__(self, n):
        self.root = [-1] * (n + 1)  # -1ならそのノードが根,で絶対値が木の要素数
        self.rank = [0] * (n + 1)

    def find(self, x):  # xの根となる要素番号を返す
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        elif self.rank[x] < self.rank[y]:
            self.root[y] += self.root[x]
            self.root[x] = y
        else:
            self.root[x] += self.root[y]
            self.root[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def getNodeLen(self, x):
        return -self.root[self.find(x)]


if __name__ == "__main__":
    N, K, L = map(int, input().split())
    uf = UF_tree(N + 1)
    for _ in range(K):
        a, b = map(int, input().split())
        uf.unite(a, b)

    ans = [1] * (N + 1)
    for _ in range(L):
        a, b = map(int, input().split())
        if uf.isSame(a, b):
            ans[a] += 1
            ans[b] += 1
    print(*ans[1:])

Submission status: Wrong Answer

Solution code:
n,k,l=map(int,input().split())
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)
    def count(self, x):
        return -self.root[self.find(x)]
uf1=unionfind(n)
uf2=unionfind(n)
uf3=unionfind(n)
for i in range(k):
    p,q=map(int,input().split())
    uf1.unite(p,q)
for i in range(l):
    p,q=map(int,input().split())
    uf2.unite(p,q)
    if uf1.same(p,q):
        uf3.unite(p,q)
ans=[0]*(n+1)
for i in range(1,n+1):
    ans[i]=uf3.count(i)
print(" ".join(map(str,ans[1:])))

Submission status: Wrong Answer

Solution code:
from collections import *
from heapq import *
from itertools import *
import sys
import copy
from bisect import *
sys.setrecursionlimit(10**9)
N,K,L = map(int,input().split())
RoLists=[[] for i in range(N)]
RaLists=[[] for _ in range(N)]
for i in range(K):
    p,q=map(int,input().split())
    RoLists[p-1].append(q-1)
    RoLists[q-1].append(p-1)
for j in range(L):
    p,q=map(int,input().split())
    RaLists[p-1].append(q-1)
    RaLists[q-1].append(p-1)
def dfs(g, v, visited):
    if not visited[v]:
        yield v
        visited[v] = True
        for w in iter(g[v]):
            for x in dfs(g, w, visited):
                yield x
def r_dfs(g,v):
    visited = [False] * N
    for x in dfs(g, v, visited):
        yield x
for i in range(N):
    ans=0
    print(r_dfs(RoLists, i))
    for h in r_dfs(RoLists, i):
        for j in r_dfs(RaLists, i):
            if j == h:
                ans+=1
    print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents=[-1]*n
    def find(self,x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        if self.parents[x]>self.parents[y]:
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i)==root]
    def roots(self):
        return [i for i,x in enumerate(self.parents) if x<0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

n,k,l=map(int,input().split())
uf1=UnionFind(n)
uf2=UnionFind(n)
for _ in range(k):
  u,v=map(int,input().split())
  uf1.unite(u-1,v-1)
for _ in range(l):
  u,v=map(int,input().split())
  uf2.unite(u-1,v-1)
ar=[0]*n
br=[0]*n
for i in range(n):
  ar[i]=uf1.find(i)
  br[i]=uf2.find(i)
dic={}
for i in range(n):
  if ar[i]>br[i]:
    ar[i],br[i]=br[i],ar[i]
  if not (ar[i],br[i]) in dic:
    dic[(ar[i],br[i])]=1
  else:
    dic[(ar[i],br[i])]+=1
ans=[]
for i in range(n):
  ans.append(dic[(ar[i],br[i])])
print(*ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd
import queue
N, K, L = map(int,input().split())
PQ = [tuple(map(int,input().split())) for _ in range(K)]
RS = [tuple(map(int,input().split())) for _ in range(L)]

road = [[] for _ in range(N)]
railroad = [[] for _ in range(N)]
for p,q in PQ:
    road[p-1].append(q-1)
    road[q-1].append(p-1)
for r,s in RS:
    railroad[r-1].append(s-1)
    railroad[s-1].append(r-1)

uf_road = [0]*N
uf_railroad = [0]*N
idx_road = 1
idx_railroad = 1
# 連結判定
for i in range(N):
    if uf_road[i] == 0:
        q = queue.Queue()
        q.put(i)
        while not q.empty():
            now_node = q.get()
            print(now_node)
            uf_road[now_node] = idx_road
            for target in road[now_node]:
                road[target].remove(now_node)
                q.put(target)
            road[now_node] = []
        idx_road += 1
    if uf_railroad[i] == 0:
        q = queue.Queue()
        q.put(i)
        while not q.empty():
            now_node = q.get()
            uf_railroad[now_node] = idx_railroad
            for target in railroad[now_node]:
                railroad[target].remove(now_node)
                q.put(target)
            railroad[now_node] = []
        idx_railroad += 1
dic = dd(int)
#print(uf_road)
#print(uf_railroad)
for i,j in zip(uf_road, uf_railroad):
    dic[(i,j)] += 1
res = [dic[(i,j)] for i,j in zip(uf_road, uf_railroad)]
print(*res)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd
import queue
N, K, L = map(int,input().split())
PQ = [tuple(map(int,input().split())) for _ in range(K)]
RS = [tuple(map(int,input().split())) for _ in range(L)]

road = [[] for _ in range(N)]
railroad = [[] for _ in range(N)]
for p,q in PQ:
    road[p-1].append(q-1)
    road[q-1].append(p-1)
for r,s in RS:
    railroad[r-1].append(s-1)
    railroad[s-1].append(r-1)

uf_road = [0]*N
uf_railroad = [0]*N
idx_road = 1
idx_railroad = 1
# 連結判定
for i in range(N):
    if uf_road[i] == 0:
        q = queue.Queue()
        q.put(i)
        while not q.empty():
            now_node = q.get()
            uf_road[now_node] = idx_road
            for target in road[now_node]:
                road[target].remove(now_node)
                road[now_node].remove(target)
                q.put(target)
                #if uf_road[target] == 0:
                #    q.put(target)
        idx_road += 1
    if uf_railroad[i] == 0:
        q = queue.Queue()
        q.put(i)
        while not q.empty():
            now_node = q.get()
            uf_railroad[now_node] = idx_railroad
            for target in railroad[now_node]:
                railroad[target].remove(now_node)
                railroad[now_node].remove(target)
                q.put(target)
        idx_railroad += 1
dic = dd(int)
for i,j in zip(uf_road, uf_railroad):
    dic[(i,j)] += 1
res = [dic[(i,j)] for i,j in zip(uf_road, uf_railroad)]
print(*res)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
class UnionFindNode:
    def __init__(self, group_id, parent=None, value=None):
        self.group_id_ = group_id
        self.parent_ = parent
        self.value = value
        self.rank_ = 1
        self.member_num_ = 1

    def is_root(self):
        return not self.parent_

    def root(self):
        parent = self
        while not parent.is_root():
            parent = parent.parent_
            self.parent_ = parent
        return parent

    def find(self):
        root = self.root()
        return root.group_id_

    def rank(self):
        root = self.root()
        return root.rank_

    def unite(self, unite_node):
        root = self.root()
        unite_root = unite_node.root()

        if root.group_id_ != unite_root.group_id_:
            if root.rank() > unite_root.rank():
                n_root, child = root, unite_root
            else:
                n_root, child = unite_root, root
            child.parent_ = n_root
            n_root.rank_ = max(n_root.rank_, child.rank_ + 1)
            n_root.member_num_ = n_root.member_num_ + child.member_num_
N, K, L = map(int, input().split())
node_list1 = [UnionFindNode(i) for i in range(N)]
for _ in range(K):
    a, b = map(int, input().split())
    node_list1[a-1].unite(node_list1[b-1])
    
node_list2 = [UnionFindNode(i) for i in range(N)]
for _ in range(L):
    a, b = map(int, input().split())
    if node_list1[a-1].find() == node_list1[b-1].find():
        node_list2[a-1].unite(node_list2[b-1])
for i in range(N):
    print(node_list2[i].root().member_num_)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
con = 300000

def getlist():
	return list(map(int, input().split()))

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

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

#処理内容
def main():
	#受け取り、処理
	N, K, L = getlist()
	UFp = UnionFind(N)
	UFr = UnionFind(N)
	for i in range(K):
		p, q = getlist()
		UFp.union(p, q)
	for i in range(L):
		r, s = getlist()
		UFr.union(r, s)

	s1 = UFp.par
	s2 = UFr.par
	s3 = []
	for i in range(1, N + 1):
		s3.append([s1[i], s2[i]])

	#前計算
	D = defaultdict(int)
	for i in range(N):
		a = s3[i][0]
		b = s3[i][1]
		D[a * con + b] += 1
	#答え
	ans = []
	for i in range(N):
		ans.append(D[s3[i][0] * con + s3[i][1]])
	print(" ".join(list(map(str, ans))))

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
con = 10 ** 9 + 7

def getlist():
	return list(map(int, input().split()))

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

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

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

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

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

#処理内容
def main():
	#受け取り、処理
	N, K, L = getlist()
	UFp = UnionFind(N)
	UFr = UnionFind(N)
	for i in range(K):
		p, q = getlist()
		UFp.union(p - 1, q - 1)
	for i in range(L):
		r, s = getlist()
		UFr.union(r - 1, s - 1)

	s1 = UFp.par
	s2 = UFr.par
	s3 = []
	for i in range(N):
		s3.append([s1[i], s2[i]])

	#前計算
	D = defaultdict(int)
	for i in range(N):
		a = s3[i][0]
		b = s3[i][1]
		D[a * con + b] += 1
	#答え
	ans = []
	for i in range(N):
		ans.append(D[s3[i][0] * con + s3[i][1]])
	print(" ".join(list(map(str, ans))))

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
con = 10 ** 9 + 7

def getlist():
	return list(map(int, input().split()))

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

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

#処理内容
def main():
	#受け取り、処理
	N, K, L = getlist()
	UFp = UnionFind(N)
	UFr = UnionFind(N)
	for i in range(K):
		p, q = getlist()
		UFp.union(p, q)
	for i in range(L):
		r, s = getlist()
		UFr.union(r, s)

	s1 = UFp.par
	s2 = UFr.par
	s3 = []
	for i in range(1, N + 1):
		s3.append(sorted([s1[i], s2[i]]))

	#前計算
	D = defaultdict(int)
	for i in range(N):
		a = s3[i][0]
		b = s3[i][1]
		D[a * con + b] += 1
	#答え
	ans = []
	for i in range(N):
		ans.append(D[s3[i][0] * con + s3[i][1]])
	print(" ".join(list(map(str, ans))))

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
con = 10 ** 9 + 7

def getlist():
	return list(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 same_check(self, 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

#処理内容
def main():
	#受け取り、処理
	N, K, L = getlist()
	UFp = UnionFind(N)
	UFr = UnionFind(N)
	for i in range(K):
		p, q = getlist()
		UFp.union(p, q)
	for i in range(L):
		r, s = getlist()
		UFr.union(r, s)

	s1 = UFp.par
	s2 = UFr.par
	s3 = []
	for i in range(1, N + 1):
		s3.append(sorted([s1[i], s2[i]]))

	#前計算
	D = defaultdict(int)
	for i in range(N):
		a = s3[i][0]
		b = s3[i][1]
		D[a * con + b] += 1
	#答え
	ans = []
	for i in range(N):
		ans.append(D[s3[i][0] * con + s3[i][1]])
	print(" ".join(list(map(str, ans))))

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
con = 10 ** 9 + 7

def getlist():
	return list(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 same_check(self, 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

#処理内容
def main():
	#受け取り、処理
	N, K, L = getlist()
	UFp = UnionFind(N)
	UFr = UnionFind(N)
	for i in range(K):
		p, q = getlist()
		UFp.union(p, q)
	for i in range(L):
		r, s = getlist()
		UFr.union(r, s)

	s1 = UFp.par
	s2 = UFr.par
	s3 = []
	for i in range(1, N + 1):
		s3.append([s1[i], s2[i]])

	#前計算
	D = defaultdict(int)
	for i in range(N):
		a = s3[i][0]
		b = s3[i][1]
		D[a * con + b] += 1
	#答え
	ans = []
	for i in range(N):
		ans.append(D[s3[i][0] * con + s3[i][1]])
	print(" ".join(list(map(str, ans))))

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline

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

    def unite(self,x,y):
        x=self.findroot(x)
        y=self.findroot(y)
        if self.rank[x]==self.rank[y]:
            self.rank[x]+=1
        if self.rank[x]<self.rank[y]:
            self.par[x]=y
            self.size[y]+=self.size[x]
        else:
            self.par[y]=x
            self.size[x]+=self.size[y]
    
    def issame(self,x,y):
        return self.findroot(x)==self.findroot(y)
    
    def size(self,x):
        x=self.findroot(x)
        return self.size[x]
    
    def root(self):
        return self.par

n,k,l=map(int,input().split())
road=UnionFind(n)
railway=UnionFind(n)
for _ in range(k):
    p,q=map(int,input().split())
    road.unite(p,q)
for _ in range(l):
    r,s=map(int,input().split())
    railway.unite(r,s)

roadroot=road.root()
railroot=railway.root()
D={}
for i in range(1,n+1):
    x,y=roadroot[i],railroot[i]
    if (x,y) in D:
        D[(x,y)]+=1
    else:
        D[(x,y)]=1

for j in range(1,n+1):
    print(D[(roadroot[j],railroot[j])], end=" ")

Submission status: Wrong Answer

Solution code:
N,K,L = [int(x) for x in input().split()]
li = []
road_set = [set([i]) for i in range(N)]
rail_set = [set([i]) for i in range(N)]
for _ in range(K):
    a,b = [int(x) for x in input().split()]
    road_set[a-1] |= road_set[b-1]
    road_set[b-1] |= road_set[a-1]
for _ in range(L):
    a,b = [int(x) for x in input().split()]
    rail_set[a-1] |= rail_set[b-1]
    rail_set[b-1] |= rail_set[a-1]

for i in range(N):
    li.append(len(road_set[i] & rail_set[i]))
print(*li)
#print(road_set,rail_set)

Submission status: Wrong Answer

Solution code:
class UnionFind :
    """
    Union Find木
    ---
    頂点のインデックスは0~

    Attributes
    ---
    parent : list<int>
        親のリスト．parent[頂点のインデックス] = 親のインデックス
    height : list<int>
        各木の高さ
    size : list<int>
        各木の頂点数
    component : int
        連結成分の数
    """

    def __init__(self, size) :
        """
        Parameters
        ---
        size : int
            頂点数
        """
        self.parent = list(range(size))
        self.height = [0] * size
        self.size = [1] * size
        self.component = size

    def root(self, index) :
        """
        親のインデックスの取得

        Parameters
        ---
        index : int
            取得する頂点のインデックス

        Returns
        ---
        rootIndex : int
            指定した頂点の根のインデックス
        """
        if self.parent[index] == index :  # 根の場合
            return index
        rootIndex = self.root(self.parent[index])  # 葉の場合親の根を取得
        self.parent[index] = rootIndex  # 親の付け直し
        return rootIndex

    def union(self, index1, index2) :  # 結合
        """
        木の結合

        Parameters
        ---
        index1 : int
        index2 : int
            結合する頂点のインデックス
        """
        root1 = self.root(index1)
        root2 = self.root(index2)

        if root1 == root2 :  # 連結されている場合
            return

        self.component -= 1  # 連結成分を減らす

        if self.height[root1] < self.height[root2] :
            self.parent[root1] = root2  # root2に結合
            self.size[root2] += self.size[root1]
        else :
            self.parent[root2] = root1  # root1に結合
            self.size[root1] += self.size[root2]
            if self.height[root1] == self.height[root2] :
                self.height[root1] += 1
        return

    def isSameRoot(self, index1, index2) :
        """
        同じ木に属するかを判定する

        Parameters
        ---
        index1 : int
        index2 : int

        Returns
        ---
        boolean
        """
        return self.root(index1) == self.root(index2)

    def sizeOfSameRoot(self, index) :
        """
        指定した頂点の属する木の大きさを取得する
        """
        return self.size[self.root(index)]

    def getComponent(self) :
        """
        連結成分数を取得する
        """
        return self.component

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

tree = UnionFind(N)

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

ans = [1 for _ in range(N)]

for _ in range(L):
    r, s = map(int, input().split())
    if tree.isSameRoot(r - 1, s - 1):
        ans[r - 1] += 1
        ans[s - 1] += 1

print(*ans)

Submission status: Wrong Answer

Solution code:
import collections

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

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

def solve():
 n,k,l = (int(i) for i in input().split())
 ufr = UnionFind(n-1)
 for i in range(k):
   tmp1,tmp2 = (int(i) for i in input().split())
   ufr.union(tmp1-1,tmp2-1)
 uft = UnionFind(n-1)
 for i in range(l):
   tmp1,tmp2 = (int(i) for i in input().split())
   uft.union(tmp1-1,tmp2-1)
 query = []
 for i in range(n):
    query.append((ufr.par[i],uft.par[i]))
 c = collections.Counter(query)
 ans = []
 for i in range(n):
  ans.append(c[query[i]])
 print(*ans)

solve()

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)
        self.size = [1] * (n+1)
    
    # 根を検索する関数
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.find(self.par[x])
  
    # 結合(unite)する関数
    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
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    
    # 同じグループに属するかを判定する関数
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
    # 要素が属する木の深さを返す関数
    def get_depth(self, x):
        return self.rank[self.find(x)]
    
    # 要素が属する木のサイズを返す関数
    def get_size(self, x):
        return self.size[self.find(x)]
    
    # グループ数を返す関数
    def group_sum(self):
        c = 0
        for i in range(len(self.par)):
            if self.find(i) == i:
                c += 1
        return c

if __name__ == "__main__":
    N,K,L = map(int, input().split())
    uf_road = UnionFind(N)
    uf_train = UnionFind(N)

    for i in range(K):
        p, q = [int(i) for i in input().split()]
        uf_road.unite(p, q)
    
    r, s = [0]*L, [0]*L
    ans = [1]*N
    for i in range(L):
        r[i], s[i] = [int(i) for i in input().split()]
        uf_train.unite(r[i], s[i])
    
    for i in range(L):
        if uf_road.same_check(r[i], s[i]) and uf_train.same_check(r[i], s[i]):
            ans[r[i]-1] += 1
            ans[s[i]-1] += 1
    
    print(*ans)

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)
        self.size = [1] * (n+1)
    
    # 根を検索する関数
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.find(self.par[x])
  
    # 結合(unite)する関数
    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
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    
    # 同じグループに属するかを判定する関数
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
    # 要素が属する木の深さを返す関数
    def get_depth(self, x):
        return self.rank[self.find(x)]
    
    # 要素が属する木のサイズを返す関数
    def get_size(self, x):
        return self.size[self.find(x)]
    
    # グループ数を返す関数
    def group_sum(self):
        c = 0
        for i in range(len(self.par)):
            if self.find(i) == i:
                c += 1
        return c

if __name__ == "__main__":
    N,K,L = map(int, input().split())
    uf_road = UnionFind(N)
    uf_train = UnionFind(N)

    for i in range(K):
        p, q = [int(i) for i in input().split()]
        uf_road.unite(p, q)
    
    ans = [1]*N
    for i in range(L):
        r, s = [int(i) for i in input().split()]
        uf_train.unite(r, s)
        if uf_road.same_check(r, s):
            ans[r-1] += 1
            ans[s-1] += 1
    
    print(*ans)

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)
        self.size = [1] * (n+1)
    
    # 根を検索する関数
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.find(self.par[x])
  
    # 結合(unite)する関数
    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
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    
    # 同じグループに属するかを判定する関数
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
    # 要素が属する木の深さを返す関数
    def get_depth(self, x):
        return self.rank[self.find(x)]
    
    # 要素が属する木のサイズを返す関数
    def get_size(self, x):
        return self.size[self.find(x)]
    
    # グループ数を返す関数
    def group_sum(self):
        c = 0
        for i in range(len(self.par)):
            if self.find(i) == i:
                c += 1
        return c

if __name__ == "__main__":
    N,K,L = map(int, input().split())
    uf = UnionFind(N)

    for i in range(K):
        p, q = [int(i) for i in input().split()]
        uf.unite(p, q)
    
    ans = [1]*N
    for i in range(L):
        r, s = [int(i) for i in input().split()]
        if uf.same_check(r, s):
            ans[r-1] += 1
            ans[s-1] += 1
    
    print(*ans)

Submission status: Wrong Answer

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

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

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

    def union(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            if self.rank[x] > self.rank[y]:
                self.parent[y] = self.parent[x]
                self.size[x] += self.size[y]
            elif self.rank[y] > self.rank[x]:
                self.parent[x] = self.parent[y]
                self.size[y] += self.size[x]
            else:
                self.parent[y] = self.parent[x]
                self.rank[x] += 1
                self.size[x] += self.size[y]

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

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

uf_road_railway = UnionFind(N)
for i in range(L):
    r, s = map(int, input().split())
    r -= 1
    s -= 1
    if uf_road.find(r, s):
        uf_road_railway.union(r, s)
print(" ".join((map(lambda x: str(uf_road_railway.size[uf_road_railway.root(x)]), range(N)))))