Problem:


Score : 400 points

Problem Statement

There are N cities. There are also K roads and L railways, extending between the cities.
The i-th road bidirectionally connects the p_i-th and q_i-th cities, and the i-th railway bidirectionally connects the r_i-th and s_i-th cities.
No two roads connect the same pair of cities. Similarly, no two railways connect the same pair of cities.

We will say city A and B are connected by roads if city B is reachable from city A by traversing some number of roads. Here, any city is considered to be connected to itself by roads.
We will also define connectivity by railways similarly.

For each city, find the number of the cities connected to that city by both roads and railways.

Constraints

2 ≦ N ≦ 2*10^5

1 ≦ K, L≦ 10^5

1 ≦ p_i, q_i, r_i, s_i ≦ N

p_i < q_i

r_i < s_i

When i ≠ j, (p_i, q_i) ≠ (p_j, q_j)

When i ≠ j, (r_i, s_i) ≠ (r_j, s_j)

Input

The input is given from Standard Input in the following format:

N K L
p_1 q_1
:
p_K q_K
r_1 s_1
:
r_L s_L

Output

Print N integers. The i-th of them should represent the number of the cities connected to the i-th city by both roads and railways.

Sample Input 1

4 3 1
1 2
2 3
3 4
2 3

Sample Output 1

1 2 2 1

All the four cities are connected to each other by roads.

By railways, only the second and third cities are connected. Thus, the answers for the cities are 1, 2, 2 and 1, respectively.

Sample Input 2

4 2 2
1 2
2 3
1 4
2 3

Sample Output 2

1 2 2 1

Sample Input 3

7 4 4
1 2
2 3
2 5
6 7
3 5
4 5
3 4
6 7

Sample Output 3

1 1 2 1 2 2 2



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


Sample output:
1 2 2 1

Submission status: Accepted

Solution code:
from collections import defaultdict


class UF:
    def __init__(self, _n):
        assert _n >= 0
        self._count = _n
        self._parent = list(range(_n))
        self._rank = [1] * _n

    def find(self, p):
        assert p >= 0 & p < len(self._parent)
        while p != self._parent[p]:
            self._parent[p] = self._parent[self._parent[p]]    # path compression by halving
            p = self._parent[p]
        return p

    def count(self):
        return self._count

    def connected(self, p, q):
        return self.find(p) == self.find(q)

    def union(self, p, q):
        root_p = self.find(p)
        root_q = self.find(q)
        if root_p == root_q:
            return
        
        if self._rank[root_p] < self._rank[root_q]:
            self._parent[root_p] = root_q
        elif self._rank[root_p] > self._rank[root_q]:
            self._parent[root_q] = root_p
        else:
            self._parent[root_q] = root_p
            self._rank[root_p] += 1
        self._count -= 1


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

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

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

d = defaultdict(int)
for i in range(n):
    d[uf_road.find(i), uf_rail.find(i)] += 1
#print(d)
#print(' '.join(str(d[(uf_road.find(i), uf_rail.find(i))]) for i in range(n)))
print(*(d[uf_road.find(i), uf_rail.find(i)] for i in range(n)))

Submission status: Accepted

Solution code:
#http://www.geocities.jp/m_hiroi/light/pyalgo61.html
class UF(object):
    def __init__(self, n):
        self.table = [None for i in range(n)]
    def find(self, x):
        if self.table[x] is None:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]
    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            self.table[s2] = s1

n, k, l = [int(x) for x in raw_input().split()]
d = UF(n)
t = UF(n)
for i in range(k):
    p, q = [int(x) - 1 for x in raw_input().split()]
    d.union(p, q)
for i in range(l):
    r, s = [int(x) - 1 for x in raw_input().split()]
    t.union(r, s)
res = {}
for i in range(n):
    key = (d.find(i), t.find(i))
    res[key] = res.get(key, 0) + 1
for i in range(n):
    print res[(d.find(i), t.find(i))],

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

from collections import defaultdict


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


def union(parent, rank, x, y):
    x = find(parent, x)
    y = find(parent, y)
    if x == y:
        return
    if rank[x] < rank[y]:
        parent[x] = y
    elif rank[x] > rank[y]:
        parent[y] = x
    else:
        parent[y] = x
        rank[x] += 1


