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
input = sys.stdin.readline

class Unionfind:

    __slots__ = ['nodes','size']

    def __init__(self, n):
        self.nodes = list(range(n))
        self.size = [1]*n

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

    def unite(self, x, y):
        x = self.root(x); y = self.root(y)
        if x == y:
            return
        if self.size[x] < self.size[y]:
            x, y = y, x
        self.size[x] += self.size[y]
        self.nodes[y] = x

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

N,K,L = map(int,input().split())
road = [[int(e)-1 for e in input().split()] for _ in range(K)]
rail = [[int(e)-1 for e in input().split()] for _ in range(L)]

uf1 = Unionfind(N)
uf2 = Unionfind(N)

for p,q in road:
    uf1.unite(p,q)

for r,s in rail:
    uf2.unite(r,s)

set1 = [0]*N
set2 = [0]*N

for node in range(N):
    if node == uf1.root(node):
        set1[node] = set()
    set1[node] = set1[uf1.root(node)]
    set1[node].add(node)
    if node == uf2.root(node):
        set2[node] = set()
    set2[node] = set2[uf2.root(node)]
    set2[node].add(node)

ans = []

for node in range(N):
    ans.append(str(len(set1[node] & set2[node])))

print(" ".join(ans))

Submission status: Runtime Error

Solution code:
def root(x,d):
    if d[x]!=x:
        d[x]=root(x,d)
    return d[x]
def unite(x,y,h):
    x=root(x,h)
    y=root(y,h)
    if x!=y:
        h[x]=min(x,y)
        h[y]=h[x]
from collections import defaultdict
n,k,l=map(int,input().split())
a=[i for i in range(n+1)]
b=[i for i in range(n+1)]
for i in range(k):
    s,t=map(int,input().split())
    unite(s,t,a)
for i in range(l):
    s,t=map(int,input().split())
    unite(s,t,b)
d=defaultdict(int)
l=""
for i in range(1,n+1):
    d[(root(a[i],a),root(b[i],b))]+=1
for i in range(1,n+1):
    l+=str(d[(root(a[i],a),root(b[i],b))])+" "
print(l[:-1])

Submission status: Runtime Error

Solution code:
from collections import defaultdict
n,k,l = map(int, input().split())


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size = [1] * 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:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
            self.size[x] = 0
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # すべての頂点に対して親を検索する
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)


D = defaultdict(int)

uf = UnionFind()
tf = UnionFind()
n,k,l =  map(int, input().split())
dp =[1]*n
for i in range(k):
    x,y =map(int, input().split())
    uf.unite(x-1, y-1)  # (3)
for i in range(l):
    x,y =map(int, input().split())
    tf.unite(x-1, y-1)  # (3)
tf.all_find()
uf.all_find()
D = defaultdict(int)
for r, t in zip(uf.par, tf.par):
    D[(r, t)] += 1
 
ans = [D[(r, t)] for r, t in zip(uf.par, tf.par)]
print(*ans, sep=' ')

Submission status: Runtime Error

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


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size = [1] * 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:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
            self.size[x] = 0
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # すべての頂点に対して親を検索する
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)


D = defaultdict(int)

uf = UnionFind()
tf = UnionFind()
n,k,l =  map(int, input().split())
dp =[1]*n
for i in range(k):
    x,y =map(int, input().split())
    uf.unite(x-1, y-1)  # (3)
for i in range(l):
    x,y =map(int, input().split())
    tf.unite(x-1, y-1)  # (3)
tf.all_find()
uf.all_find()
D = defaultdict(int)
for r, t in zip(uf.par, tf.par):
    D[(r, t)] += 1
 
ans = [D[(r, t)] for r, t in zip(uf.par, tf.par)]
print(*ans, sep=' ')

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

"""
参考：https://img.atcoder.jp/arc065/editorial.pdf
・Union-Find木
"""

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

from collections import Counter

# Union-Find木
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        # 1-indexedのままでOK、その場合は[0]は未使用
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0）
        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
            # 木の高さが同じなら片方を1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

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

