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: Time Limit Exceeded

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

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

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

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

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

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

def execOne(num, uf):
    for _ in range(num):
        d0, d1 = map(int, input().split())
        d0 = d0 - 1
        d1 = d1 - 1
        uf.union(d0, d1)

uf_D = UnionFind(N)
uf_T = UnionFind(N)

execOne(K, uf_D)
execOne(L, uf_T)

res = [0] * N
for i in range(N):
    for j in range(N):
        if (uf_D.same_check(i,j) and uf_T.same_check(i,j)):
            res[i] += 1
#print(*(res[i] for i in range(N)))
print(" ".join([str(i) for i in res]))

Submission status: Time Limit Exceeded

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

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

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

def execOne(num, list, root):
    for _ in range(num):
        d0, d1 = map(int, input().split())
        d0 = d0 - 1
        d1 = d1 - 1
        r0 = root[d0]
        r1 = root[d1]
        for l in list[r1]:
            root[l] = r0
        list[r0].extend(list[r1])
        #print(d0, d1, list, root)

execOne(K, list_D, root_D)
execOne(L, list_T, root_T)

#和集合
res = [0] * N
for i in range(N):
    rd = root_D[i]
    rt = root_T[i]
    d = set(list_D[rd])
    t = set(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: Time Limit Exceeded

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

N,K,L=map(int,input().split())
R=[list(map(int,input().split())) for i in range(K)]
T=[list(map(int,input().split())) for i in range(L)]

Group1=[i for i in range(N+1)]#グループ分け.Group[i]=jのときiとjは同じグループ
Group2=[i for i in range(N+1)]#グループ分け.Group[i]=jのときiとjは同じグループ

def find1(x):#find(a)=find(b)のとき同じグループ
    while Group1[x] != x:
        x=Group1[x]
    return x

def Union1(x,y):#xとyが同じグループになるよう更新
    if find1(x) != find1(y):
        Group1[find1(y)]=Group1[find1(x)]=min(find1(y),find1(x))

def find2(x):#find(a)=find(b)のとき同じグループ
    while Group2[x] != x:
        x=Group2[x]
    return x

def Union2(x,y):#xとyが同じグループになるよう更新
    if find2(x) != find2(y):
        Group2[find2(y)]=Group2[find2(x)]=min(find2(y),find2(x))

for i,j in R:
    Union1(i,j)

for i,j in T:
    Union2(i,j)

Grin1=[[] for i in range(N+1)]
Grin2=[[] for i in range(N+1)]

for i in range(1,N+1):
    Grin1[Group1[find1(i)]].append(i)
    Grin2[Group2[find2(i)]].append(i)

for i in range(1,N+1):
    Grin1[i]=set(Grin1[i])
    Grin2[i]=set(Grin2[i])

for i in range(1,N+1):
    print(len(Grin1[find1(i)] & Grin2[find2(i)]),end=" ")

Submission status: Time Limit Exceeded

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

Group1=[i for i in range(N+1)]#グループ分け.Group[i]=jのときiとjは同じグループ
Group2=[i for i in range(N+1)]#グループ分け.Group[i]=jのときiとjは同じグループ

def find1(x):#find(a)=find(b)のとき同じグループ
    while Group1[x] != x:
        x=Group1[x]
    return x

def Union1(x,y):#xとyが同じグループになるよう更新
    if find1(x) != find1(y):
        Group1[find1(y)]=Group1[find1(x)]=min(find1(y),find1(x))

def find2(x):#find(a)=find(b)のとき同じグループ
    while Group2[x] != x:
        x=Group2[x]
    return x

def Union2(x,y):#xとyが同じグループになるよう更新
    if find2(x) != find2(y):
        Group2[find2(y)]=Group2[find2(x)]=min(find2(y),find2(x))

for i,j in R:
    Union1(i,j)

for i,j in T:
    Union2(i,j)

Grin1=[set() for i in range(N+1)]
Grin2=[set() for i in range(N+1)]

for i in range(1,N+1):
    Grin1[Group1[find1(i)]].add(i)
    Grin2[Group2[find2(i)]].add(i)

for i in range(1,N+1):
    print(len(Grin1[find1(i)] & Grin2[find2(i)]),end=" ")

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, k, l = map(int, input().split())
    roads = [set([i]) for i in range(n)]
    rails = [set([i]) for i in range(n)]
    for _ in range(k):
        a, b = map(lambda s: int(s) - 1, input().split())
        i_large, i_small = (a, b) if len(roads[a]) > len(roads[b]) else (b, a)
        roads[i_large] |= roads[i_small]
        for i in roads[i_small]:
            roads[i] = roads[i_large]
    for _ in range(l):
        a, b = map(lambda s: int(s) - 1, input().split())
        i_large, i_small = (a, b) if len(rails[a]) > len(rails[b]) else (b, a)
        rails[i_large] |= rails[i_small]
        for i in rails[i_small]:
            rails[i] = rails[i_large]
    res = [len(roads[i] & rails[i]) for i in range(n)]
    print(' '.join(map(str, res)))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, k, l = map(int, input().split())
    roads = [set([i]) for i in range(n)]
    rails = [set([i]) for i in range(n)]
    for _ in range(k):
        a, b = map(lambda s: int(s) - 1, input().split())
        u = roads[a] | roads[b]
        for i in u:
            roads[i] = u
    for _ in range(l):
        a, b = map(lambda s: int(s) - 1, input().split())
        u = rails[a] | rails[b]
        for i in u:
            rails[i] = u
    res = [len(roads[i] & rails[i]) for i in range(n)]
    print(' '.join(map(str, res)))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, K, L = map(int, input().split())
road = np.array(range(1, N+1))
rail = np.array(range(1, N+1))

for k in range(K):
    p, q = map(int, input().split()) # p < q
    # 数字小さい方に統一する
    road[road == road[q-1]] = road[p-1]
    # for n in range(N):
    # if road[n] == road[q-1]: # p, q >= 1
    #   road[n] = road[p-1]

for l in range(L):
    r, s = map(int, input().split()) # r < s
    # 数字小さい方に統一する
    
    rail[rail == rail[s-1]] = rail[r-1]
    # for n in range(N):
    #    if rail[n] == rail[s-1]:
    #        rail[n] = rail[r-1]
            
set_list = []
for n in range(N):
    set_list.append((road[n], rail[n]))

ans = ""
for n in range(N):
    ans += " %d"%(set_list.count(set_list[n]))

print(ans[1:])

Submission status: Time Limit Exceeded

Solution code:
N, K, L = map(int, input().split())
road = list(range(1, N+1))
rail = list(range(1, N+1))

for k in range(K):
    p, q = map(int, input().split()) # p < q
    # 数字小さい方に統一する
    for n in range(N):
        if road[n] == road[q-1]: # p, q >= 1
            road[n] = road[p-1]

for l in range(L):
    r, s = map(int, input().split()) # r < s
    # 数字小さい方に統一する
    for n in range(N):
        if rail[n] == rail[s-1]:
            rail[n] = rail[r-1]
            

set_list = []
for n in range(N):
    set_list.append((road[n], rail[n]))
ans = ""
for n in range(N):
    ans += " %d"%(set_list.count(set_list[n]))
print(ans[1:])

Submission status: Time Limit Exceeded

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


class UFT():
    def __init__(self):
        self.par = [i for i in range(N + 1)]
        self.rank = [0] * (N + 1)

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

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

        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)


