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

    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

    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))
解()

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}

    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))
解()




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

Submission status: Time Limit Exceeded

Solution code:
#! /usr/bin/python3
# 連結 / Connectivity
"""
全ての都市について、その都市と道路・鉄道の
どちらでも連結している都市の数を求めてください。

※問題では都市は 1-index なことに注意。
"""
import numpy as np
test_mode = False

pq = []
rs = []

# ----- ここから入力 -----
N, K, L = map(int, input().split())

for _ in range(K):
    pq.append(list(map(int, input().split())))
    # [pi, qi]の2次元リスト

for _ in range(L):
    rs.append(list(map(int, input().split())))
    # [ri, si]の2次元リスト

if test_mode:
    print('pq :', pq)
    print('rs :', rs)
# ----- ここまで入力 -----

table_road = [[0 for _ in range(N+1)] for _ in range(N+1)]
# 道路による都市連結表。(N+1)x(N+1) の単位正方行列。連結していると1、していないと0。
table_rail = [[0 for _ in range(N+1)] for _ in range(N+1)]
# 鉄道による都市連結表。(N+1)x(N+1) の単位正方行列。連結していると1、していないと0。
connections_list = [0 for _ in range(N+1)]
# 各都市の連結数リスト。i番目の要素が都市iに対応。


def initial_setting():
    """
    最初の穴埋め
    """
    for i in range(1, N+1):
        table_road[i][i] = 1
        table_rail[i][i] = 1
    # 対角線を埋める

    if test_mode:
        print('table_road:', table_road)
        print('table_rail:', table_rail)
        print('対角線を埋めた')


    for i in range(K):
        table_road[pq[i][0]][pq[i][1]] = 1
    for i in range(L):
        table_rail[rs[i][0]][rs[i][1]] = 1
    # 直接接続している都市の組み合わせを埋める


def fill_table(table, n):
    """
    1都市の経由でつながっている都市を、
    n x n 正方形の表 table に書き加える関数。
    x<y<z
    """
    need_to_loop = False

    temp_table = table
    original = str(table)
    for x in range(1, n):
        for y in range(x+1, n):
            for z in range(y+1, n):
                if test_mode:
                    print('[x, y, z] =', x, y, z)
                if temp_table[x][y] == 1 and temp_table[y][z] == 1:
                    temp_table[x][z] = 1
                if temp_table[x][y] == 1 and temp_table[x][z] == 1:
                    temp_table[y][z] = 1
    edited = str(temp_table)

    if original != edited:
        need_to_loop = True
    if test_mode:
        print('temp_table:', temp_table)
        print('補正の穴埋めをした')
        print(need_to_loop)
    if need_to_loop:
        return fill_table(temp_table, n)
    # まだだったらもう一回

    return temp_table


def count_connections(l_2d, tate, yoko):
    """
    接続を 0,1,2 で表記した2次元リストを受けて
    connections_list を編集する。
    """
    for i in range(1, tate):
        for j in range(1, yoko):
            if l_2d[i][j] == 2:
                connections_list[i] += 1
                if not i == j:
                    connections_list[j] += 1



def main():
    """
    main
    """
    if test_mode:
        print('table_road:', table_road)
        print('table_rail:', table_rail)

        print('入力して表を作った')

    initial_setting()

    if test_mode:
        print('table_road:', np.array(table_road))
        print('table_rail:', np.array(table_rail))

    table_road_filled = np.array(fill_table(table_road, N))
    table_rail_filled = np.array(fill_table(table_rail, N))

    if test_mode:
        print('table_road_filled:')
        print(table_road_filled)
        print('table_rail_filled:')
        print(table_rail_filled)

    table_sum = table_road_filled + table_rail_filled

    if test_mode:
        print('table_sum:')
        print(table_sum)

    count_connections(list(table_sum), N+1, N+1)

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
from collections import defaultdict as dd

class UFT(object):
  def __init__(self,n):
    self.parent={i:i for i in range(1,n+1)}
    self.height={i:0 for i in range(1,n+1)}
  def find(self,a):
    if self.parent[a]!=a:
      self.parent[a]=self.find(self.parent[a])
    return self.parent[a]
  def unite(self,a,b):
    a=self.find(a)
    b=self.find(b)
    if self.height[a]>self.height[b]:
      self.parent[b]=a
    else:
      if self.height[a]==self.height[b]:
        self.height[b]+=1
      self.parent[a]=b
  def isunited(self,a,b):
    return self.find(a)==self.find(b)


n,k,l=map(int,input().split())
uk=UFT(n)
ul=UFT(n)
dc=dd(int)