# (道路グループ番号, 鉄道グループ番号) のペアを各都市について作る
pairs = [None] * N
for i in range(N):
    pairs[i] = (uf1.find[i+1], uf2.find[i+1])

# 同じ内容のペアについて数える
c = Counter(pairs)

ans = [0] * N
for i in range(N):
    # 自分のペアのカウント数を各都市について取得
    ans[i] = c[pairs[i]]
print(*ans)

Submission status: Runtime Error

Solution code:
import copy
N, M = [int(_) for _ in input().split()]
AB = [[int(_) - 1 for _ in input().split()] for _ in range(M)]

G = [set() for _ in range(N)]
a = set()
for ab in AB:
    G[ab[0]].add(ab[1])


def find(a, x):
    stack = []
    while a[x] != x:
        stack += [x]
        x = a[x]
    while stack:
        a[stack.pop()] = x
    return x


def unite(a, x, y):
    x = find(a, x)
    y = find(a, y)
    a[x] = a[y] = min(x, y)


ans = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        if j in G[i]:
            Gn = copy.deepcopy(G)
            Gn[i].discard(j)
            a = [i for i in range(N)]
            for k in range(N - 1):
                for l in Gn[k]:
                    unite(a, k, l)
            par = set()
            for k in range(N):
                par.add(find(a, k))
            if len(par) > 1:
                ans += 1
print(ans)

Submission status: Runtime Error

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


def find(a, x):
    stack = []
    while a[x] != x:
        x = a[x]
        stack += [x]
    while stack:
        a[stack.pop()] = x
    return x


def unite(a, x, y):
    x = find(a, x)
    y = find(a, y)
    a[x] = a[y] = min(x, y)


a_road = [i for i in range(N)]
for _ in range(K):
    p, q = [int(_) - 1 for _ in input().split()]
    unite(a_road, p, q)
a_railway = [i for i in range(N)]
for _ in range(L):
    r, s = [int(_) - 1 for _ in input().split()]
    unite(a_railway, r, s)
memo = {}
for i in range(N):
    memo[a_road[i], a_railway[i]] = memo.get(
        (find(a_road, i), find(a_railway, i)), 0) + 1

print(' '.join(str(memo[a_road[i], a_railway[i]]) for i in range(N)))

Submission status: Runtime Error

Solution code:

import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def bfs(N, path, res):
    is_visited = [False for i in range(N + 1)]
    for i in range(1, N + 1):
        if is_visited[i] == True:
            continue
        que = deque([i])
        res[i] = set([i])
        while 1:
            if len(que) <= 0:
                break

            p = que.popleft()
            is_visited[p] = True

            for q in path[p]:
                if is_visited[q] == False:
                    is_visited[q] = True
                    res[i].add(q)
                    #res[q] = res[i]
                    que.append(q)



def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, K, L] = [int(input_raw[0]), int(input_raw[1]), int(input_raw[2])]
    road = {}
    train = {}
    for i in range(1, N + 1):
        road[i] = []
        train[i] = []

    for i in range(K):
        input_raw = read_func().strip().split()
        [p, q] = [int(input_raw[0]), int(input_raw[1])]
        road[p].append(q)
        road[q].append(p)
    res_road = {}
    bfs(N, road, res_road)

    for i in range(L):
        input_raw = read_func().strip().split()
        [p, q] = [int(input_raw[0]), int(input_raw[1])]
        train[p].append(q)
        train[q].append(p)

    res_train = {}
    bfs(N, train, res_train)

    for i in range(1, N + 1):
        print len(res_road[i] & res_train[i]),




if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np

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

#print(N,K,L,D,T)

array_D = np.eye(N,N,dtype=int)
array_T = np.eye(N,N,dtype=int)
root_D = [i for i in range(N)]
root_T = [i for i in range(N)]