Road = UFT()
for _ in range(K):
    p, q = [int(_) for _ in input().split()]
    Road.unite(p, q)
Railway = UFT()
for _ in range(L):
    r, s = [int(_) for _ in input().split()]
    Railway.unite(r, s)
memo = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
    memo[Road.find(i)][Railway.find(i)] += 1
print(' '.join(str(memo[Road.find(i)][Railway.find(i)])
               for i in range(1, N + 1)))

Submission status: Time Limit Exceeded

Solution code:
N, K, L = [int(_) for _ in input().split()]
memo = [[i, i] for i in range(N + 1)]

for _ in range(K):
    p, q = [int(_) for _ in input().split()]
    memo[p][0] = min(memo[p][0], memo[q][0])
    memo[q][0] = memo[p][0]
for _ in range(L):
    r, s = [int(_) for _ in input().split()]
    memo[r][1] = min(memo[r][1], memo[s][1])
    memo[s][1] = memo[r][1]


def dfs0(i):
    if i == memo[i][0]:
        return i
    else:
        memo[i][0] = dfs0(memo[i][0])
        return memo[i][0]


def dfs1(i):
    if i == memo[i][1]:
        return i
    else:
        memo[i][1] = dfs1(memo[i][1])
        return memo[i][1]


for i in range(1, N + 1):
    memo[i][0] = dfs0(i)
    memo[i][1] = dfs1(i)
count = [[0] * N for _ in range(N)]
for i in range(1, N + 1):
    count[memo[i][0] - 1][memo[i][1] - 1] += 1
print(' '.join(str(count[memo[i][0]-1][memo[i][1]-1])
               for i in range(1, N + 1)))

Submission status: Time Limit Exceeded

