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:
class UnionFind:
    MAX_N = 0
    PAR  = [] 
    RANK = []

    def __init__(self,n):
        self.MAX_N = n
        self.PAR = [ i for i in range(n)]
        self.RANK= [ 0 ] * 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
        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 = map(int,input().split())
path = UnionFind(N+1)
for _ in range(K):
    p,q = map(int,input().split())
    path.union(p,q)
rail = UnionFind(N+1)
for _ in range(L):
    p,q = map(int,input().split())
    rail.union(p,q)

Data = {}
for i in range(1,N+1):
    p = path.find(i)
    r = rail.find(i)
    k = str(p)+"-"+str(r)
    if k in Data.keys():
        Data[k] += 1
    else:
        Data[k] = 1

for i in range(1,N+1):
    p = path.find(i)
    r = rail.find(i)
    k = str(p)+"-"+str(r)
    print( Data[k], end= ' ')

Submission status: Time Limit Exceeded

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

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

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


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


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


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

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

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

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

ans = [0 for i in range(N)]

for i in range(N):
    for j in range(N):
        if find(road_par, i) == find(road_par, j) and find(rail_par, i) == find(rail_par, j):
            ans[i] += 1

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

Submission status: Time Limit Exceeded

Solution code:
def find_train(x): # 木の根を求める
    if par_train[x]==x:
        return x
    else:
        return find_train(par_train[x])

def unite_train(x,y): # xとyの属する集合を併合
    x=find_train(x)
    y=find_train(y)
    if x==y:return
    if rank_train[x]<rank_train[y]:
        par_train[x]=y
    else:
        par_train[y]=x
        if rank_train[x]==rank_train[y]:
            rank_train[x]+=1

def same_train(x,y): # xとyが同じ集合に属するか判定
    return find_train(x)==find_train(y)

def find_road(x): # 木の根を求める
    if par_road[x]==x:
        return x
    else:
        return find_road(par_road[x])

def unite_road(x,y): # xとyの属する集合を併合
    x=find_road(x)
    y=find_road(y)
    if x==y:return
    if rank_road[x]<rank_road[y]:
        par_road[x]=y
    else:
        par_road[y]=x
        if rank_road[x]==rank_road[y]:
            rank_road[x]+=1

def same_road(x,y): # xとyが同じ集合に属するか判定
    return find_road(x)==find_road(y)