for _ in range(K):
    d0, d1 = map(int, input().split())
    d0 = d0 - 1
    d1 = d1 - 1
    r0 = root_D[d0]
    r1 = root_D[d1]
    array_D[r0] = array_D[r0] | array_D[r1]
    root_D[r1] = r0
    root_D[d1] = r0
    #print(list_D, root_D)

for _ in range(L):
    t0, t1 = map(int, input().split())
    t0 = t0 - 1
    t1 = t1 - 1
    r0 = root_T[t0]
    r1 = root_T[t1]
    array_T[r0] = array_T[r0] | array_T[r1]
    root_T[r1] = r0
    root_T[t1] = r0
    #print(list_T, root_T)

#和集合
res = [0] * N
for i in range(N):
    rd = root_D[i]
    rt = root_T[i]
    d = array_D[rd]
    t = array_T[rt]
    res[i] = sum(d & t)
#print(*(res[i] for i in range(N)))
print(" ".join([str(i) for i in res]))

Submission status: Runtime Error

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

#print(N,K,L,D,T)

list_D = [set([i]) for i in range(N)]
list_T = [set([i]) for i in range(N)]
root_D = [i for i in range(N)]
root_T = [i for i in range(N)]

#print(list_D)

for _ in range(K):
    d = map(int, input().split())
    d0 = d[0] - 1
    d1 = d[1] - 1
    r0 = root_D[d0]
    r1 = root_D[d1]
    list_D[r0] = list_D[r0] | list_D[r1]
    root_D[r1] = r0
    root_D[d1] = r0
    #print(list_D, root_D)

for _ in range(L):
    t = map(int, input().split())
    t0 = t[0] - 1
    t1 = t[1] - 1
    r0 = root_T[t0]
    r1 = root_T[t1]
    list_T[r0] = list_T[r0] | list_T[r1]
    root_T[r1] = r0
    root_T[t1] = r0
    #print(list_T, root_T)

#和集合
res = [0] * N
for i in range(N):
    rd = root_D[i]
    rt = root_T[i]
    d = list_D[rd]
    t = list_T[rt]
    res[i] = len(d & t)
#print(*(res[i] for i in range(N)))
print(" ".join([str(i) for i in res]))

Submission status: Runtime Error

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

#print(N,K,L,D,T)

list_D = [set([i]) for i in range(N)]
list_T = [set([i]) for i in range(N)]
root_D = [i for i in range(N)]
root_T = [i for i in range(N)]

#print(list_D)

for _ in range(K):
    d = map(int, input().split())
    d0 = d[0] - 1
    d1 = d[1] - 1
    r0 = root_D[d0]
    r1 = root_D[d1]
    list_D[r0] = list_D[r0] | list_D[r1]
    root_D[r1] = r0
    root_D[d1] = r0
    #print(list_D, root_D)

for for _ in range(L):
    t = map(int, input().split())
    t0 = t[0] - 1
    t1 = t[1] - 1
    r0 = root_T[t0]
    r1 = root_T[t1]
    list_T[r0] = list_T[r0] | list_T[r1]
    root_T[r1] = r0
    root_T[t1] = r0
    #print(list_T, root_T)

#和集合
res = [0] * N
for i in range(N):
    rd = root_D[i]
    rt = root_T[i]
    d = list_D[rd]
    t = list_T[rt]
    res[i] = len(d & t)
#print(*(res[i] for i in range(N)))
print(" ".join([str(i) for i in res]))

Submission status: Runtime Error

Solution code:
N,K,L = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(K)]
T = [list(map(int, input().split())) for _ in range(L)]

#print(N,K,L,D,T)

list_D = [set([i]) for i in range(N)]
list_T = [set([i]) for i in range(N)]
root_D = [i for i in range(N)]
root_T = [i for i in range(N)]

#print(list_D)

for d in D:
    d0 = d[0] - 1
    d1 = d[1] - 1
    r0 = root_D[d0]
    r1 = root_D[d1]
    list_D[r0] = list_D[r0] | list_D[r1]
    root_D[r1] = r0
    root_D[d1] = r0
    #print(list_D, root_D)

