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: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(4100000)

import math

import logging

logging.basicConfig(level=logging.DEBUG)

logger = logging.getLogger(__name__)

from unionfind import UnionFind, UnionFindCounter


def resolve():
    # S = [x for x in sys.stdin.readline().split()][0]  # 文字列 一つ
    # N = [int(x) for x in sys.stdin.readline().split()][0]  # int 一つ
    N, K, L = [int(x) for x in sys.stdin.readline().split()]  # 複数int
    # grid = [list(sys.stdin.readline().split()[0]) for _ in range(N)]  # 文字列grid
    grid = [[int(x) - 1 for x in sys.stdin.readline().split()]
            for _ in range(K + L)]  # int grid

    logger.debug('{}'.format([]))

    p_uf = UnionFind(N)
    r_uf = UnionFind(N)
    both_uf = UnionFindCounter(N)

    for k in range(K):
        p, q = grid[k]
        p_uf.unite(p, q)

    for l in range(K, K + L):
        r, s = grid[l]
        r_uf.unite(r, s)
        if p_uf.isSame(r, s):
            both_uf.unite(r, s)

    print(' '.join([str(x) for x in both_uf.getCount()]))


if __name__ == "__main__":
    resolve()

# AtCoder Unit Test で自動生成できる, 最後のunittest.main は消す
# python -m unittest template/template.py で実行できる
# pypy3 -m unittest template/template.py で実行できる

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """4 3 1
1 2
2 3
3 4
2 3"""
        output = """1 2 2 1"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """4 2 2
1 2
2 3
1 4
2 3"""
        output = """1 2 2 1"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """7 4 4
1 2
2 3
2 5
6 7
3 5
4 5
3 4
6 7"""
        output = """1 1 2 1 2 2 2"""
        self.assertIO(input, output)

    def test_入力例_4(self):
        input = """2 1 1