for _ in range(k):
  a,b=map(int,input().split())
  uk.unite(a,b)

for _ in range(l):
  a,b=map(int,input().split())
  ul.unite(a,b)
  
for i in range(1,n+1):
  dc[(uk.find(i),ul.find(i))]+=1

print(" ".join(map(str,(dc[(uk.find(i),ul.find(i))] for i in range(1,n+1)))))

Submission status: Time Limit Exceeded

Solution code:
N,K,L = map(int,input().split())
roads = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(K)]
rails = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(L)]

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1

uf_road = UnionFind(N)
for a,b in roads:
    if uf_road.is_same(a,b): continue
    uf_road.unite(a,b)

uf_rail = UnionFind(N)
for a,b in rails:
    if uf_rail.is_same(a,b): continue
    uf_rail.unite(a,b)

for i in range(N):
    uf_road.root(i)
    uf_rail.root(i)

road_sets = [None] * N
for i in range(N):
    r = uf_road.root(i)
    if not road_sets[r]:
        road_sets[r] = set()
    road_sets[r].add(i)

rail_sets = [None] * N
for i in range(N):
    r = uf_rail.root(i)
    if not rail_sets[r]:
        rail_sets[r] = set()
    rail_sets[r].add(i)

ans = []
for i in range(N):
    r1 = uf_road.root(i)
    r2 = uf_rail.root(i)
    cnt = len(road_sets[r1] & rail_sets[r2])
    ans.append(cnt)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
class UnionFind():
    def __init__(self,size):
        self.table = [-1 for _  in range(size)]
    def find(self,x):
        while self.table[x] >= 0:
            x = self.table[x]
        return x

    def union(self,x,y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] != self.table[s2]:
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                else:
                    self.table[s1] = s2
            else:
                self.table[s1] += -1
                self.table[s2] = s1
        return
n,k,l = map(int, sys.stdin.readline().split())
p = []
for i in range(k):
    p.append(list(map(int, input().split())))
do = [[] for i in range(n+1)]
for pi in p:  #0-originedに注意
    do[pi[0]].append(pi[1])
    do[pi[1]].append(pi[0])
p = []
for i in range(l):
    p.append(list(map(int, input().split())))
te = [[] for i in range(n+1)]
for pi in p:  #0-originedに注意
    te[pi[0]].append(pi[1])
    te[pi[1]].append(pi[0])
dou = UnionFind(n)
for i in range(n+1):
  a = do[i]
  for j in a:
    dou.union(i-1,j-1)
douro = [-1] * n
for i in range(n):
  douro[i] = dou.find(i)
tet = UnionFind(n)
for i in range(n+1):
  a = te[i]
  for j in a:
    tet.union(i-1,j-1)
tetu = [-1] * n
for i in range(n):
  tetu[i] = tet.find(i)
pair = [[0,0]for i in range(n)]
for i in range(n):
  pair[i] = (douro[i],tetu[i])
from collections import defaultdict
d = defaultdict(int)
for i in range(n):
  d[pair[i]] += 1
ans = []
for i in range(n):
  ans.append(d[pair[i]])
print(" ".join(map(str,ans)))

Submission status: Time Limit Exceeded

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


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

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

    def 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[y] = x
        else:
            self.par[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

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


uf1 = UnionFind(n)
uf2 = UnionFind(n)

rec = []
for i in range(k):
    p, q = map(int, input().split())
    uf1.unite(p - 1, q - 1)
    rec.append((p - 1, q - 1))

num = [1] * n
for i in range(l):
    r, s = map(int, input().split())
    uf2.unite(r - 1, s - 1)
    if (r - 1, s - 1) not in rec:
        rec.append((r - 1, s - 1))

for a, b in rec:
    if uf1.same(a, b) and uf2.same(a, b):
        num[a] += 1
        num[b] += 1


print(" ".join(map(str, num)))

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    def __init__(self, size):
        self.table = [-1 for _  in range(size)]

    def find(self, x):
        while self.table[x] >= 0:
            x = self.table[x]
        return x

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] != self.table[s2]:
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                else:
                    self.table[s1] = s2
            else:
                self.table[s1] += -1
                self.table[s2] = s1
        return


n, k, ll = (int(i) for i in input().split())
qList = [[int(i) for i in input().split()] for i in range(k)]
rList = [[int(i) for i in input().split()] for i in range(ll)]

unionQ = UnionFind(n+1)
for q in qList:
    unionQ.union(q[0], q[1])

unionR = UnionFind(n+1)
for r in rList:
    unionR.union(r[0], r[1])