for t in T:
    t0 = t[0] - 1
    t1 = t[1] - 1
    r0 = root_T[t0]
    r1 = root_T[t1]
    list_T[r0] = list_T[r0] | list_T[r1]
    root_T[r1] = r0
    root_T[t1] = r0
    #print(list_T, root_T)

#和集合
#res = [0] * N
for i in range(N):
    rd = root_D[i]
    rt = root_T[i]
    d = list_D[rd]
    t = list_T[rt]
    res[i] = len(d & t)
#print(*(res[i] for i in range(N)))
print(" ".join([str(i) for i in res]))

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define itrfor(itr,A) for(auto itr = A.begin(); itr !=A.end();itr++)
typedef long long llong;
char moji[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
char moji2[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
char moji3[10]={'0','1','2','3','4','5','6','7','8','9'};
#define Sort(a) sort(a.begin(),a.end());
#define Reverse(a) reverse(a.begin(),a.end());
#define print(a) cout << a << endl;
#define n_max int(1e5+5)


struct UnionFind{
    int A[n_max];
    UnionFind( int n){
        REP(i,n) A[i]=i;
    }

    int root(int a){
        if(A[a] == a)    return a;
        int tmp;
        tmp = root(A[a]);
        A[a] = tmp;
        return tmp;
    }

    bool same(int a, int b){
        if(root(a) == root(b)) return true;
        return false;
    }

    void merge(int a,int b){
        A[root(a)] = root(b);
    }
};


struct town{
    int k,l;
    int id;
};


bool comp(town a,town b){
    if(a.k != b.k) return a.k < b.k;
    else return a.l < b.l;
}


int main(){
    int n,k,l;
    cin >> n >> k >> l;
    UnionFind K(n),L(n);

    int a,b;
    REP(i,k){
        scanf("%d%d",&a,&b);
        K.merge(a-1,b-1);
    }
    REP(i,l){
        scanf("%d%d",&a,&b);
        L.merge(a-1,b-1);
    }

    town T[n_max];
    REP(i,n){
        T[i].id=i;
        T[i].k = K.root(i);
        T[i].l = L.root(i);
    }

    sort(T,T+n,comp);

    int ans[n_max]={};

    int i=0;
    while(1){
        pair<int,int> p;
        p.first = T[i].k;
        p.second = T[i].l;
        vector<int> ind;
        ind.push_back(T[i].id);
        while(1){
            i+=1;
            if(i < n and T[i].k == p.first and T[i].l == p.second){
                ind.push_back(T[i].id);
            }
            else{
                itrfor(itr,ind) ans[*itr] = ind.size();
                break;
            }
        }
        if(i >=n) break;
    }

    REP(i,n) cout << ans[i] << " ";

}

Submission status: Runtime Error

Solution code:
u'''Return all length combination'''
def all_comb(iterable):
    for i in range(0, len(iterable) + 1):
        comb = itertools.combinations(iterable, i)
        for pair in comb:
            yield(pair)


class UnionFind:
    def __init__(self, elems=None):
        class KeyDict(dict):
            def __missing__(self, key):
                self[key] = key
                return key

        self.parent = KeyDict()
        self.rank = collections.defaultdict(int)

        if elems is not None:
            for elem in elems:
                _, _ = self.parent[elem], self.rank[elem]

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

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

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

    def grouper(self):
        roots = [(x, self.find(x_par)) for x, x_par in self.parent.items()]
        root = operator.itemgetter(1)
        for _, group in itertools.groupby(sorted(roots, key=root), root):
            yield [x for x, _ in group]

N, K, L = map(int, input().split())
load_connections = UnionFind(range(1, N + 1))
rail_connections = UnionFind(range(1, N + 1))

for i in range(K):
    (p, q) = map(int, input().split())
    load_connections.unite(p, q)

for i in range(L):
    (r, s) = map(int, input().split())
    rail_connections.unite(r, s)

for i in range(1, N + 1):
    print([load_connections.are_same(i, j) and rail_connections.are_same(i, j) for j in range(1, N + 1)].count(True))

Submission status: Runtime Error

Solution code:
def bps(gr,p,s,num):
    if gr[s]!=-1:
        return
    gr[s]=num
    for x in p[s]:
        bps(gr,p,x,num)

N,K,L=list(map(int,input().split()))
dic={}
road=[[] for _ in range(N)]
rail=[[] for _ in range(N)]

for i in range(K):
    p,q=list(map(int,input().split()))
    road[p-1].append(q-1)
    road[q-1].append(p-1)

for i in range(L):
    r,s=list(map(int,input().split()))
    rail[r-1].append(s-1)
    rail[s-1].append(r-1)


roadG=[-1 for _ in range(N)]
num=0
for i in range(N):
    if roadG[i]==-1:
        bps(roadG,road,i,num)
        num+=1

railG=[-1 for _ in range(N)]
num=0
for i in range(N):
    if railG[i]==-1:
        bps(railG,rail,i,num)
        num+=1
dic={}
arr=[]
for i in range(N):
    key=roadG[i]*N+railG[i]
    arr.append(key)
    dic[key]=dic.setdefault(key,0)+1
print(dic[arr[0]],end='')
for x in arr[1:]:
    print(' {}'.format(dic[x]),end='')
print('')

Submission status: Runtime Error

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

    def buildTree(a):
        aT = [0]*(iN+1)
        for p,q in a:
            #if p > q :
            #   p,q = q,p
            thisroot = max(aT[q],aT[p],q) #試しにデカい方に合わせる
            if p <= aT[q] < thisroot:  #2個づつ来るからこんなんでいいだろ
                aT[aT[q]] = thisroot
            if p <= aT[p] < thisroot:
                aT[aT[p]] = thisroot
            aT[q] = thisroot
            aT[p] = thisroot
        return aT
    def getRoot(a,i):
        if a[i] == i or a[i] == 0:
            if a[i] == 0 : a[i] = i
            return i
        elif i < a[i] :
            a[i] = getRoot(a,a[i])
            return a[i]
        else:
        #   print("! ",i,a[i])

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

解()

Submission status: Runtime Error

Solution code:
mport sys
sys.setrecursionlimit(10**5)
def 解():
    iN,iK,iL = [int(_) for _ in input().split()]
    aD = [[int(_) for _ in sLine.split()] for sLine in sys.stdin.readlines()]
    a道 = aD[0:iK]
    a鉄道 = aD[iK:]

    d道 = {}
    d鉄道 = {}
#   for i in range(1,iN+1):
#       d道[i] = {i}
#       d鉄道[i] ={i}
    def fMakeSet(d,x,y):
        if x in d:
            d[x].add(y)
        else:
            d[x] = {y}

    for p,q in a道:
        #d道[p].add(q)
        #d道[q].add(p)
        fMakeSet(d道,q,p)
        fMakeSet(d道,p,q)
    for r,s in a鉄道:
        fMakeSet(d鉄道,r,s)
        fMakeSet(d鉄道,s,r)

    def fdfs(d,iS):
        dsVisited=set()
        def digRoute(iT):
            dsVisited.add(iT)
            if iT in d:
                for i in d[iT] - dsVisited:
                    #dsVisited.add(i)
                    digRoute(i)
        digRoute(iS)
        return dsVisited
    def buildGroup(d):
        gl = {}
        gidx = {}
        v = set()
        iC = 0
        for i in range(1,iN+1):
            if i in v:
                continue
            else:
                dsList = fdfs(d,i)
                for i in dsList:
                    gidx[i] = iC
                gl[iC]=dsList
                iC += 1
                v = v | dsList
        return (gl,gidx)
    dg鉄道,idxdg鉄道 = (buildGroup(d鉄道))
    dg道,idxdg道 = (buildGroup(d道))
    ak鉄道 = dg鉄道.keys()
    ak道 = dg道.keys()
    aM = [[ None for _ in range(len(ak道))] for _ in range(len(ak鉄道))]
    for i in ak鉄道:
        for j in ak道:
            aM[i][j]=len(dg鉄道[i] & dg道[j])
    aRet = []
    for i in range(1,iN+1):
        aRet.append(str(aM[idxdg鉄道[i]][idxdg道[i]]))
    print( " ".join(aRet))
解()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionliit(10**5)
def 解():
    iN,iK,iL = [int(_) for _ in input().split()]
    aD = [[int(_) for _ in sLine.split()] for sLine in sys.stdin.readlines()]
    a道 = aD[0:iK]
    a鉄道 = aD[iK:]

    d道 = {}
    d鉄道 = {}
    for i in range(1,iN+1):
        d道[i] = {i}
        d鉄道[i] ={i}

    for p,q in a道:
        d道[p].add(q)
        d道[q].add(p)
    for r,s in a鉄道:
        d鉄道[r].add(s)
        d鉄道[s].add(r)

    def fdfs(d,iS):
        dsVisited=set()
        def digRoute(iT):
            for i in d[iT] - dsVisited:
                dsVisited.add(i)
                digRoute(i)
        digRoute(iS)
        return dsVisited

    aRet = []
    for i in range(1,iN+1):
        aRet.append(str(len(fdfs(d道,i) & fdfs(d鉄道,i))))
    print( " ".join(aRet))
解()

Submission status: Runtime Error

Solution code:
import sys
iN,iK,iL = [int(_) for _ in input().split()]
aD = [[int(_) for _ in sLine.split()] for sLine in sys.stdin.readlines()]
a道 = aD[0:iK]
a鉄道 = aD[iK:]

d道 = {}
d鉄道 = {}
for i in range(1,iN+1):
    d道[i] = {i}
    d鉄道[i] ={i}

for p,q in a道:
    d道[p].add(q)
    d道[q].add(p)
for r,s in a鉄道:
    d鉄道[r].add(s)
    d鉄道[s].add(r)

def fdfs(d,iS):
    dsVisited=set()
    def digRoute(iT):
        for i in d[iT] - dsVisited:
            dsVisited.add(i)
            digRoute(i)
    digRoute(iS)
    return dsVisited

aRet = []
for i in range(1,iN+1):
    aRet.append(str(len(fdfs(d道,i) & fdfs(d鉄道,i))))
print( " ".join(aRet))

Submission status: Runtime Error

Solution code:
7 4 4
1 2
2 3
2 5
6 7
3 5
4 5
3 4
6 7

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Wed Aug 15 14:20:12 2018
ABC049D
@author: maezawa
"""

n, k, l = list(map(int, input().split()))
road = [{}]
rail = [{}]

for i in range(k):
    pi, qi = list(map(int, input().split()))
    j = 0
    while j<len(road):
        if road[j] == {}:
            road[j] = {pi, qi}
            break
        elif pi in road[j] or qi in road[j]:
            road[j] |= {pi, qi}
            if len(road)>j+1:
                for m in range(j+1,len(road)):
                    if pi in road[m] or qi in road[m]:
                        road[j] |= road[m]
                        road.pop(m)
            break
        else:
            road.append({pi, qi})
            j += 1   
        
#print(*road)

for i in range(l):
    pi, qi = list(map(int, input().split()))
    j = 0
    while j<len(rail):
        if rail[j] == {}:
            rail[j] = {pi, qi}
            break
        elif pi in rail[j] or qi in rail[j]:
            rail[j] |= {pi, qi}
            if len(rail)>j+1:
                for m in range(j+1,len(rail)):
                    if pi in rail[m] or qi in rail[m]:
                        rail[j] |= rail[m]
                        rail.pop(m)
            break
        else:
            rail.append({pi, qi})
            j += 1
    
#print(*rail)

ans = [1]*n
for roadset in road:
    for railset in rail:
        randr = roadset & railset
        if randr != {}:
            lenrandr = len(randr)
            for i in randr:
                ans[i-1] = lenrandr

print(ans[0], end='')
for i in range(1, n):
    print(' '+str(ans[i]), end='')
print()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Wed Aug 15 14:20:12 2018
ABC049D
@author: maezawa
"""

n, k, l = list(map(int, input().split()))
road = [{}]
rail = [{}]

for i in range(k):
    pi, qi = list(map(int, input().split()))
    j = 0
    while j<len(road):
        if road[j] == {}:
            road[j] = {pi, qi}
            break
        elif pi in road[j] or qi in road[j]:
            road[j] |= {pi, qi}
            if len(road)>j:
                for m in range(j+1,len(road)):
                    if pi in road[m] or qi in road[m]:
                        road[j] |= road[m]
                        road.pop(m)
            break
        else:
            road.append({pi, qi})
            j += 1   
        
#print(*road)

for i in range(l):
    pi, qi = list(map(int, input().split()))
    j = 0
    while j<len(rail):
        if rail[j] == {}:
            rail[j] = {pi, qi}
            break
        elif pi in rail[j] or qi in rail[j]:
            rail[j] |= {pi, qi}
            if len(rail)>j:
                for m in range(j+1,len(rail)):
                    if pi in rail[m] or qi in rail[m]:
                        rail[j] |= rail[m]
                        rail.pop(m)
            break
        else:
            rail.append({pi, qi})
            j += 1
    
#print(*rail)

ans = [1]*n
for roadset in road:
    for railset in rail:
        randr = roadset & railset
        if randr != {}:
            lenrandr = len(randr)
            for i in randr:
                ans[i-1] = lenrandr

print(ans[0], end='')
for i in range(1, n):
    print(' '+str(ans[i]), end='')
print()

Submission status: Runtime Error

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

def get_groups(n, m):
    road = [[] for _ in range(n+1)]
    for _ in range(m):
        p, q = list(map(int, input().split()))
        road[p].append(q)
        road[q].append(p)

    groups = [0]*(n+1)
    group_idx = 1
    for i in range(1, n+1):
        if groups[i] == 0:
            groups[i] = group_idx
            connect = [i]
            while len(connect) > 0:
                cnct = connect[0]
                connect = connect[1:]
                for c in road[cnct]:
                    if groups[c] == 0:
                        groups[c] = group_idx
                        connect.append(c)
            group_idx += 1
            
    return groups

road_groups = get_groups(n, k)
train_groups = get_groups(n, l)
# print(road_groups, train_groups)
pairs = {}
for c in range(1, n+1):
    key = (road_groups[c], train_groups[c])
    if not key in pairs.keys():
        pairs[key] = 1
    else:
        pairs[key] += 1

ans = ''
for c in range(1, n+1):
    key = (road_groups[c], train_groups[c])
    ans += f'{pairs[key]} '
print(ans)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10**8)

def find(x,table):	#xの根を返す	
	if table[x] == x:
		return x
	else:
		table[x] = find(table[x],table)	#親の更新(根を直接親にして参照距離を短く)
		return table[x]

def union(x,y,table,rank):	#xとyを繋げる
	x = find(x,table)	
	y = find(y,table)
	
	if x == y:
		return
	
	if rank[x] > rank[y]:
		table[y] = x
	else:
		table[x] = y
		if rank[x] == rank[y]:
			rank[y] += 1

def check(x,y,table):
	if find(x,table) == find(y,table):
		return True
	else:
		return False

N,M = map(int,input().split())
P_li = list(map(int,input().split()))

table = [i for i in range(N+1)]	#木の親 table[x] == x なら根	
rank  = [1 for i in range(N+1)]	#木の長さ

for i in range(0,M):
	a,b = map(int, input().split())
	union(a,b,table,rank)
	
ans = 0

for i in range(1,N+1):
	if check(i,P_li[i-1],table):
		ans += 1

print (ans)