def main():
    n, k, l = [int(i) for i in raw_input().split()]
    road_parent = range(n)
    road_rank = [0 for _ in xrange(n)]
    train_parent = range(n)
    train_rank = [0 for _ in xrange(n)]

    for i in range(k):
        p, q = [int(i)-1 for i in raw_input().split()]
        union(road_parent, road_rank, p, q)
    for i in range(l):
        r, s = [int(i)-1 for i in raw_input().split()]
        union(train_parent, road_rank, r, s)
    counter = defaultdict(int)
    for i in range(n):
        counter[(find(road_parent, i), find(train_parent, i))] += 1
    ans_list = [counter[(find(road_parent, i), find(train_parent, i))] for i in xrange(n)]
    print ' '.join(map(str, ans_list))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

from collections import defaultdict
def find(x, parent):
    if parent[x] == x:
        return x
    else:
        parent[x] = find(parent[x], parent)
        return parent[x]


def union(x, y, parent):
    x = find(x, parent)
    y = find(y, parent)
    if x == y:
        return
    parent[y] = x


def main():
    n, k, l = [int(i) for i in raw_input().split()]
    road_parent = range(n)
    train_parent = range(n)

    for i in range(k):
        p, q = [int(i)-1 for i in raw_input().split()]
        union(p, q, road_parent)
    for i in range(l):
        r, s = [int(i)-1 for i in raw_input().split()]
        union(r, s, train_parent)
    counter = defaultdict(int)
    for i in range(n):
        counter[(find(i, road_parent), find(i, train_parent))] += 1
    ans_list = [counter[(find(i, road_parent), find(i, train_parent))] for i in xrange(n)]
    print ' '.join(map(str, ans_list))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

par = [i for i in range(N)]
size = [1] * N


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

def unite(x, y):
    root_x = find(x, par)
    root_y = find(y, par)
    if root_y > root_x:
        par[root_x] = root_y
    else:
        par[root_y] = root_x

par2 = [i for i in range(N)]
def unite2(x, y):

    x = find(x, par2)
    y = find(y, par2)

    if x != y:
        # xとyの属している集合が異なる時
        par2[x] = y
        s = size[x] + size[y]
        size[y] = s

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

    unite(p-1, q-1)


#print(par)

root =[find(i, par) for i in range(N)]

#print(root)

#find(0,par)

#print(par)

for _ in range(L):
    p, q = map(int, input().split())
    s = root[p-1]
    t = root[q-1]
    if s == t:
        unite2(p-1, q-1)

#print(par2)

for i in range(N-1):
    p = find(i, par2)
    print(size[p], end=' ')
print(size[find(N-1, par2)])

Submission status: Runtime Error

Solution code:
from collections import Counter

n,k,l=map(int,input().split())
city1=[i for i in range(n)]
city2=[i for i in range(n)]

def root(c,x):
  if x==c[x]:
    return x
  else:
    return root(c,c[x])

def union(c,x,y):
  rx=root(c,x)
  ry=root(c,y)
  c[rx]=ry

for i in range(k):
  a,b=map(int,input().split())
  union(city1,a-1,b-1)
for i in range(l):
  a,b=map(int,input().split())
  union(city2,a-1,b-1)
r=[]
for i in range(n):
  r.append((root(city1,i),root(city2,i)))
c=Counter(r)
for i in range(n):
  ans=c[r[i]]
  if i==n-1:
    print(ans)
  else:
    print(ans,end=' ')

Submission status: Runtime Error

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

par = [i for i in range(N)]
size = [1] * N


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

def unite(x, y):
    root_x = find(x, par)
    root_y = find(y, par)
    par[root_x] = root_y

par2 = [i for i in range(N)]
def unite2(x, y):

    x = find(x, par2)
    y = find(y, par2)

    if x != y:
        # xとyの属している集合が異なる時
        par2[x] = y
        s = size[x] + size[y]
        size[y] = s

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

    unite(p-1, q-1)

Submission status: Runtime Error

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

par = [i for i in range(N)]
size = [1] * N


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

def unite(x, y):
    root_x = find(x, par)
    root_y = find(y, par)

    if root_x != root_y:
        # xとyの属している集合が異なる時
        pass
        par[root_x] = root_y

par2 = [i for i in range(N)]
def unite2(x, y):

    x = find(x, par2)
    y = find(y, par2)

    if x != y:
        # xとyの属している集合が異なる時
        par2[x] = y
        s = size[x] + size[y]
        size[y] = s

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

    unite(p-1, q-1)

