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:

    # n要素で初期化
    def __init__(self,n):
        self.par = list(range(n))
        self.rank = [0]*n
        self.memo = [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]
    
    # xとyの属する集合を併合
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return None
        
        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

    # xとyが同じ集合に属するか否か
    def same(self,x,y):
        return self.find(x) == self.find(y)
    
    # 木の根を求める
    def findsp(self,x):
        if self.par[x] == x:
            self.memo[x] = 1
            return x
        else:
            self.par[x] = self.find(self.par[x])
            self.memo[x] = 1
            return self.par[x]

    def allfind(self,n):
        for i in range(n):
            if self.memo[i] == 1:
                self.findsp(i)
    
    def root(self,x):
        return self.par[x]

if __name__ == '__main__':
    n,k,l = map(int,input().split())
    UF_k = UnionFind(n)
    UF_l = UnionFind(n)
    for i in range(k):
        p,q = map(int,input().split())
        UF_k.unite(p-1,q-1)
    for i in range(l):
        r,s = map(int,input().split())
        UF_l.unite(r-1,s-1)
    UF_k.allfind(n)
    UF_l.allfind(n)
    l = []
    for i in range(n):
        l.append((UF_k.root(i),UF_l.root(i)))
    for i in range(n):
        print(l.count(l[i]),end=' ')

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:

    # n要素で初期化
    def __init__(self,n):
        self.par = list(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]
    
    # xとyの属する集合を併合
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return None
        
        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

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

if __name__ == '__main__':
    n,k,l = map(int,input().split())
    UF = UnionFind(2*n)
    for i in range(k):
        p,q = map(int,input().split())
        UF.unite(p-1,q-1)
    for i in range(l):
        r,s = map(int,input().split())
        UF.unite(n+r-1,n+s-1)

    for i in range(n):
        res = 0
        for j in range(n):
            if UF.same(i,j) and UF.same(i+n,j+n):
                res += 1
        print(res,end=' ')

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:

    # n要素で初期化
    def __init__(self,n):
        self.par = list(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]
    
    # xとyの属する集合を併合
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return None
        
        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

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

if __name__ == '__main__':
    n,k,l = map(int,input().split())
    UF_k = UnionFind(n)
    UF_l = UnionFind(n)
    for i in range(k):
        p,q = map(int,input().split())
        UF_k.unite(p-1,q-1)
    for i in range(l):
        r,s = map(int,input().split())
        UF_l.unite(r-1,s-1)

    for i in range(n):
        res = 0
        for j in range(n):
            if UF_k.same(i,j) and UF_l.same(i,j):
                res += 1
        print(res,end=' ')

Submission status: Time Limit Exceeded

Solution code:
# 連結
import sys
from collections import Counter, defaultdict
input = sys.stdin.readline
N, K, L = map(int, input().split())


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

    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 members(self, x):
        root = self.find(x)
        return [i for i in range(self.n+1) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


A = UnionFind(N)
B = UnionFind(N)


ans = [0 for i in range(N+1)]
for _ in range(K):
    p, q = map(int, input().split())
    A.union(p, q)
for _ in range(L):
    p, q = map(int, input().split())
    B.union(p, q)

members = defaultdict(list)
for i in range(1, N+1):
    K = A.find(i)
    members[A.find(i)].append(i)

roots = A.roots()

for parent in roots:
    if parent == 0:
        continue

    group = members[parent]
    # ここでN**2のループをしている危険性があるので予め連想配列で処理する
    B_parent = [B.find(child) for child in group]
    C = dict(Counter(B_parent))
    for child in group:
        ans[child] = C[B.find(child)]
print(*ans[1:])

Submission status: Time Limit Exceeded

Solution code:
# 連結
from collections import Counter
N, K, L = map(int, input().split())


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

    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 members(self, x):
        root = self.find(x)
        return [i for i in range(self.n+1) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


A = UnionFind(N)
B = UnionFind(N)

ans = [0 for i in range(N+1)]
for _ in range(K):
    p, q = map(int, input().split())
    A.union(p, q)
for _ in range(L):
    p, q = map(int, input().split())
    B.union(p, q)

roots = A.roots()

for parent in roots:
    if parent == 0:
        continue

    group = A.members(parent)

    B_parent = [B.find(child) for child in group]
    C = dict(Counter(B_parent))
    for child in group:
        ans[child] = C[B.find(child)]
print(*ans[1:])

Submission status: Time Limit Exceeded

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

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

    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 find(self, x):          #親を出力
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def same(self, x, y):       #xとyが同じグループかどうか
        return self.find(x) == self.find(y)

    def size(self, x):          #グループの要素数
        return -self.parents[self.find(x)]

    def members(self, x):       #xと同じグループの要素
        root = self.find(x)
        return {i for i in range(self.n) if self.find(i) == root}

    def roots(self):            #親の要素一覧
        return {i for i, x in enumerate(self.parents) if x < 0}

    def group_count(self):      #グループの個数
        return len(self.roots())

    def all_group_members(self):      #グループのメンバー一覧
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

################

def main():
    N, K, L = map(int, input().split())
    ufK = UnionFind(N)
    ufL = UnionFind(N)
    for i in range(K):
        a,b = map(int,input().split())
        ufK.union(a-1, b-1)
    for i in range(L):
        a,b = map(int,input().split())
        ufL.union(a-1, b-1)

    ret = [0]*N
    for i in range(N):
        ret[i]=len(set(ufK.members(i)) & set(ufL.members(i)))
    print(*ret)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

    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 find(self, x):          #親を出力
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def same(self, x, y):       #xとyが同じグループかどうか
        return self.find(x) == self.find(y)

    def size(self, x):          #グループの要素数
        return -self.parents[self.find(x)]

    def members(self, x):       #xと同じグループの要素
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):            #親の要素一覧
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):      #グループの個数
        return len(self.roots())

    def all_group_members(self):      #グループのメンバー一覧
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