Solution code:
class UFT():
    def __init__(self):
        self.par = {}
        self.rank = {}

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

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

        self.rank[x] = self.rank.get(x, 0)
        self.rank[y] = self.rank.get(y, 0)

        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)

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

Road = UFT()
for _ in range(K):
    p, q = [int(_) for _ in input().split()]
    Road.unite(p, q)
Railway = UFT()
for _ in range(L):
    r, s = [int(_) for _ in input().split()]
    Railway.unite(r, s)
memo = {}
for i in range(1, N + 1):
    memo[Road.find(i), Railway.find(i)] = memo.get((Road.find(i), Railway.find(i)), 0) + 1
print(' '.join(str(memo[Road.find(i), Railway.find(i)]) for i in range(1, N + 1)))

Submission status: Time Limit Exceeded

Solution code:
class UFT():
    def __init__(self):
        self.par = {}
        self.rank = {}

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

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

        self.rank[x] = self.rank.get(x, 0)
        self.rank[y] = self.rank.get(y, 0)

        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)

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

Road = UFT()
for _ in range(K):
    p, q = [int(_) for _ in input().split()]
    Road.unite(p, q)
Railway = UFT()
for _ in range(L):
    r, s = [int(_) for _ in input().split()]
    Railway.unite(r, s)
memo = [[0] * N for _ in range(N)]
for i in range(1, N + 1):
    memo[Road.find(i) - 1][Railway.find(i) - 1] += 1
print(' '.join(str(memo[Road.find(i) - 1][Railway.find(i) - 1]) for i in range(1, N + 1)))

Submission status: Time Limit Exceeded

Solution code:
class UFT():
    def __init__(self):
        self.par = {}
        self.rank = {}

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

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

        self.rank[x] = self.rank.get(x, 0)
        self.rank[y] = self.rank.get(y, 0)

        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)

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

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

Submission status: Time Limit Exceeded

Solution code:
class UFT():
    def __init__(self):
        self.par = {}
        self.rank = {}

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

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

        self.rank[x] = self.rank.get(x, 0)
        self.rank[y] = self.rank.get(y, 0)

        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 root(self, x):
        return self.par.get(x, x)


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

C = UFT()
for _ in range(K):
    p, q = [int(_) for _ in input().split()]
    C.unite(p, q)
for _ in range(L):
    r, s = [int(_) for _ in input().split()]
    C.unite(r + N, s + N)
memo = [[0] * N for _ in range(N)]
for i in range(1, N + 1):
    memo[C.root(i) - 1][C.root(i + N) - N - 1] += 1
print(' '.join(str(memo[C.root(i) - 1][C.root(i + N) - N - 1]) for i in range(1, N + 1)))

Submission status: Time Limit Exceeded

Solution code:
class UFT():
    def __init__(self):
        self.par = {}
        self.rank = {}

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

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

        self.rank[x] = self.rank.get(x, 0)
        self.rank[y] = self.rank.get(y, 0)

        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)


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

C = UFT()
for _ in range(K):
    p, q = [int(_) for _ in input().split()]
    C.unite(p, q)
for _ in range(L):
    r, s = [int(_) for _ in input().split()]
    C.unite(r + N, s + N)
ans = []
for i in range(1, N + 1):
    count = 0
    for j in range(1, N + 1):
        if C.same(i, j) and C.same(i + N, j + N):
            count += 1
    ans += [str(count)]
print(' '.join(ans))

Submission status: Time Limit Exceeded

Solution code:
class Unionfind:
  def __init__(self,n):
    self.Tree=[i for i in range(n)]
    self.rank=[0]*n

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

  def unite(self,x,y):
    s1=self.find(x)
    s2=self.find(y)
    if s1==s2:
      pass
    else:
      if self.rank[s1]>self.rank[s2]:
        self.Tree[s2]=s1
      elif self.rank[s1]<self.rank[s2]:
        self.Tree[s1]=s2
      else:
        self.Tree[s2]=s1
        self.rank[s1]+=1
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.unite(p-1,q-1)
for j in range(L):
  r,s=map(int,input().split())
  uf2.unite(r-1,s-1)
ans=[1]*N
for i in range(N):
  for j in range(i):
    if uf1.find(i)==uf1.find(j) and uf2.find(i)==uf2.find(j):
      ans[i]+=1
      ans[j]+=1
ans=list(map(str,ans))
print(" ".join(ans))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3                                                                                                                                                                                                                                                                                                                                                              
# -*- coding: utf-8 -*-                                                                                                                                                                                                                                                                                                                                                         

'''                                                                                                                                                                                                                                                                                                                                                                             
https://abc049.contest.atcoder.jp/tasks/arc065_b                                                                                                                                                                                                                                                                                                                                
'''