Submission status: Runtime Error

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

par = [i for i in range(N)]
size = [1] * N


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

def unite(x, y):
    x = find(x, par)
    y = find(y, par)

    if x != y:
        # xとyの属している集合が異なる時
        pass
        par[x] = y

par2 = [i for i in range(N)]
def unite2(x, y):

    x = find(x, par2)
    y = find(y, par2)

    if x != y:
        # xとyの属している集合が異なる時
        par2[x] = y
        s = size[x] + size[y]
        size[y] = s

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

    unite(p-1, q-1)

Submission status: Runtime Error

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

par = [i for i in range(N)]
size = [1] * N


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

def unite(x, y):
    x = find(x, par)
    y = find(y, par)

    if x != y:
        # xとyの属している集合が異なる時
        par[x] = y

par2 = [i for i in range(N)]
def unite2(x, y):

    x = find(x, par2)
    y = find(y, par2)

    if x != y:
        # xとyの属している集合が異なる時
        par2[x] = y
        s = size[x] + size[y]
        size[y] = s

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

Submission status: Runtime Error

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

par = [i for i in range(N)]
size = [1] * N


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

def unite(x, y):
    x = find(x, par)
    y = find(y, par)

    if x != y:
        # xとyの属している集合が異なる時
        par[x] = y

par2 = [i for i in range(N)]
def unite2(x, y):

    x = find(x, par2)
    y = find(y, par2)

    if x != y:
        # xとyの属している集合が異なる時
        par2[x] = y
        s = size[x] + size[y]
        size[y] = s

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

Submission status: Runtime Error

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

par = [i for i in range(N)]
size = [1] * N


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

def unite(x, y):
    x = find(x, par)
    y = find(y, par)

    if x != y:
        # xとyの属している集合が異なる時
        par[x] = y

par2 = [i for i in range(N)]
def unite2(x, y):

    x = find(x, par2)
    y = find(y, par2)

    if x != y:
        # xとyの属している集合が異なる時
        par2[x] = y
        s = size[x] + size[y]
        size[y] = s

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


#print(par)

root =[find(i, par) for i in range(N)]

Submission status: Runtime Error

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

par = [i for i in range(N)]
size = [1] * N


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

def unite(x, y):
    x = find(x, par)
    y = find(y, par)

    if x != y:
        # xとyの属している集合が異なる時
        par[x] = y


par2 = [i for i in range(N)]



def unite2(x, y):

    x = find(x, par2)
    y = find(y, par2)

    if x != y:
        # xとyの属している集合が異なる時
        par2[x] = y
        s = size[x] + size[y]
        size[y] = s

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


#print(par)

root =[find(i, par) for i in range(N)]

#print(root)

#find(0,par)

#print(par)

for _ in range(L):
    p, q = map(int, input().split())
    s = root[p-1]
    t = root[q-1]
    if s == t:
        unite2(p-1, q-1)

#print(par2)

for i in range(N-1):
    p = find(i, par2)
    print(size[p], end=' ')
print(size[find(N-1, par2)])

Submission status: Runtime Error

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

par = [i for i in range(N)]
size = [1] * N


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

def unite(x, y):
    x = find(x, par)
    y = find(y, par)

    if x != y:
        # xとyの属している集合が異なる時
        par[x] = y


par2 = [i for i in range(N)]

def unite2(x: object, y: object) -> object:

    x = find(x, par2)
    y = find(y, par2)

    if x != y:
        # xとyの属している集合が異なる時
        par2[x] = y
        s = size[x] + size[y]
        size[y] = s

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

for _ in range(L):
    p, q = map(int, input().split())
    s = find(p-1, par)
    t = find(q-1, par)
    if s==t:
        unite2(p-1, q-1)

for i in range(N-1):
    p = find(i, par2)
    print(size[p], end=' ')
print(size[find(N-1, par2)])

Submission status: Runtime Error

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

par = [i for i in range(N)]
size = [1] * N
rank = [1] * N

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

def unite(x, y):
    x = find(x, par)
    y = find(y, par)

    if x != y:
        # xとyの属している集合が異なる時
        par[x] = y


par2 = [i for i in range(N)]

def unite2(x, y):

    x = find(x, par2)
    y = find(y, par2)

    if x != y:
        # xとyの属している集合が異なる時
        par2[x] = y
        s = size[x] + size[y]
        size[y] = s

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