1 2
1 2"""
        output = """2 2"""
        self.assertIO(input, output)

Submission status: Runtime Error

Solution code:
import numpy as np

a,b,c= input().split(" ")

arr_x = np.repeat(0, int(a)**2).reshape(int(a), int(a))
arr_y = np.repeat(0, int(a)**2).reshape(int(a), int(a))

for i in range(int(b)):
  inb = input().split(" ")
  arr_x[int(inb[0])-1][int(inb[1])-1] = 1
  arr_x[int(inb[1])-1][int(inb[0])-1] = 1



for i in range(int(c)):
  inb = input().split(" ")
  arr_y[int(inb[0])-1][int(inb[1])-1] = 1
  arr_y[int(inb[1])-1][int(inb[0])-1] = 1

for i in range(int(a)):
  arr_x[i][i]=1
  for n in range(int(a)-1):
    if(arr_x[i][n]==1):
      arr_x[i]= arr_x[i] + arr_x[n]

for i in range(int(a)):
  arr_y[i][i]=1
  for n in range(int(a)):
    if(arr_y[i][n]==1):
      arr_y[i]= arr_y[i] + arr_y[n]

        

arr_x = -(arr_x * -1 //2**10)
arr_y = -(arr_y * -1 //2**10)
asd = arr_x + arr_y
asd = asd//2
ans = asd.sum(axis=0)

for i in range(int(a)):
  print(ans[i], end="")

Submission status: Runtime Error

Solution code:
#D - 連結 / Connectivity
#https://atcoder.jp/contests/abc049/tasks/arc065_b
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 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]

p = UnionFind(n)
r = UnionFind(n)
ans = []
n, k, l = list(map(int,input().split()))
for _ in range(k):
    a,b = list(map(int,input().split()))
    p.union(a-1,b-1)
for _ in range(l):
    c, d = list(map(int,input().split()))
    r.union(c-1,d-1)
for i in range(n):
    s = p.members(i)
    t = r.members(i)
    #print(s,t)
    count = 0
    for i in s:
        if i in t:
            count += 1
    ans.append(count)

#print(''.join(ans))、なぜか通らない、おそらくstrに変更しないと不可の模様
print(' '.join(map(str, ans)))

Submission status: Runtime Error

Solution code:
N, K, L = map(int, input().split())
uf = UnionFind(2 * N)
for _ in range(K):
    p, q = map(int, input().split())
    uf.union(p - 1, q - 1)

for _ in range(L):
    r, s = map(int, input().split())
    uf.union(r - 1 + N, s - 1 + N)

ans = [0] * N
for i in range(N):
    cnt = 0
    for j in range(N):
        if uf.find(i) == uf.find(j) and uf.find(i + N) == uf.find(j + N):
            cnt += 1
    ans[i] = cnt

for i in range(N - 1):
    print(ans[i], end=' ')
print(ans[N - 1])

Submission status: Runtime Error

Solution code:
# union-find木
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

## 
# N個の都市
# K本の道路
# L本の鉄道
N, K, L = map(int, input().split())

# N都市を初期の要素数とする
# 道路と鉄道をそれぞれ別のunion-find木として表現する
uf_p = UnionFind(N)
uf_t = UnionFind(N)

# 道路の木
for _ in range(K):
    x,y = map(int, input().split())
    uf_p.union(x-1,y-1)

# 鉄道の木
for _ in range(L):
    x,y = map(int, input().split())
    uf_.tunion(x-1,y-1)

    
# 出力結果を整形
result = []
for i in range(N):
    # 道路と鉄道の両方繋がっている件数をand条件で抽出する
    result.append(str(len(set(uf_p.members(i)) & set(uf_t.members(i)))))

print(" ".join(result))

Submission status: Runtime Error

Solution code:
# union-find木
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

## 
# N個の都市
# K本の道路
# L本の鉄道
N, K, L = map(int, input().split())

# N都市を初期の要素数とする
# 道路と鉄道をそれぞれ別のunion-find木として表現する
uf_p = UnionFind(N)
uf_t = UnionFind(N)

# 道路の木
for _ in range(K):
    x,y = map(int, input().split())
    uf_p.union(px-1,py-1)

# 鉄道の木
for _ in range(L):
    x,y = map(int, input().split())
    uf_.tunion(px-1,py-1)

    
# 出力結果を整形
result = []
for i in range(N):
    # 道路と鉄道の両方繋がっている件数をand条件で抽出する
    result.append(str(len(set(uf_p.members(i)) & set(uf_t.members(i)))))

print(" ".join(result))

Submission status: Runtime Error

Solution code:
# union-find木
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

## 
# N個の都市
# K本の道路
# L本の鉄道
N, K, L = map(int, input().split())

# N都市を初期の要素数とする
# 道路と鉄道をそれぞれ別のunion-find木として表現する
uf_p = UnionFind(N)
uf_t = UnionFind(N)

# 道路の木
for _ in range(K):
    x,y = map(int, input().split())
    uf_p.union(px-1,py-1)

# 鉄道の木
for _ in range(L):
    x,y = map(int, input().split())
    uf_.tunion(px-1,py-1)


# 鉄道の木
for rx,ry in r:
    uf_t.union(rx-1,ry-1)

    
# 出力結果を整形
result = []
for i in range(N):
    # 道路と鉄道の両方繋がっている件数をand条件で抽出する
    result.append(str(len(set(uf_p.members(i)) & set(uf_t.members(i)))))

print(" ".join(result))

Submission status: Runtime Error

Solution code:
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)]

def find_root(root,x):
    y = root[x]
    if x == y:
        return x
    z = find_root(root,y)
    root[x] = z
    return z
 
def merge(root,size,x,y):
    x = find_root(root,x)
    y = find_root(root,y)
    if x == y:
        return
    sx,sy = size[x],size[y]
    if sx < sy:
        sx,sy = sy,sx
        x,y = y,x
    root[y] = x
    size[x] += sy
    
def UF_make(graph,n):
    Root=list(range(n+1))
    Size=[1] * (n+1)
    for i in range(len(graph)):
        merge(Root,Size,graph[i][0],graph[i][1])
    for i in range(n+1):
        Root[i] = find_root(Root,i)
    Root.pop(0)  #
    return Root

PQN=UF_make(PQ,N)
RSN=UF_make(RS,N)
PQRS=[[PQN[i]*10**6+RSN[i],i,0] for i in range(N)]
PQRS.sort()

p=0
while p<N:
    i=1
    c=0
    if p+i>=N-1:
        break
    while PQRS[p][0]==PQRS[p+i][0]:
        c+=1
        i+=1
    for j in range(p,p+i):
        PQRS[j][2]=c
    p+=i

PQRS.sort(key=lambda x:x[1])
for i in range(N):
    print(PQRS[i][2]+1,end=' ')

Submission status: Runtime Error

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

    # root検索
    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(self, x, y):
        return self.find(x) == self.find(y)


def solve():
    N, K, L = tuple(map(int, input().split()))

    PQ = []
    for _ in range(K):
        PQ.append(tuple(map(int, input().split())))
    RS = []
    for _ in range(L):
        RS.append(tuple(map(int, input().split())))

    # print(N, K, L)
    # print(PQ)
    # print(RS)

    road = UnionFind((K + 1) * 2)
    rail = UnionFind((L + 1) * 2)

    for a, b in PQ:
        road.union(a, b)

    for a, b in RS:
        rail.union(a, b)

    d = {}
    for i in range(N):
        i += 1
        road_root = road.find(i)
        rail_root = rail.find(i)
        if not (road_root, rail_root) in d:
            d[(road_root, rail_root)] = 1
        else:
            d[(road_root, rail_root)] += 1

    ans = []
    for i in range(N):
        i += 1
        road_root = road.find(i)
        rail_root = rail.find(i)
        ans.append(d[(road_root, rail_root)])

    return " ".join(tuple(map(str, ans)))


if __name__ == '__main__':
    res = solve()
    print(res)

Submission status: Runtime Error

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r,self.members(r)) for r in self.roots())
N,K,L = map(int,input().split())
uf = UnionFind(N)
ans = 0
for i in range(K):
    p,q = map(int,input().split())
    uf.union(p,q)
for i in range(L):
    r,s = map(int,input().split())
    if uf.same(r,s):
        ans += 1

Submission status: Runtime Error

Solution code:
import sys

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

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

    def union(self, x, y):
        x = self.par[x]
        y = self.par[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 isSame(self, x, y):
        return self.par[x] == self.par[y]

    def refresh(self):
        for p in range(N):
            self.find(p)

N, K, L = [int(x) for x in input().strip().split()]
road = UnionFind(N)
train = UnionFind(N)

for ｋ in range(K):
    p, q = [int(x) - 1 for x in input().strip().split()]
    road.union(p, q)
for l in range(L):
    r, s = [int(x) - 1 for x in input().strip().split()]
    train.union(r, s)

road.refresh()
train.refresh()

ans = [1] * N
for i in range(N - 1):
    for j in range(i + 1, N):
        if i == j:
            continue
        if road.par[i] == road.par[j] and train.par[i] == train.par[j]:
            ans[i] += 1
            ans[j] += 1

print(*ans)

Submission status: Runtime Error

Solution code:
import sys

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

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

    def union(self, x, y):
        x = self.par[x]
        y = self.par[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 isSame(self, x, y):
        return self.par[x] == self.par[y]

    def refresh(self):
        for p in range(N):
            self.find(p)

N, K, L = [int(x) for x in input().strip().split()]
road = UnionFind(N)
train = UnionFind(N)

for ｋ in range(K):
    p, q = [int(x) - 1 for x in input().strip().split()]
    road.union(p, q)
for l in range(L):
    r, s = [int(x) - 1 for x in input().strip().split()]
    train.union(r, s)

road.refresh()
train.refresh()

ans = [0] * N
for i in range(N):
    c = 1
    for j in range(N):
        if i == j:
            continue
        if road.par[i] == road.par[j] and train.par[i] == train.par[j]:
            c += 1
    ans[i] = c
print(*ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
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):
    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]

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

# 道路のUnionFind
uf1 = UnionFind(N)
for i in range(K):
    p, q = map(int, input().split())
    uf1.union(p - 1, q - 1)
 
# 鉄道のUnionFind
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 in range(N):
    c[(uf1.find(i), uf2.find(i))] += 1
ans = ""

# 回答を出力
for i in range(N):
    ans += str(c[(uf1.find(i), uf2.find(i))]) + " "
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
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):
    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]

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

# 道路のUnionFind
uf1 = UnionFind(N)
for i in range(K):
    p, q = map(int, input().split())
    uf1.union(p - 1, q - 1)
 
# 鉄道のUnionFind
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 in range(N):
    c[(uf1.find(i), uf2.find(i))] += 1
ans = ""
# 回答を出力
for i in range(N):
    ans += str(c[(uf1.find(i), uf2.find(i))]) + " "
print(ans)

Submission status: Runtime Error

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

road_par = []
road_rank = []
rail_par = []
rail_rank = []
c1 = []
c2 = []

def init(par, rank, c, n):
    for i in range(n):
        par.append(i)
        rank.append(0)
        c.append(0)


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


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


N, K, L = map(int, input().split())
init(road_par, road_rank, c1, N)
init(rail_par, rail_rank, c2, N)

for i in range(K):
    f, t = map(int, input().split())
    unite(road_par, road_rank, f-1, t-1)

for i in range(L):
    f,t = map(int, input().split())
    unite(rail_par, rail_rank, f-1, t-1)

for i in range(N):
    c1[find(road_par, i)] += 1
    c2[find(rail_par, i)] += 1

for i in range(N):
    if c1[i] == 1:
        road_par[i] = -1
    if c2[i] == 1:
        rail_par[i] = -1

ans = [0 for i in range(N)]
for i in range(N):
    if road_par[i] != -1:
        ans[i] +=1
    if rail_par[i] != -1:
        ans[i] += 1

for i in range(N):
    print(ans[i])

Submission status: Runtime Error

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

road_par = []
road_rank = []
rail_par = []
rail_rank = []
c1 = []
c2 = []

def init(par, rank, c, n):
    for i in range(n):
        par.append(i)
        rank.append(0)
        c.append(0)


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


def unite(par, rank, x, y):
    x = par[x]; y = par[y]
    if x == y:
        return
    if rank[x] < rank[y]:
        par[x] = y
    elif rank[y] < rank[x]:
        par[y] = x
    else:
        par[y] = x
        rank[x] += 1


def same(par, x, y):
    if find(par, x) == find(par, y):
        return True
    else:
        return False


N, K, L = map(int, input().split())
init(road_par, road_rank, c1, N)
init(rail_par, rail_rank, c2, N)

for i in range(K):
    f, t = map(int, input().split())
    unite(road_par, road_rank, f-1, t-1)

for i in range(L):
    f,t = map(int, input().split())
    unite(rail_par, rail_rank, f-1, t-1)

for i in range(N):
    c1[find(road_par, i)] += 1
    c2[find(rail_par, i)] += 1

for i in range(N):
    if c1[i] == 1:
        road_par[i] = -1
    if c2[i] == 1:
        rail_par[i] = -1

ans = [0 for i in range(N)]
for i in range(N):
    if road_par[i] != -1:
        ans[i] +=1
    if rail_par[i] != -1:
        ans[i] += 1

for i in range(N):
    print(ans[i])

Submission status: Runtime Error

Solution code:
road_par = []
road_rank = []
rail_par = []
rail_rank = []
c1 = []
c2 = []

def init(par, rank, c, n):
    for i in range(n):
        par.append(i)
        rank.append(0)
        c.append(0)


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


def unite(par, rank, x, y):
    x = par[x]; y = par[y]
    if x == y:
        return
    if rank[x] < rank[y]:
        par[x] = y
    elif rank[y] < rank[x]:
        par[y] = x
    else:
        par[y] = x
        rank[x] += 1


def same(par, x, y):
    if find(par, x) == find(par, y):
        return True
    else:
        return False


N, K, L = map(int, input().split())
init(road_par, road_rank, c1, N)
init(rail_par, rail_rank, c2, N)

for i in range(K):
    f, t = map(int, input().split())
    unite(road_par, road_rank, f-1, t-1)

for i in range(L):
    f,t = map(int, input().split())
    unite(rail_par, rail_rank, f-1, t-1)

for i in range(N):
    c1[find(road_par, i)] += 1
    c2[find(rail_par, i)] += 1

for i in range(N):
    if c1[i] == 1:
        road_par[i] = -1
    if c2[i] == 1:
        rail_par[i] = -1

ans = [0 for i in range(N)]
for i in range(N):
    if road_par[i] != -1:
        ans[i] +=1
    if rail_par[i] != -1:
        ans[i] += 1

for i in range(N):
    print(ans[i])

Submission status: Runtime Error

Solution code:
def change(after,index,li):
    before = li[index]
    for i in range(len(li)):
        if li[i]==before:
            li[i]=after


def main():
    n,k,l = map(int,input().split())
    road=[0 for _ in range(n)]
    train=[0 for _ in range(n)]
    r=t=1
    for _ in range(k):
        p,q = map(int,input().split())
        if road[p-1]==0 and road[q-1]==0:
            road[p-1]=road[q-1]=r
            r+=1
        elif road[p-1]!=0 and road[q-1]==0:
            change(r,p-1,road)
            road[q-1]=r
            r+=1
        elif road[p-1]==0 and road[q-1]!=0:
            change(r,q-1,road)
            road[p-1]=r
            r+=1
        else:
            change(r,p-1,*road)
            change(r,q-1,*road)
            r+=1
    for _ in range(l):
        p,q = map(int,input().split())
        if train[p-1]==0 and train[q-1]==0:
            train[p-1]=train[q-1]=t
            t+=1
        elif train[p-1]!=0 and train[q-1]==0:
            change(t,p-1,train)
            train[q-1]=t
            t+=1
        elif train[p-1]==0 and train[q-1]!=0:
            change(t,q-1,train)
            train[p-1]=t
            t+=1
        else:
            change(t,p-1,train)
            change(t,q-1,train)
            t+=1
    for i in range(n):
        ans=1
        for j in range(n):
            if i!=j and train[i]!=0 and train[i]==train[j] and road[i]!=0 and  road[i]==road[j]:
                ans+=1
        print(ans)
main()

Submission status: Runtime Error

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

root_road = list(range(N))
root_rail = list(range(N))
depth_road = [1 for _ in range(N)]
depth_rail = [1 for _ in range(N)]

def find(a,root):
    if root[a] == a:
        return a
    else:
        root[a] = find(root[a],root)
        return root[a]

def unite(a,b,root,depth):
    A = find(a,root)
    B = find(b,root)
    if A == B:
        return
    elif depth[A] > depth[B]:
        root[B] = A
        depth[A] += depth[B]
    else:
        root[A] = B
        depth[B] += depth[A]

for i in range(K):
    p,q = map(int,input().split())
    unite(p-1,q-1,root_road,depth_road)
for i in range(L):
    r,s = map(int,input().split())
    unite(r-1,s-1,root_rail,depth_rail)
d = defaultdict(int)
pairs = []
for i in range(N):
    road = find(i,root_road)
    rail = find(i,root_rail)
    pairs.append((road,rail))
    d[(road,rail)] += 1
for p in pairs:
    print(d[p],end = " ")

Submission status: Runtime Error

Solution code:
import sys
import collections as c
sys.setrecursionlimit(10**6)

import sys
sys.setrecursionlimit(10**7)

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

    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    def Unite(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if(x == y):
            return 
        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 isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    def Count(self, x):
        return -self.root[self.Find_Root(x)]

N, K, L = map(int,input().split())
p = []
q = []
l = []
r = []

for _ in range(K):
	p_tmp, q_tmp = map(int ,input().split())
	p.append(p_tmp)
	q.append(q_tmp)

for _ in range(L):
	l_tmp, r_tmp = map(int, input().split())
	l.append(l_tmp)
	r.append(r_tmp)

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

for i in range(K):
	road.uniteTree(p[i], q[i])

for i in range(L):
	train.uniteTree(l[i], r[i])

ar = []

for i in range(1,N+1):
	a = road.findRoot(i)
	b = train.findRoot(i)
	ar.append(str([a,b]))

Car = c.Counter(ar)

for i in range(N):
	print(Car[ar[i]], end = " ")

Submission status: Runtime Error

Solution code:
import sys
import collections as c
sys.setrecursionlimit(10**6)

class UnionFind():
	def __init__(self, n):
		self.size = n
		self.root = [-1 for _ in range(n+1)]
		self.rnk = [0 for _ in range(n+1)]

	def findRoot(self, a):
		if self.root[a] < 0:
			return a
		else:
			return self.findRoot(self.root[a])

	def uniteTree(self, a, b):
		a = self.findRoot(a)
		b = self.findRoot(b)

		if a == b:
			return

		elif self.rnk[a] > self.rnk[b]:
			self.root[a] += self.root[b]
			self.root[b] = a

		elif self.rnk[b] > self.rnk[a]:
			self.root[b] += self.root[a]
			self.root[a] = b

		elif self.rnk[a] == self.rnk[b]:
			self.root[b] += self.rnk[a]
			self.root[a] = b
			self.rnk[b] += 1

	def judgeTree(self, a, b):
		return self.findRoot(a) == self.findRoot(b)

	def count(self, a):
		return self.rnk[self.findRoot(a)] * (-1)

N, K, L = map(int,input().split())
p = []
q = []
l = []
r = []

for _ in range(K):
	p_tmp, q_tmp = map(int ,input().split())
	p.append(p_tmp)
	q.append(q_tmp)

for _ in range(L):
	l_tmp, r_tmp = map(int, input().split())
	l.append(l_tmp)
	r.append(r_tmp)

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

for i in range(K):
	road.uniteTree(p[i], q[i])

for i in range(L):
	train.uniteTree(l[i], r[i])

ar = []

for i in range(1,N+1):
	a = road.findRoot(i)
	b = train.findRoot(i)
	ar.append(str([a,b]))

Car = c.Counter(ar)

for i in range(N):
	print(Car[ar[i]], end = " ")