################

def main():
    N, K, L = map(int, input().split())
    ufK = UnionFind(N)
    ufL = UnionFind(N)
    rel = [list(map(int,input().split())) for i in range(K)]
    for i in rel:
        ufK.union(i[0]-1, i[1]-1)
    rel = [list(map(int,input().split())) for i in range(L)]
    for i in rel:
        ufL.union(i[0]-1, i[1]-1)

    ret = [0]*N
    for i in range(N):
        ret[i]=len(set(ufK.members(i)) & set(ufL.members(i)))
    print(*ret)

if __name__ == '__main__':
    main()

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)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N,K,L = map(int,input().split())
ans = []
ufp = UnionFind(N)
ufr = UnionFind(N)
for i in range(K):
    p,q = map(int, input().split())
    ufp.union(p-1, q-1)
for i in range(L):
    r,s = map(int,input().split())
    ufr.union(r-1, s-1)

for i in range(N):
    count = 0
    l = ufp.members(i)
    for j in l:
        if ufr.same(i, j):
            count+=1
    ans.append(count)
print(' '.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
class UF():
  def __init__(self, N):
    self.parents = [-1] * (N+1)

  def union(self, f, t):
    p1 = self.find(f)
    p2 = self.find(t)
    if p1 == p2:
      return

    if self.parents[p1] > self.parents[p2]:
      p1,p2 = p2,p1
    self.parents[p1] += self.parents[p2]
    self.parents[p2] = p1

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

  def members(self, n):
    root = self.find(n)
    if root == -1:
      return []
    return [ i for i, p in enumerate(self.parents) if self.find(i) == root]

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

for _ in range(K):
  f,t = map(int, input().split())
  uf_road.union(f,t)

for _ in range(L):
  f,t = map(int, input().split())
  uf_railway.union(f,t)

res = []
for i in range(1, N+1):
  road_members = uf_road.members(i)
  railway_members = uf_railway.members(i)
  c = 0
  for road_member in road_members:
    if road_member in railway_members:
      c += 1
  res.append(c)

print(" ".join([str(i) for i in res]))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

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

# Group1
G1 = [[] for i in range(N)]
for i in range(K):
    p, q = map(int, input().split())
    p -= 1
    q -= 1
    G1[p].append(q)
    G1[q].append(p)
gids = [0]*N
done = [False]*N
def dfs1(i, gid):
    gids[i] = gid
    done[i] = True
    for nex in G1[i]:
        if done[nex]: continue
        dfs1(nex, gid)
gid = 0
for i in range(N):
    if not done[i]:
        dfs1(i, gid)
        gid += 1

# Group2
G = [[] for i in range(N)]
for i in range(L):
    r, s = map(int, input().split())
    r -= 1
    s -= 1
    G[r].append(s)
    G[s].append(r)
done = [False]*N
D = []
gids2 = [0]*N
def dfs(i, gid):
    D[gid][gids[i]] += 1
    done[i] = True
    gids2[i] = gid
    for nex in G[i]:
        if done[nex]: continue
        dfs(nex, gid)
gid = 0
for i in range(N):
    if not done[i]:
        D.append([0]*N)
        dfs(i, gid)
        gid += 1

# answer
ans = [0]*N
for i in range(N):
    ans[i] = D[gids2[i]][gids[i]]
print(*ans)

Submission status: Time Limit Exceeded

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

# UnionFind
class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(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 unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            self.parent[x] = y

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

N, K, L = map(int, input().split())
un = UnionFind(N)
for i in range(K):
    p, q = map(int, input().split())
    p -= 1
    q -= 1
    un.unite(p, q)
G = [[] for i in range(N)]
for i in range(L):
    r, s = map(int, input().split())
    r -= 1
    s -= 1
    G[r].append(s)
    G[s].append(r)
done = [False]*N
D = []
gid = 0
def dfs(i, gid):
    D[gid][un.root(i)] += 1
    done[i] = True
    for nex in G[i]:
        if done[nex]: continue
        dfs(nex, gid)
for i in range(N):
    if not done[i]:
        D.append(defaultdict(int))
        dfs(i, gid)
        gid += 1
ans = [0]*N
done = [False]*N
gid = 0
def dfs2(i, gid):
    done[i] = True
    ans[i] = D[gid][un.root(i)]
    for nex in G[i]:
        if done[nex]: continue
        dfs2(nex, gid)
for i in range(N):
    if not done[i]:
        dfs2(i, gid)
        gid += 1
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


class UnionFind:
    def __init__(self, node):
        self.parent = [-1 for _ in range(node)]
        self.node = node

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

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

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

    def get_size(self, x):
        return -self.parent[self.find(x)]

    def members(self, x, is_set=False):
        root = self.find(x)
        res = [i for i in range(self.node) if self.find(i) == root]
        if is_set:
            return set(res)
        return res

    def all_root(self):
        return [idx for idx, val in enumerate(self.parent) if val < 0]


def main():
    cities, roads, railroads = map(int, input().split())
    uf_road = UnionFind(cities)
    uf_train = UnionFind(cities)
    for _ in range(roads):
        p, q = map(lambda x: int(x) - 1, input().split())
        uf_road.union(p, q)
    for _ in range(railroads):
        r, s = map(lambda x: int(x) - 1, input().split())
        uf_train.union(r, s)
    each_pair = []
    for i in range(cities):
        each_pair.append(tuple([tuple(uf_road.members(i)), tuple(uf_train.members(i))]))
    pair_count = dict(Counter(each_pair))
    answer = [pair_count[each_pair[i]] for i in range(cities)]
    print(" ".join(map(str, answer)))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

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

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

    def get_size(self, x):
        return -self.parent[self.find(x)]

    def members(self, x, is_set=False):
        root = self.find(x)
        res = [i for i in range(self.node) if self.find(i) == root]
        if is_set:
            return set(res)
        return res

    def all_root(self):
        return [idx for idx, val in enumerate(self.parent) if val < 0]


def main():
    cities, roads, railroads = map(int, input().split())
    uf_road = UnionFind(cities)
    uf_train = UnionFind(cities)
    for _ in range(roads):
        p, q = map(lambda x: int(x) - 1, input().split())
        uf_road.union(p, q)
    for _ in range(railroads):
        r, s = map(lambda x: int(x) - 1, input().split())
        uf_train.union(r, s)
    pair_count = {}
    each_pair = []
    for i in range(cities):
        now_pair = tuple([tuple(uf_road.members(i)), tuple(uf_train.members(i))])
        if now_pair in pair_count:
            pair_count[now_pair] += 1
        else:
            pair_count[now_pair] = 1
        each_pair.append(now_pair)
    answer = [pair_count[each_pair[i]] for i in range(cities)]
    print(" ".join(map(str, answer)))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

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

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

    def get_size(self, x):
        return -self.parent[self.find(x)]

    def members(self, x, is_set=False):
        root = self.find(x)
        res = [i for i in range(self.node) if self.find(i) == root]
        if is_set:
            return set(res)
        return res

    def all_root(self):
        return [idx for idx, val in enumerate(self.parent) if val < 0]


def main():
    cities, roads, railroads = map(int, input().split())
    uf_road = UnionFind(cities)
    uf_train = UnionFind(cities)
    for _ in range(roads):
        p, q = map(lambda x: int(x) - 1, input().split())
        uf_road.union(p, q)
    for _ in range(railroads):
        r, s = map(lambda x: int(x) - 1, input().split())
        uf_train.union(r, s)
    answer = [1 for _ in range(cities)]
    for i in range(cities):
        answer[i] = len(uf_road.members(i, True).intersection(uf_train.members(i, True)))
    print(" ".join(map(str, answer)))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    #n個の要素を初期化
    def __init__(self, n):
        self.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]
    
    #xとyの属する集合を併合
    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
    
    #xとyが同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    #要素xが属するグループに属する要素をリストで返す
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]


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