for _ in range(L):
    p, q = map(int, input().split())
    s = find(p-1, par)
    t = find(q-1, par)
    if s==t:
        unite2(p-1, q-1)

for i in range(N):
    p = find(i, par2)
    print(size[p], end=' ')

Submission status: Runtime Error

Solution code:
N, K, L = map(int, input().split())
#Parent List(PL)
road = [i for i in range(N)]
rail = [i for i in range(N)]

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

for i in range(K+L):
    PL = (lambda x:road if x < K else rail)(i)
    p, q = map(lambda x:int(x)-1, input().split())
    p, q = fp(p,PL), fp(q,PL)
    PL[p] = PL[q] = min(p, q)

from collections import defaultdict as dd
Wconnected = dd(lambda:0)
for i in range(N):
    Wconnected[fp(i,road),fp(i,rail)] += 1
print(*[Wconnected[fp(i,road),fp(i,rail)] for i in range(N)])

Submission status: Runtime Error

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

roads_dic = dict()
railways_dic = dict()
for i in range(n):  
    if roads[i] == i:
        roads_dic[i] = {i}
    else:
        roads_dic[roads[i]].add(i)
    if railways[i] == i:
        railways_dic[i] = {i}
    else:
        railways_dic[railways[i]].add(i)

ans = [len(roads_dic[roads[i]] & railways_dic[railways[i]]) for i in range(n)]
print(" ".join(map(str, ans)))

Submission status: Runtime Error

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

roads_dic = dict()
railways_dic = dict()
for i in range(n):  
    if roads[i] == i:
        roads_dic[i] = {i}
    else:
        roads_dic[roads[i]].add(i)
    if railways[i] == i:
        railways_dic[i] = {i}
    else:
        railways_dic[railways[i]].add(i)

ans = [len(roads_dic[roads[i]] & railways_dic[railways[i]]) for i in range(n)]
print(" ".join(map(str, ans)))

Submission status: Runtime Error

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

roads_dic = dict()
railways_dic = dict()
for i in range(n):  
    if roads[i] == i and not i in roads_dic:
        roads_dic[i] = {i}
    elif not roads[roads[i]] in roads_dic:
        roads_dic[roads[roads[i]]] = {i, roads[i]}
    else:
        roads_dic[roads[i]].add(i)

    if railways[i] == i and not i in railways_dic:
        railways_dic[i] = {i}
    elif not railways[railways[i]] in railways_dic:
        railways_dic[railways[railways[i]]] = {i, railways[i]}
    else:
        railways_dic[railways[i]].add(i)

ans = [len(roads_dic[roads[i]] & railways_dic[railways[i]]) for i in range(n)]
print(" ".join(map(str, ans)))

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
input = sys.stdin.readline

def main():
  n, k, l = map(int, input().split())
  road_matrix = np.identity(n, dtype='bool')
  train_matrix = np.identity(n, dtype='bool')

  for _ in range(k):
    p, q = map(int, input().split())
    p, q = p-1, q-1
    road_matrix[p][q] = 1
    road_matrix[q][p] = 1
    
  for _ in range(l):
    r, s = map(int, input().split())
    r, s = r-1, s-1
    train_matrix[r][s] = 1
    train_matrix[s][r] = 1
  
  r = search(road_matrix)
  t = search(train_matrix)
  
  cnt_arr = np.sum(r & t, axis=1)
  print(' '.join(map(str,cnt_arr)))


def search(matrix):
  result = np.copy(matrix)
  while True:
    tmp = np.dot(result, matrix)
    if (tmp == result).all:
      result = tmp
      break
    result = tmp

  return result


if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;

long set_index;

void dfs(Graph graph, vector<bool>& seen, vector<int>& set, int v){
    seen[v] = true;
    set[v] = set_index;
    for (auto next_v : graph[v]){
        if (seen[next_v]) continue;
        dfs(graph, seen, set, next_v);
    }
}

void input(Graph& graph, int M){
    int p, q;
    for (int i=0; i<M; i++){
        cin >> p >> q;
        graph[p-1].push_back(q-1);
        graph[q-1].push_back(p-1);
    }
}

void connect(Graph& graph, vector<bool>& seen, vector<int>& set, int n){
    set_index = 0;
    for (int v=0; v<n; v++){
        if (seen[v]) continue;
        dfs(graph, seen, set, v);
        set_index++;
    }
}