import itertools
import sys
import itertools
import operator
import collections

from inspect import currentframe

def chkprint(*args):
    names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args), file=sys.stderr)

def printerr(value):
    print(value, file=sys.stderr)

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())
road_connections = UnionFind(range(1, N + 1))
rail_connections = UnionFind(range(1, N + 1))

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

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

d = collections.defaultdict(lambda: 0)
for i in range(1, N + 1):
    p1, p2 = road_connections.find(i), rail_connections.find(i)
    d[(p1, p2)] += 1

ans = [str(d[(road_connections.find(i), rail_connections.find(i))]) for i in range(1, N + 1)]
print(' '.join(ans))

Submission status: Time Limit Exceeded

Solution code:
import itertools
import sys
import itertools
import operator
import collections

from inspect import currentframe

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: Time Limit Exceeded

Solution code:
N, K, L = [int(_) for _ in input().split()]
PQ = sorted([sorted([int(_) for _ in input().split()]) for _ in range(K)], key = lambda xs: xs[0])
RS = sorted([sorted([int(_) for _ in input().split()]) for _ in range(L)], key = lambda xs: xs[0])

road_train = [[i, i] for i in range(N + 1)]

for pq in PQ:
    road_train[pq[0]][0] = min(road_train[pq[0]][0], road_train[pq[1]][0])
    road_train[pq[1]][0] = road_train[pq[0]][0]
for rs in RS:
    road_train[rs[0]][1] = min(road_train[rs[0]][1], road_train[rs[1]][1])
    road_train[rs[1]][1] = road_train[rs[0]][1]

dp = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
result = []
for i in range(1, N + 1):
    if dp[road_train[i][0]][road_train[i][1]] == 0:
        count = 0
        for j in range(1, N + 1):
            if road_train[j] == road_train[i]:
                count += 1
        dp[road_train[i][0]][road_train[i][1]] = count
    result += [str(dp[road_train[i][0]][road_train[i][1]])]

print(' '.join(result))

Submission status: Time Limit Exceeded

Solution code:
import itertools
N, K, L = [int(_) for _ in input().split()]
PQ = [[int(_) for _ in input().split()] for _ in range(K)]
RS = [[int(_) for _ in input().split()] for _ in range(L)]

road = [[1 if i == j else 0 for j in range(N + 1)] for i in range(N + 1)]
road[0][0] = 0
train = [[1 if i == j else 0 for j in range(N + 1)] for i in range(N + 1)]
train[0][0] = 0

for i, j in itertools.product(range(K), range(1, N + 1)):
    if road[PQ[i][0]][j] or road[PQ[i][1]][j]:
        road[PQ[i][0]][j] = 1
        road[PQ[i][1]][j] = 1
        road[j][PQ[i][0]] = 1
        road[j][PQ[i][1]] = 1

for i, j in itertools.product(range(L), range(1, N + 1)):
    if train[RS[i][0]][j] or train[RS[i][1]][j]:
        train[RS[i][0]][j] = 1
        train[RS[i][1]][j] = 1
        train[j][RS[i][0]] = 1
        train[j][RS[i][1]] = 1

print(' '.join([str(sum([road[i][j] and train[i][j] for j in range(1, N + 1)])) for i in range(1, N + 1)]))

Submission status: Time Limit Exceeded

Solution code:
#unionfind
class UF:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n
    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            # 経路の圧縮
            self.table[x] = self._root(self.table[x])
            return self.table[x]
    def find(self, x, y):
        return self._root(x) == self._root(y)
    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2
    def show(self):
        print(self.table)
    def data(self):
        res={}
        n=len(self.table)
        for i in range(n):
            res.update({i:[i] if self.table[i]<0 else [self.table[i]]})
        for i in range(n):
            res[res[i][0]]+=[i]
        for i in range(n):
            if len(res[i])==1:
                del res[i]
            else:
                del res[i][0]
        return list(res.values())

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

Submission status: Time Limit Exceeded

Solution code:
import 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鉄道 = {}
	def fMakeSet(d,x,y):
		if x in d:
			d[x].add(y)
		else:
			d[x] = {y}
		
	for p,q in a道:
		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]=str(len(dg鉄道[i] & dg道[j]))
	aRet = []
	for i in range(1,iN+1):	
		aRet.append(aM[idxdg鉄道[i]][idxdg道[i]])
	print( " ".join(aRet))
解()

Submission status: Time Limit Exceeded

Solution code:
import 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道))
    aRet = []
    for i in range(1,iN+1):
        aRet.append(str(len( dg道[idxdg道[i]] & dg鉄道[idxdg鉄道[i]])))
    print( " ".join(aRet))
解()