findQList = []
findRList = []
arr = [[0 for i in range(n+1)] for j in range(n+1)]
for i in range(n+1):
    findQList.append(unionQ.find(i))
    findRList.append(unionR.find(i))
    arr[findQList[i]][findRList[i]] += 1

for i in range(1, n+1):
    print(arr[findQList[i]][findRList[i]], end=" ")

Submission status: Time Limit Exceeded

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[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[m] ={}
            break
        else:
            rail.append({pi, qi})
            j += 1
    
#print(*rail)
for i in reversed(range(len(road))):
    if road[i] == {}:
        road.pop(i)

for i in reversed(range(len(rail))):
    if rail[i] == {}:
        rail.pop(i)

ans = [1]*n
for roadset in road:
    for railset in rail:
        randr = set(roadset) & set(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: Time Limit Exceeded

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[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[m] ={}
            break
        else:
            rail.append({pi, qi})
            j += 1
    
#print(*rail)

ans = [1]*n
for roadset in road:
    for railset in rail:
        randr = set(roadset) & set(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: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, L, PQ, RS):
    ans = 0
    gr = defaultdict(list)
    for p, q in PQ:
        gr[p].append(q)
        gr[q].append(p)

    gt = defaultdict(list)
    for r, s in RS:
        gt[r].append(s)
        gt[s].append(r)

    ccr = {}
    unused = set(gr.keys())
    while unused:
        q = [unused.pop()]
        con = set([])
        while q:
            v = q.pop()
            con.add(v)
            for u in gr[v]:
                if u in unused:
                    q.append(u)
                    unused.remove(u)
        for v in con:
            ccr[v] = con

    cct = {}
    unused = set(gt.keys())
    while unused:
        q = [unused.pop()]
        con = set([])
        while q:
            v = q.pop()
            con.add(v)
            for u in gt[v]:
                if u in unused:
                    q.append(u)
                    unused.remove(u)
        for v in con:
            cct[v] = con

    ans = []
    for i in range(1, N+1):
        if i in cct and i in ccr:
            a = len(cct[i] & ccr[i])
        else:
            a = 1
        ans.append(a)
    return " ".join(map(str, ans))


def main():
    N, K, L = read_int_n()
    PQ = [read_int_n() for _ in range(K)]
    RS = [read_int_n() for _ in range(L)]
    print(slv(N, K, L, PQ, RS))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, K, L = map(int, input().split())
G = [[[], []] for i in range(N)]
R = [[i, i] for i in range(N)]
def root(i, j):
  if R[i][j] != i:
    R[i][j] = root(R[i][j], j)
  return R[i][j]
for i in range(K):
  p, q = map(int, input().split())
  rp = root(p - 1, 0)
  rq = root(q - 1, 0)
  if rp != rq:
    R[rp][0] = min(rp, rq)
    R[rq][0] = min(rp, rq)
for i in range(L):
  r, s = map(int, input().split())
  rr = root(r - 1, 1)
  rs = root(s - 1, 1)
  if rr != rs:
    R[rr][1] = min(rr, rs)
    R[rs][1] = min(rr, rs)
U = [[[], []] for i in range(N)]
for i in range(N):
  R[i][0] = root(i, 0)
  R[i][1] = root(i, 1)
  U[R[i][0]][0].append(i)
  U[R[i][1]][1].append(i)
A = [1 for i in range(N)]
for i in range(N):
  if A[i] == 1:
    S = set(U[R[i][0]][0]) & set(U[R[i][1]][1])
    for s in S:
      A[s] = len(S)
ans = ''
for a in A:
  ans += ' ' + str(a)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K, L = map(int, input().split())
G = [[[], []] for i in range(N)]
R = [[i, i] for i in range(N)]
def root(i, j):
  if R[i][j] != i:
    R[i][j] = root(R[i][j], j)
  return R[i][j]
for i in range(K):
  p, q = map(int, input().split())
  rp = root(p - 1, 0)
  rq = root(q - 1, 0)
  if rp != rq:
    R[rp][0] = min(rp, rq)
    R[rq][0] = min(rp, rq)
for i in range(L):
  r, s = map(int, input().split())
  rr = root(r - 1, 1)
  rs = root(s - 1, 1)
  if rr != rs:
    R[rr][1] = min(rr, rs)
    R[rs][1] = min(rr, rs)
U = [[[], []] for i in range(N)]
for i in range(N):
  R[i][0] = root(i, 0)
  R[i][1] = root(i, 1)
  U[R[i][0]][0].append(i)
  U[R[i][1]][1].append(i)
A = [1 for i in range(N)]
for i in range(N):
  if A[i] == 1:
    S = set(U[R[i][0]][0]) & set(U[R[i][1]][1])
    for s in S:
      A[s] = len(S)
ans = ''
for a in A:
  ans += ' ' + str(a)
print(ans[1:])

Submission status: Time Limit Exceeded

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.append(str(pairs[key]))
print(' '.join(ans))

Submission status: Time Limit Exceeded

Solution code:
n, k, l = [int(i) for i in input().split()]
P = [[int(i) for i in input().split()] for j in range(k)]
R = [[int(i) for i in input().split()] for j in range(l)]

class UnionFind():
  def __init__(self, elements):
    self.elements = elements
    self._root = {}
    for e in self.elements:
      self._root[e] = e
    
  def unite(self, x, y):
    x = self.root(x)
    y = self.root(y)
    if not x == y:
      self._root[x] = y
    
  def root(self, x):
    if not self._root[x] == x:
      self._root[x] = self.root(self._root[x])
    return self._root[x]
  
  def count(self):
    cnt = {}
    for e in self.elements:
      cnt[self.root(e)] += cnt.get(self.root(e), 0)
      
    for e in self.elements:
      yield cnt.get(e, 0)
      
  def get_union(self):
    union = {}
    for e in self.elements:
      if self.root(e) in union:
        union[self.root(e)].add(e)
      else:
        union[self.root(e)] = {e}
    return union
      
  
road = UnionFind(range(1, n+1))
rail = UnionFind(range(1, n+1))

for i in range(k):
  road.unite(P[i][0], P[i][1])
  
for i in range(l):
  rail.unite(R[i][0], R[i][1])

ans = {}
for e in range(1, n+1):
  key = (road.root(e), rail.root(e))
  ans[key] = ans.get(key, 0) +1
  
for e in range(1, n+1):
  print(ans[(road.root(e), rail.root(e))], end=' ')

Submission status: Time Limit Exceeded

Solution code:
n, k, l = [int(i) for i in input().split()]
P = [[int(i) for i in input().split()] for j in range(k)]
R = [[int(i) for i in input().split()] for j in range(l)]

class UnionFind():
  def __init__(self, elements):
    self.elements = elements
    self._root = {}
    for e in self.elements:
      self._root[e] = e
    
  def union(self, x, y):
    x = self.root(x)
    y = self.root(y)
    if not x == y:
      self._root[x] = y
    
  def root(self, x):
    if not self._root[x] == x:
      self._root[x] = self.root(self._root[x])
    return self._root[x]
  
  def count(self):
    cnt = {}
    for e in self.elements:
      cnt[self.root(e)] += cnt.get(self.root(e), 0)
      
    for e in self.elements:
      yield cnt.get(e, 0)
      
  def get_union(self):
    union = {}
    for e in self.elements:
      if self.root(e) in union:
        union[self.root(e)].add(e)
      else:
        union[self.root(e)] = {e}
    return union
      
  
road = UnionFind(range(1, n+1))
rail = UnionFind(range(1, n+1))

for i in range(k):
  road.union(P[i][0], P[i][1])
  
for i in range(l):
  rail.union(R[i][0], R[i][1])

road.union = road.get_union()
rail.union = rail.get_union()

for e in range(1, n+1):
  print(len(road.union[road.root(e)] & rail.union[rail.root(e)]), end=' ')

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools

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,K,L = map(int,input().split())

table_car = [i for i in range(N)]	#木の親 table[x] == x なら根	
rank_car  = [1 for i in range(N)]	#木の長さ
table_tr  = [i for i in range(N)] 
rank_tr   = [1 for i in range(N)]

for i in range(0,K):
	a,b = map(int, input().split())
	union(a-1,b-1,table_car,rank_car)
	
for i in range(0,L):
	a,b = map(int, input().split())
	union(a-1,b-1,table_tr,rank_tr)
	
iters = list(itertools.combinations(range(N),2))
ans_li = [1 for i in range(N)]

for iter in iters:
	a,b = iter
	if check(a,b,table_car) and check(a,b,table_tr):
		ans_li[a] += 1
		ans_li[b] += 1

print (' '.join(map(str,ans_li)))

Submission status: Time Limit Exceeded

Solution code:
N,K,L = map(int,input().split())
roads = [list(map(int,input().split())) for _ in range(K)]
rails = [list(map(int,input().split())) for _ in range(L)]
outputs = [1 for _ in range(N)]

class UF():
  def __init__(self,size):
    self.table = [-1 for _ in range(size)]
    self.results = {}
    
  def find(self,x):
    target = x
    while self.table[x] >= 0:
      x = self.table[x]
    if 0 < self.table[target]:
      self.table[target] = x
    return x
  
  def union(self,x,y):
    s1 = self.find(x)
    s2 = self.find(y)
    if s1 != s2:
      if self.table[s2] < self.table[s1]:
        self.table[s1] = s2
        self.table[s2] -= 1
        if s1 in self.results:
          self.results[s2] = self.results[s1].union(self.results[s2])
          self.results.pop(s1)
        else:
          self.results[s2].add(s1)
      else:
        self.table[s2] = s1
        self.table[s1] -= 1
        if s1 in self.results and s2 in self.results:
          self.results[s1] = self.results[s1].union(self.results[s2])
          self.results.pop(s2)
        elif s1 in self.results:
          self.results[s1].add(s2)
        else:
          self.results[s1] = set([s1,s2])
    return

w = UF(N+1)

for r in roads:
  w.union(r[0],r[1])

t = UF(N+1)
for l in rails:
  t.union(l[0],l[1])

for x in range(1,N+1):
  X= w.find(x)
  Y = t.find(x)
  if X in w.results and Y in t.results:
    outputs[x-1] = len(w.results[X].intersection(t.results[Y]))
  else:
    outputs[x-1] = 1
print(' '.join(map(str,outputs)))

Submission status: Time Limit Exceeded

Solution code:
N,K,L = map(int,input().split())
roads = [list(map(int,input().split())) for _ in range(K)]
rails = [list(map(int,input().split())) for _ in range(L)]
outputs = [1 for _ in range(N)]

class UF():
  def __init__(self,size):
    self.table = [-1 for _ in range(size)]
    self.results = {}
    
  def find(self,x):
    target = x
    while self.table[x] >= 0:
      x = self.table[x]
    if 0 < self.table[target]:
      self.table[target] = x
    return x
  
  def union(self,x,y):
    s1 = self.find(x)
    s2 = self.find(y)
    if s1 != s2:
      if self.table[s2] < self.table[s1]:
        self.table[s1] = s2
        self.table[s2] -= 1
        if s1 in self.results:
          self.results[s2] = (self.results[s1] | self.results[s2])
          self.results.pop(s1)
        else:
          self.results[s2].add(s1)
      else:
        self.table[s2] = s1
        self.table[s1] -= 1
        if s1 in self.results and s2 in self.results:
          self.results[s1] = self.results[s1] | self.results[s2]
          self.results.pop(s2)
        elif s1 in self.results:
          self.results[s1].add(s2)
        else:
          self.results[s1] = set([s1,s2])
    return

w = UF(N+1)

for r in roads:
  w.union(r[0],r[1])

t = UF(N+1)
for l in rails:
  t.union(l[0],l[1])

for x in range(1,N+1):
  X= w.find(x)
  Y = t.find(x)
  if X in w.results and Y in t.results:
    outputs[x-1] = len(w.results[X].intersection(t.results[Y]))
  else:
    outputs[x-1] = 1
print(' '.join(map(str,outputs)))

Submission status: Time Limit Exceeded

Solution code:
N,K,L = map(int,input().split())
roads = [list(map(int,input().split())) for _ in range(K)]
rails = [list(map(int,input().split())) for _ in range(L)]
outputs = [1 for _ in range(N)]

class UF():
  def __init__(self,size):
    self.table = [-1 for _ in range(size)]
    self.results = {}
    
  def find(self,x):
    target = x
    while self.table[x] >= 0:
      x = self.table[x]
    if 0 < self.table[target]:
      self.table[target] = x
    return x
  
  def union(self,x,y):
    s1 = self.find(x)
    s2 = self.find(y)
    if s1 != s2:
      if self.table[s2] < self.table[s1]:
        self.table[s1] = s2
        self.table[s2] -= 1
        if s1 in self.results:
          self.results[s2] = (self.results[s1] | self.results[s2])
          self.results.pop(s1)
        else:
          self.results[s2].add(s1)
      else:
        self.table[s2] = s1
        self.table[s1] -= 1
        if s1 in self.results and s2 in self.results:
          self.results[s1] = self.results[s1] | self.results[s2]
          self.results.pop(s2)
        elif s1 in self.results:
          self.results[s1].add(s2)
        else:
          self.results[s1] = set([s1,s2])
    return

w = UF(N+1)

for r in roads:
  w.union(r[0],r[1])

t = UF(N+1)
for l in rails:
  t.union(l[0],l[1])

for x in range(1,N+1):
  X= w.find(x)
  Y = t.find(x)
  if X in w.results and Y in t.results:
    outputs[x-1] = len(w.results[X] & t.results[Y])
  else:
    outputs[x-1] = 1
print(' '.join(map(str,outputs)))