int main(){
    int N, K, L;
    cin >> N >> K >> L;
    Graph road, rail;
    vector<bool> seen_road, seen_rail;
    vector<int> set_road, set_rail;
    road.resize(N);
    rail.resize(N);
    set_road.assign(N, 0);
    set_rail.assign(N, 0);
    input(road, K);
    input(rail, L);

    seen_road.assign(N, false);
    connect(road, seen_road, set_road, N);
    seen_rail.assign(N, false);
    connect(rail, seen_rail, set_rail, N);
   
    map<pair<long, long>, int> ans;
    for (int i=0; i<N; i++){
        ans[make_pair(set_road[i],set_rail[i])]++;
    }
    for (int i=0; i<N; i++){
        cout << ans[make_pair(set_road[i],set_rail[i])] << " ";
    }
    return 0;
}

Submission status: Runtime Error

Solution code:
N, K, L = map(int, input().split())
road = [{"Connected":[],"seen":False,"set":0} for _ in range(N)]
rail = [{"Connected":[],"seen":False,"set":0} for _ in range(N)]

def dfs(graph, v, index): #深さ優先探索
    graph[v]["seen"] = True
    graph[v]["set"] = index
    for next_v in graph[v]["Connected"]:
        if graph[next_v]["seen"]:
            continue
        dfs(graph, next_v, index)

for X in ((road, K), (rail, L)): #結合を入力
    for _ in range(X[1]):
        p, q = map(int, input().split())
        X[0][p-1]["Connected"].append(q-1)
        X[0][q-1]["Connected"].append(p-1)

for X in (road, rail): #探索して連結成分に分解
    set_index = 0
    for v in range(N):
        if X[v]["seen"]:
            continue
        dfs(X, v, set_index)
        set_index += 1
        
List = [(road[i]["set"],rail[i]["set"]) for i in range(N)]
D = {}
for X in List:
    if not X in D:
        D[X] = 1
    else:
        D[X] += 1
for A in List:
    print(D[A],end=" ")

Submission status: Runtime Error

Solution code:
import collections
N, K, L = map(int, input().split())
road = [{"Connected":[],"seen":False,"set":0} for _ in range(200000)]
rail = [{"Connected":[],"seen":False,"set":0} for _ in range(200000)]

def dfs(graph, v, index): #深さ優先探索
    graph[v]["seen"] = True
    graph[v]["set"] = index
    for next_v in graph[v]["Connected"]:
        if graph[next_v]["seen"]:
            continue
        dfs(graph, next_v, index)

for X in ((road, K), (rail, L)): #結合を入力
    for _ in range(X[1]):
        p, q = map(int, input().split())
        X[0][p-1]["Connected"].append(q-1)
        X[0][q-1]["Connected"].append(p-1)

for X in (road, rail): #探索して連結成分に分解
    set_index = 0
    for v in range(N):
        if X[v]["seen"]:
            continue
        dfs(X, v, set_index)
        set_index += 1
        
List = [(road[i]["set"],rail[i]["set"]) for i in range(N)]
count = collections.Counter(List)
for A in List:
    print(count[A],end=" ")

Submission status: Runtime Error

Solution code:
import collections
N, K, L = map(int, input().split())
road = [{"Connected":[],"seen":False,"set":0} for _ in range(N)]
rail = [{"Connected":[],"seen":False,"set":0} for _ in range(N)]

def dfs(graph, v, index): #深さ優先探索
    graph[v]["seen"] = True
    graph[v]["set"] = index
    for next_v in graph[v]["Connected"]:
        if graph[next_v]["seen"]:
            continue
        dfs(graph, next_v, index)

for X in ((road, K), (rail, L)): #結合を入力
    for _ in range(X[1]):
        p, q = map(int, input().split())
        X[0][p-1]["Connected"].append(q-1)
        X[0][q-1]["Connected"].append(p-1)

for X in (road, rail): #探索して連結成分に分解
    set_index = 0
    for v in range(N):
        if X[v]["seen"]:
            continue
        dfs(X, v, set_index)
        set_index += 1
    del set_index
        
List = [(road[i]["set"],rail[i]["set"]) for i in range(N)]
count = collections.Counter(List)
for A in List:
    print(count[A],end=" ")

Submission status: Runtime Error