uf_road = UnionFind(N)
uf_train = UnionFind(N)

for road in roads:
    x, y = road
    uf_road.unite(x-1, y-1)

for train in trains:
    x, y = train
    uf_train.unite(x-1, y-1)

ans = []
for i in range(N):
    common = set(uf_road.members(i)) & set(uf_train.members(i))
    ans.append(len(common))

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    #n個の要素を初期化
    def __init__(self, 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]
    
    #xとyの属する集合を併合
    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
    
    #xとyが同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)


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

uf_road = UnionFind(N)
uf_train = UnionFind(N)

for road in roads:
    x, y = road
    uf_road.unite(x-1, y-1)

for train in trains:
    x, y = train
    uf_train.unite(x-1, y-1)

ans = []
for i in range(N):
    res = 0
    for j in range(N):
        if uf_road.same(i, j) and uf_train.same(i, j):
            res += 1
    ans.append(res)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    def unite(x, y):
        x = find(x)
        y = find(y)
        if x == y:
            return False
        else:
            if par[x] > par[y]:
                x, y = y, x
            par[x] += par[y]
            par[y] = x
            return True
    def members(x):
        root = find(x)
        return [i for i in range(n) if find(i) == root]

    def find2(x):
        if par2[x] < 0:
            return x
        else:
            par2[x] = find2(par2[x])
            return par2[x]
    def unite2(x, y):
        x = find2(x)
        y = find2(y)
        if x == y:
            return False
        else:
            if par2[x] > par2[y]:
                x, y = y, x
            par2[x] += par2[y]
            par2[y] = x
            return True
    def members2(x):
        root2 = find2(x)
        return [i for i in range(n) if find2(i) == root2]

    n, k, l = map(int, input().split())
    par = [-1] * (n)
    par2 = [-1] * (n)
    for _ in range(k):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        unite(a, b)
    for _ in range(l):
        c, d = map(int, input().split())
        c -= 1
        d -= 1
        unite2(c, d)
    for i in range(n):
        road = set(members(i))
        train = set(members2(i))
        #print(road, train)
        print(len(road & train), end=' ')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