def main():
    # x,y = map(int,input().split())           x=1,y=2
    # a = input().split()                      a=['1','2','3',...,'n']
    # a = list(map(int,input().split()))       a=[1,2,3,4,5,...,n]
    # li = input().split('T')	              FFFTFTTFF => li=['FFF', 'F', '', 'FF']
    # 複数行の「1 2 3 4」型の入力を一配列に
    # x = sorted([list(map(int, input().split())) for _ in range(n)])
    # ソート x.sort(key=lambda y:y[1])
    # [chr(i) for i in range(97, 97+26)] 英語小文字リスト
    # [chr(i) for i in range(65, 65+26)] 英語大文字リスト atcoder
    # ord(c) chr(2) alphabet <=> number
    n,k,l = map(int,input().split()) 

    global par_train,rank_train,par_road,rank_road
    par_train=[i for i in range(n)]  # 親
    rank_train=[0 for _ in range(n)] # 木の深さ
    par_road=[i for i in range(n)]  # 親
    rank_road=[0 for _ in range(n)] # 木の深さ
    for _ in range(k):
        p,q = map(int,input().split())
        p-=1
        q-=1
        unite_train(p,q)
    for _ in range(l):
        p,q = map(int,input().split())
        p-=1
        q-=1
        unite_road(p,q)
    ans=[0 for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if same_road(i,j):
                if same_train(i,j):
                    ans[i]+=1
    for i in range(n):
        print(ans[i])

main()

Submission status: Time Limit Exceeded

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

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

    def same(self, x, y):
        return self.find(x) == self.find(y)
def main():
    n,k,l = map(int,input().split())
    Road = [list(map(int,input().split())) for i in range(k)]
    Train = [list(map(int,input().split())) for i in range(l)]

    uf_r = UnionFind(n)
    uf_t = UnionFind(n)

    for i in range(k):
        uf_r.union(Road[i][0]-1,Road[i][1]-1)

    for i in range(l):
        uf_t.union(Train[i][0]-1,Train[i][1]-1)

    Roots = [[0]*n for i in range(n)]

    for i in range(n):
        Roots[uf_r.find(i)][uf_t.find(i)] += 1

    ans = [0]*n

    for i in range(n):
        ans[i] = Roots[uf_r.find(i)][uf_t.find(i)]

    print(*ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

n,k,l = map(int,input().split())
Road = [list(map(int,input().split())) for i in range(k)]
Train = [list(map(int,input().split())) for i in range(l)]

uf_r = UnionFind(n)
uf_t = UnionFind(n)

for i in range(k):
    uf_r.union(Road[i][0]-1,Road[i][1]-1)

for i in range(l):
    uf_t.union(Train[i][0]-1,Train[i][1]-1)

Roots = [[0]*n for i in range(n)]

for i in range(n):
    Roots[uf_r.find(i)][uf_t.find(i)] += 1

ans = [0]*n

for i in range(n):
    ans[i] = Roots[uf_r.find(i)][uf_t.find(i)]

print(*ans)

Submission status: Time Limit Exceeded

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

n,k,l = map(int,input().split())
Road = [list(map(int,input().split())) for i in range(k)]
Train = [list(map(int,input().split())) for i in range(l)]

uf_r = UnionFind(n)
uf_t = UnionFind(n)
uf = UnionFind(n)

for i in range(k):
    uf_r.union(Road[i][0]-1,Road[i][1]-1)

for i in range(l):
    uf_t.union(Train[i][0]-1,Train[i][1]-1)

Roots = [[0]*n for i in range(n)]

for i in range(n):
    Roots[uf_r.find(i)][uf_t.find(i)] += 1

ans = [0]*n

for i in range(n):
    ans[i] = Roots[uf_r.find(i)][uf_t.find(i)]

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
input = sys.stdin.readline
def change(after,index,li):
    before = li[index]
    for i in range(len(li)):
        if li[i]==before:
            li[i]=after
def main():
    n,k,l = map(int,input().split())
    road=[0 for _ in range(n)]
    train=[0 for _ in range(n)]
    r=t=1
    for _ in range(k):
        p,q = map(int,input().split())
        if road[p-1]==0 and road[q-1]==0:
            road[p-1]=road[q-1]=r
            r+=1
        elif road[p-1]!=0 and road[q-1]==0:
            road[q-1]=road[p-1]
        elif road[p-1]==0 and road[q-1]!=0:
            road[p-1]=road[q-1]
        else:
            change(road[p-1],q-1,road)
    for _ in range(l):
        p,q = map(int,input().split())
        if train[p-1]==0 and train[q-1]==0:
            train[p-1]=train[q-1]=t
            t+=1
        elif train[p-1]!=0 and train[q-1]==0:
            train[q-1]=train[p-1]
        elif train[p-1]==0 and train[q-1]!=0:
            train[p-1]=train[q-1]
        else:
            change(train[p-1],q-1,train)
    for i in range(n):
        ans=1
        if train[i]!=0 or road[i]!=0:
            for j in range(n):
                if i!=j and train[i]!=0 and train[i]==train[j] and road[i]!=0 and  road[i]==road[j]:
                    ans+=1
        print(ans)
main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

class UnionFind():
  def __init__(self,N):
    self.parents=list(range(N))
    self.size=[1]*N
  def find(self,x):
    if self.parents[x]==x:
      return x
    else:
      self.parents[x]=self.find(self.parents[x])
      return self.parents[x]
  def union(self,x,y):
    x,y=self.find(x),self.find(y)
    if x==y:
      return 
    if self.size[x]<self.size[y]:
      self.size[y]+=self.size[x]
      self.parents[x]=y
    else:
      self.size[x]+=self.size[y]
      self.parents[y]=x
      
ans=['1']*N
UF=UnionFind(N)
for i in range(K):
  x,y=map(int,input().split())
  UF.union(x-1,y-1)
tmp=[]
for j in range(L):
  x,y=map(int,input().split())
  if UF.find(x-1)==UF.find(y-1):
    v=UF.find(x-1)
    ans[x-1]=str(int(ans[x-1])+1)
    ans[y-1]=str(int(ans[y-1])+1)
    tmp.append([v,x,y])
searched=[]
for k in range(len(tmp)-1):
  for l in range(k+1,len(tmp)):
    if tmp[k][0]==tmp[l][0]:
      x,y=tmp[k][1],tmp[k][2]
      z,w=tmp[l][1],tmp[l][2]
      tmp_l=[[x,z],[x,w],[y,z],[y,w]]
      if y==z:
        tmp_l.remove([y,z])
      for _ in tmp_l:
        if [tmp[k][0]]+_ not in tmp and _ not in searched :
          x,y=_[0],_[1]
          searched.append([x,y])
          ans[x-1]=str(int(ans[x-1])+1)
          ans[y-1]=str(int(ans[y-1])+1)      
print(' '.join(ans))

Submission status: Time Limit Exceeded

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

"""
・蟻本演習2-4-3
・Union-Find木
"""

import sys
from collections import defaultdict

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

class UnionFind:
    """ Union-Find木 """

    def __init__(self, n):
        self.n = n
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        # 1-indexedのままでOK、その場合は[0]は未使用
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0）
        self.rank = [0] * (n+1)
        # あるノードを根とする集合に属するノード数
        self.size = [1] * (n+1)
        # あるノードを根とする集合が木かどうか
        self.tree = [True] * (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 x == y:
            self.tree[x] = False
            return
        if not self.tree[x] or not self.tree[y]:
            self.tree[x] = self.tree[y] = False

        # 木の高さを比較し、低いほうから高いほうに辺を張る
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            # 木の高さが同じなら片方を1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

    def get_size(self, x):
        """ あるノードの属する集合のノード数 """
        return self.size[self.find(x)]
    
    def is_tree(self, x):
        """ 木かどうかの判定 """
        return self.tree[self.find(x)]

    def len(self):
        """ 集合の数 """
        res = set()
        for i in range(self.n+1):
            res.add(self.find(i))
        # グループ0の分を引いて返却
        return len(res) - 1

N, K, L = MAP()
load = UnionFind(N)
train = UnionFind(N)

for i in range(K):
    a, b = MAP()
    load.union(a, b)

for i in range(L):
    a, b = MAP()
    train.union(a, b)

groups1 = defaultdict(set)
groups2 = defaultdict(set)
for i in range(1, N+1):
    g = load.find(i)
    groups1[g].add(i)
    g = train.find(i)
    groups2[g].add(i)

ans = [0] * N
for i in range(N):
    g1 = load.find(i+1)
    g2 = train.find(i+1)
    ans[i] = len(groups1[g1] & groups2[g2])
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

N,K,L  = map(int,input().split())      
road = UnionFind(N)
train = UnionFind(N)
for i in range(K):
  p,q = map(int,input().split())
  road.Unite(p-1,q-1)
for i in range(L):  
  r,s = map(int,input().split())
  train.Unite(r-1,s-1)
  
ans = ''
for i in range(N):
  count = 0
  for j in range(N):
    if((road.isSameGroup(i,j) == True)and(train.isSameGroup(i,j)==True)):
      count += 1
  if(i != N-1): ans += str(count)+' '
  else: ans += str(count)
print(ans)  
#100% TLE

Submission status: Time Limit Exceeded

Solution code:
import collections
N, K, L = [int(x) for x in input().split(' ')]
railway = list(range(N))
road = list(range(N))

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

def union(f, x, y):
    f[find(f, x)] = find(f, y)
rail_cnt = collections.defaultdict(set)
road_cnt = collections.defaultdict(set)
for _ in range(K):
    a, b = [int(x)-1 for x in input().split(' ')]
    union(railway, a, b)
for i in range(N):
    rail_cnt[find(railway, i)].add(i)
for _ in range(L):
    a, b = [int(x)-1 for x in input().split(' ')]
    union(road, a, b)
for i in range(N):
    road_cnt[find(road, i)].add(i)
res = []
for i in range(N):
    cur = road_cnt[road[i]] & rail_cnt[railway[i]]
    res.append(str(len(cur)))
print(' '.join(res))

Submission status: Time Limit Exceeded

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

def unite(node_a, node_b):
    root_a = node_a.root()
    root_b = node_b.root()
    if root_a == root_b:
        return False
    # if root_b.depth > root_a.depth:
    #     root_a, root_b = root_b, root_a
    root_b.is_root = False
    root_b.parent = root_a
    root_a.depth = max(root_a.depth, root_b.depth+1)
    return True

class Node:
    def __init__(self, id):
        self.id = id
        self.is_root = True
        self.parent = None
        self.depth = 1
    
    def root(self):
        if self.is_root:
            return self
        elif self.parent.is_root:
            return self.parent
        else:
            self.parent = self.parent.root()
            return self.parent

def main():
    N, K, L = map(int, input().split())
    
    trains = [Node(i) for i in range(N)]
    streets = [Node(i) for i in range(N)]

    for i in range(K):
        p, q = map(int, input().split())
        p -= 1; q -= 1
        unite(trains[p], trains[q])
    for i in range(L):
        r, s = map(int, input().split())
        r -= 1; s -= 1
        unite(streets[r], streets[s])
    dic = {}
    roots = []
    for i in range(N):
        tmp = (trains[i].root().id, streets[i].root().id)
        roots.append(tmp)
        if tmp in dic:
            dic[tmp] += 1
        else:
            dic[tmp] = 1
    
    for i in range(N-1):
        print(dic[roots[i]], end=" ")
    print(dic[roots[N-1]])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

import sys
def input():
	return sys.stdin.readline().strip()




class Union_Find():
	def __init__(self, n):
		self.union = [i for i in range(n)]
		self.level = [0 for i in range(n)]
		self.group = [[i] for i in range(n)]

	def root(self, i, mode=0):
		keiro = [i]
		ans = i
		while ans != self.union[ans]:
			ans = self.union[ans]
			keiro.append(ans)
		if mode == 0:
			return ans
		else:
			return ans, keiro

	def unite(self, i, j):
		root_i, list_i = self.root(i, 1)
		root_j, list_j = self.root(j, 1)
		if root_i != root_j:
			if self.level[root_i] < self.level[root_j]:
				self.group[root_j].extend(self.group[root_i])
				self.level[root_j] = max(self.level[root_i] + 1, self.level[root_j])
				for node in list_i:
					self.union[node] = root_j
			else:
				self.group[root_i].extend(self.group[root_j])
				self.level[root_i] = max(self.level[root_j] + 1, self.level[root_i])
				for node in list_j:
					self.union[node] = root_i

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

UF_road = Union_Find(N)
UF_train = Union_Find(N)
for i in range(K):
	p, q = list(map(int, input().split()))
	p -= 1
	q -= 1
	UF_road.unite(p,q)
for i in range(L):
	p, q = list(map(int, input().split()))
	p -= 1
	q -= 1
	UF_train.unite(p,q)

number = [-1 for i in range(N)]
for i in range(N):
	if number[i] == -1:
		if True:
			x = i
			road = UF_road.group[UF_road.root(x)]
			while len(road) > 0:
				train = set(UF_train.group[UF_train.root(road[0])])
				road = set(road)
				double = road & train
				road -= double
				double = list(double)
				num = len(double)
				for town in double:
					number[town] = num
				road = list(road)
		

def list_print(A):
	length = len(A)
	for i in range(length - 1):
		print(A[i], end="")
		print(" ", end="")
	print(A[N - 1])

list_print(number)

Submission status: Time Limit Exceeded

Solution code:

import sys
def input():
	return sys.stdin.readline().strip()




class Union_Find():
	def __init__(self, n):
		self.union = [i for i in range(n)]
		self.level = [0 for i in range(n)]
		self.group = [[i] for i in range(n)]

	def root(self, i, mode=0):
		keiro = [i]
		ans = i
		while ans != self.union[ans]:
			ans = self.union[ans]
			keiro.append(ans)
		if mode == 0:
			return ans
		else:
			return ans, keiro

	def unite(self, i, j):
		root_i, list_i = self.root(i, 1)
		root_j, list_j = self.root(j, 1)
		if root_i != root_j:
			if self.level[root_i] < self.level[root_j]:
				self.group[root_j].extend(self.group[root_i])
				self.level[root_j] = max(self.level[root_i] + 1, self.level[root_j])
				for node in list_i:
					self.union[node] = root_j
			else:
				self.group[root_i].extend(self.group[root_j])
				self.level[root_i] = max(self.level[root_j] + 1, self.level[root_i])
				for node in list_j:
					self.union[node] = root_i

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

UF_road = Union_Find(N)
UF_train = Union_Find(N)
for i in range(K):
	p, q = list(map(int, input().split()))
	p -= 1
	q -= 1
	UF_road.unite(p,q)
for i in range(L):
	p, q = list(map(int, input().split()))
	p -= 1
	q -= 1
	UF_train.unite(p,q)

number = [-1 for i in range(N)]
for i in range(N):
	if number[i] == -1:
		road = set(UF_road.group[UF_road.root(i)])
		train = set(UF_train.group[UF_train.root(i)])
		double = road & train
		double = list(double)
		num = len(double)
		for town in double:
			number[town] = num
def list_print(A):
	length = len(A)
	for i in range(length - 1):
		print(A[i], end="")
		print(" ", end="")
	print(A[N - 1])

list_print(number)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Wed Sep 11 11:26:39 2019
D - 連結 / Connectivity
実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 
400 点
@author: justwah
"""

class UnionFind:
    def __init__(self, N):
        self.rank = [0]*N
        self.parent = [i for i in range(N)]
        self.n = N
        
    def root(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]
        
    def merge(self, a, b):
        a = self.root(a)
        b = self.root(b)
        if a == b:
            return
        if self.rank[a] < self.rank[b]:
            self.parent[a] = b
        else:
            self.parent[b] = a
            if self.rank[a] == self.rank[b]:
                self.rank[a] +=1
                
    def same(self, a, b):
        return self.root(a) == self.roob(b)


n, k, l = map(int, input().split())
same = [0]*n

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

uf_rail = UnionFind(n)
for _ in range(l):
    r, s = map(int, input().split())
    uf_rail.merge(r-1, s-1)
    
for i in range(n):
    for j in range(n):
        if (uf_road.parent[i] - uf_road.parent[j] == 0) \
            and (uf_rail.parent[i] - uf_rail.parent[j] == 0):
            same[i] +=1

for i in range(n):
    print(same[i], end = ' ')

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Wed Sep 11 11:26:39 2019
D - 連結 / Connectivity
実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 
400 点
@author: justwah

stupid hard code solution
need to find good way to accommodate multiple forests for unionfind
"""

n, k, l = map(int, input().split())
parentK = [0]*n
parentL = [0]*n
rankK = [0]*n
rankL = [0]*n
same = [0]*n


for i in range(n):
    parentK[i] = i
    parentL[i] = i

def rootK(x): #recursively find root for a node
    if parentK[x] == x: # if at root, return self
        return x
    else:
        parentK[x] = rootK(parentK[x])  # while searching rejoint queried node to a common parent for hierarchical tree
        return parentK[x]
    
def mergeK(a, b):
    a = rootK(a)
    b = rootK(b)
    if rankK[a] < rankK[b]: # joint lower rank node to a higher rank one
        parentK[a] = b
    else:
        parentK[b] = a
        if rankK[a] == rankK[b]: # rank only change if two same rank node joined
            rankK[a] +=1
    return

def rootL(x): #recursively find root for a node
    if parentL[x] == x: # if at root, return self
        return x
    else:
        parentL[x] = rootL(parentL[x])  # while searching rejoint queried node to a common parent for hierarchical tree
        return parentL[x]
    
def mergeL(a, b):
    a = rootL(a)
    b = rootL(b)
    if rankL[a] < rankL[b]: # joint lower rank node to a higher rank one
        parentL[a] = b
    else:
        parentL[b] = a
        if rankL[a] == rankL[b]: # rank only change if two same rank node joined
            rankL[a] +=1
    return

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

for _ in range(l):
    r, s = map(int, input().split())
    mergeL(r-1, s-1)
    
for i in range(n):
    for j in range(n):
        if (parentK[i] - parentK[j] == 0) and (parentL[i] - parentL[j] == 0):
            same[i] +=1

for i in range(n):
    print(same[i], end = ' ')

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(10**8)

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

    def root(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.root(self.par[x]) # contraction
            return self.par[x]

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            if self.par[x] > self.par[y]: # merge technique
                x, y = y, x
            self.par[x] += self.par[y]
            self.par[y] = x

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

    def size(self, x):
        return -self.par[self.root(x)]

n, k, l = map(int, input().split())
uf_r = UnionFind(n)
for i in range(k):
    p, q = map(int, input().split())
    p -= 1
    q -= 1
    uf_r.unite(p, q)
uf_t = UnionFind(n)
for i in range(l):
    r, s = map(int, input().split())
    r -= 1
    s -= 1
    uf_t.unite(r, s)

root_r = defaultdict(set)
root_t = defaultdict(set)
for i in range(n):
    root_r[uf_r.root(i)].add(i)
    root_t[uf_t.root(i)].add(i)

ans = []
for i in range(n):
    ans.append(str(len(root_r[uf_r.root(i)] & root_t[uf_t.root(i)])))

print(' '.join(ans))

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations as combi
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1]*(n+1)
    self.rnk = [0]*(n+1)

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

  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if(x == y):
      return 
    elif(self.rnk[x] > self.rnk[y]):
      self.root[x] += self.root[y]
      self.root[y] = x
    else:
      self.root[y] += self.root[x]
      self.root[x] = y
      if(self.rnk[x] == self.rnk[y]):
        self.rnk[y] += 1

  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)
    
  def Count(self, x):
    return -self.root[self.Find_Root(x)]
N, K, L = map(int, input().split())
k = UnionFind(N)
l = UnionFind(N)
checkset = set()
res = [1] * (N + 1)
for _ in range(K):
  x, y = map(int, input().split())
  k.Unite(x, y)
  checkset.add(x)
  checkset.add(y)
for _ in range(L):
  x, y = map(int, input().split())
  l.Unite(x, y)
  checkset.add(x)
  checkset.add(y)
for c in combi(list(checkset), 2):
  if k.isSameGroup(c[0], c[1]) and l.isSameGroup(c[0], c[1]):
    res[c[0]] += 1
    res[c[1]] += 1
print(*(res[1: ]))