Solution code:
import collections
N, K, L = map(int, input().split())
road = [{"Connected":[],"seen":False,"set":-1} for _ in range(N)]
rail = [{"Connected":[],"seen":False,"set":-1} for _ in range(N)]

def dfs(graph, v, index): #深さ優先探索
    graph[v]["seen"] = True
    graph[v]["set"] = index
    for next_v in graph[v]["Connected"]:
        if graph[next_v]["seen"]:
            continue
        dfs(graph, next_v, index)

for X in ((road, K), (rail, L)): #結合を入力
    for _ in range(X[1]):
        p, q = map(int, input().split())
        X[0][p-1]["Connected"].append(q-1)
        X[0][q-1]["Connected"].append(p-1)

for X in (road, rail): #探索して連結成分に分解
    set_index = 0
    for v in range(N):
        if X[v]["seen"]:
            continue
        dfs(X, v, set_index)
        set_index += 1
        
List = [(road[i]["set"],rail[i]["set"]) for i in range(N)]
count = collections.Counter(List)
for A in List:
    print(count[A],end=" ")

Submission status: Runtime Error

Solution code:
import collections
N, K, L = map(int, input().split())
road = [{"Connected":[],"seen":False} for _ in range(N)]
rail = [{"Connected":[],"seen":False} for _ in range(N)]

def dfs(graph, v, index): #深さ優先探索
    graph[v]["seen"] = True
    graph[v]["set"] = index
    for next_v in graph[v]["Connected"]:
        if graph[next_v]["seen"]:
            continue
        dfs(graph, next_v, index)

for X in ((road, K), (rail, L)): #結合を入力
    for _ in range(X[1]):
        p, q = map(int, input().split())
        X[0][p-1]["Connected"].append(q-1)
        X[0][q-1]["Connected"].append(p-1)

for X in (road, rail): #探索して連結成分に分解
    set_index = 0
    for v in range(N):
        if X[v]["seen"]:
            continue
        dfs(X, v, set_index)
        set_index += 1
        
List = [(road[i]["set"],rail[i]["set"]) for i in range(N)]
count = collections.Counter(List)
for A in List:
    print(count[A],end=" ")

Submission status: Runtime Error

Solution code:
import collections
N, K, L = map(int, input().split())
road = [{"Connected":[],"set":0,"seen":False} for _ in range(N)]
rail = [{"Connected":[],"set":0,"seen":False} for _ in range(N)]

def dfs(graph, v, num): #深さ優先探索
    graph[v]["seen"] = True
    graph[v]["set"] = num
    for next_v in set(graph[v]["Connected"]):
        if graph[next_v]["seen"]:
            continue
        dfs(graph, next_v, num)

for X in ((road, K), (rail, L)): #結合を入力
    for _ in range(X[1]):
        p, q = map(int, input().split())
        X[0][p-1]["Connected"].append(q-1)
        X[0][q-1]["Connected"].append(p-1)

for X in [road, rail]: #探索して連結成分に分解
    set_index = 0
    for v in range(N):
        if X[v]["seen"]:
            continue
        dfs(X, v, set_index)
        set_index += 1
        

List = [(road[i]["set"],rail[i]["set"]) for i in range(N)]
counter = collections.Counter(List)
for A in List:
    print(counter[A],end=" ")

Submission status: Runtime Error

Solution code:
import collections
N, K, L = map(int, input().split())
road = [{"Connected":[],"set":0,"seen":False} for _ in range(N+1)]
rail = [{"Connected":[],"set":0,"seen":False} for _ in range(N+1)]

def dfs(graph, v, num): #深さ優先探索
    graph[v]["seen"] = True
    graph[v]["set"] = num
    for next_v in graph[v]["Connected"]:
        if graph[next_v]["seen"]:
            continue
        dfs(graph, next_v, num)

for X in ((road, K), (rail, L)): #結合を入力
    for i in range(X[1]):
        p, q = map(int, input().split())
        X[0][p]["Connected"].append(q)
        X[0][q]["Connected"].append(p)

for X in [road, rail]: #探索して連結成分に分解
    set_index = 0
    for v in range(N):
        if X[v+1]["seen"]:
            continue
        set_index += 1
        dfs(X, v+1, set_index)
        

List = [(road[i+1]["set"],rail[i+1]["set"]) for i in range(N)]
counter = collections.Counter(List)
for A in List:
    print(counter[A],end=" ")