import copy
from queue import Queue
import heapq
import numpy as np

MOD = 1000000007

#n = int(input())
#b = int(input())
n, k, l = [int(i) for i in input().split()]
#table = [int(i)  for i in input().split()] for j in range(h)] #table[h][w]
#table = [list(input()) for n in range(r)] #table[h][w]
#s = [int(i) for i in input().split()]
#s = [int(i) for i in range(n)]
#s = [int(input()) for i in range(n)]
#s = input()
#list = list(s)
dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
dp2 = [[0 for _ in range(n+1)] for _ in range(n+1)]
#dp = [[[0 for _ in range(11)] for _ in range(2)] for _ in range(11)]

#a = [[0 for _ in range(n+1)] for _ in range(n+1)]
#b = [[0 for _ in range(n+1)] for _ in range(n+1)]

for i in range(k):
    s = [int(i) for i in input().split()]
    dp[s[0]][s[1]] = 1
    dp[s[1]][s[0]] = 1
for i in range(l):
    s = [int(i) for i in input().split()]
    dp2[s[0]][s[1]] = 1
    dp2[s[1]][s[0]] = 1

ch = [0 for _ in range(n+1)]
q = Queue()

for i in range(1,n+1) :
    if(ch[i] == 0) :
        q.put(i)
        ch[i] = i
        while (not q.empty()):
            temp = q.get()
            for j in range (1,n+1):
                if(dp[temp][j] == 1 and ch[j] == 0):
                    ch[j] = i
                    q.put(j)

ch2 = [0 for _ in range(n+1)]
for i in range(1,n+1) :
    if(ch2[i] == 0) :
        q.put(i)
        ch2[i] = i
        while (not q.empty()):
            temp = q.get()
            for j in range (1,n+1):
                if(dp2[temp][j] == 1 and ch2[j] == 0):
                    ch2[j] = i
                    q.put(j)


kotae = [0 for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1,n+1):
        if(ch[i] == ch[j] and ch2[i] == ch2[j]):
            kotae[i] += 1

kotae2 = [str(kotae[i]) for i in range(1,n+1)]
kotae3 = " ".join(kotae2)
print(kotae3)