Submission status: Runtime Error

Solution code:
import collections
N, K, L = map(int, input().split())
road = [{"Connected":[],"set":0,"seen":False} for _ in range(N)]
rail = [{"Connected":[],"set":0,"seen":False} for _ in range(N)]

def dfs(graph, v, num): #深さ優先探索
    graph[v]["seen"] = True
    graph[v]["set"] = num
    for next_v in graph[v]["Connected"]:
        if graph[next_v]["seen"]:
            continue
        dfs(graph, next_v, num)

for X in ((road, K), (rail, L)): #結合を入力
    for i in range(X[1]):
        p, q = map(int, input().split())
        X[0][p-1]["Connected"].append(q-1)
        X[0][q-1]["Connected"].append(p-1)

for X in [road, rail]: #探索して連結成分に分解
    set_index = 0
    for v in range(N):
        if X[v]["seen"]:
            continue
        set_index += 1
        dfs(X, v, set_index)
        

List = [(road[i]["set"],rail[i]["set"]) for i in range(N)]
counter = collections.Counter(List)
for A in List:
    print(counter[A],end=" ")

Submission status: Runtime Error

Solution code:
import collections
N, K, L = map(int, input().split())
road = [{"Connected":[],"set":0,"seen":False} for _ in range(N)]
rail = [{"Connected":[],"set":0,"seen":False} for _ in range(N)]

def dfs(node, num): #深さ優先探索
    node["seen"] = True
    node["set"] = num
    for next_node in node["Connected"]:
        if next_node["seen"]:
            continue
        dfs(next_node, num)

for X in ((road, K), (rail, L)): #結合を入力
    for i in range(X[1]):
        p, q = map(int, input().split())
        X[0][p-1]["Connected"].append(X[0][q-1])
        X[0][q-1]["Connected"].append(X[0][p-1])

for X in [road, rail]: #探索して連結成分に分解
    set_index = 0
    for x in X:
        if x["seen"]:
            continue
        dfs(x, set_index)
        set_index += 1

List = [(road[i]["set"],rail[i]["set"]) for i in range(N)]
counter = collections.Counter(List)
for A in List:
    print(counter[A],end=" ")

Submission status: Runtime Error

Solution code:
import collections
N, K, L = map(int, input().split())
road = [{"Connected":[],"set":-1,"seen":False} for i in range(N)]
rail = [{"Connected":[],"set":-1,"seen":False} for i in range(N)]

def dfs(node, num): #深さ優先探索
    node["seen"] = True
    node["set"] = num
    for next_node in node["Connected"]:
        if next_node["seen"]:
            continue
        dfs(next_node, num)

for X in ((road, K), (rail, L)): #結合を入力
    for i in range(X[1]):
        p, q = map(int, input().split())
        X[0][p-1]["Connected"].append(X[0][q-1])
        X[0][q-1]["Connected"].append(X[0][p-1])

for X in [road, rail]: #探索して連結成分に分解
    set_index = 0
    for x in X:
        if x["seen"]:
            continue
        dfs(x, set_index)
        set_index += 1
        
List = [(road[i]["set"],rail[i]["set"]) for i in range(N)]
counter = collections.Counter(List)
for A in List:
    print(counter[A],end=" ")

Submission status: Runtime Error

Solution code:
import collections
N, K, L = map(int, input().split())
road = [{"Connected":[],"set":-1,"seen":False} for i in range(N)]
rail = [{"Connected":[],"set":-1,"seen":False} for i in range(N)]

def dfs(node, num): #深さ優先探索
    node["seen"] = True
    node["set"] = num
    for next_node in node["Connected"]:
        if next_node["seen"]:
            continue
        dfs(next_node, num)

for i in range(K):
    p, q = map(int, input().split())
    road[p-1]["Connected"].append(road[q-1])
    road[q-1]["Connected"].append(road[p-1])
for i in range(L):
    r, s = map(int, input().split())
    rail[r-1]["Connected"].append(rail[s-1])
    rail[s-1]["Connected"].append(rail[r-1])
for X in [road, rail]: #連結成分に分解
    set_index = 0
    for x in X:
        if x["seen"]:
            continue
        dfs(x, set_index)
        set_index += 1
List = [(road[i]["set"],rail[i]["set"]) for i in range(N)]
counter = collections.Counter(List)
for A in List:
    print(counter[A],end=" ")