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
from collections import defaultdict

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

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

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

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

def main():
    input = sys.stdin.readline
    N, K, L = map(int, input().split())
    road = UnionFind(N)
    rail = UnionFind(N)

    for _ in range(K):
        p, q = map(int, input().split())
        road.unite(p-1, q-1)

    for _ in range(L):
        r, s = map(int, input().split())
        rail.unite(r-1, s-1)

    road_r = defaultdict(set)
    rail_r = defaultdict(set)
    for i in range(N):
        road_r[road.find(i)].add(i)
        rail_r[rail.find(i)].add(i)

    memo = [[-1 for _ in range(N)] for _ in range(N)]
    ans = [0 for _ in range(N)]
    for i in range(N):
        n = road.find(i)
        m = rail.find(i)

        if memo[n][m] != -1:
            ans[i] = memo[n][m]
        else:
            a = len(road_r[n] & rail_r[m])
            memo[n][m] = a
            ans[i] = a

    return print(*ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

class UnionFind:
    def __init__(self, n):
        self.root = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1] * (n+1)  # The number of nodes under the target node.

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

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

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

def main():
    input = sys.stdin.readline
    N, K, L = map(int, input().split())
    road = UnionFind(N)
    rail = UnionFind(N)

    for _ in range(K):
        p, q = map(int, input().split())
        road.unite(p-1, q-1)

    for _ in range(L):
        r, s = map(int, input().split())
        rail.unite(r-1, s-1)

    road_r = defaultdict(set)
    rail_r = defaultdict(set)
    for i in range(N):
        road_r[road.find(i)].add(i)
        rail_r[rail.find(i)].add(i)

    memo = [[-1 for _ in range(N)] for _ in range(N)]
    ans = [0 for _ in range(N)]
    for i in range(N):
        n = road.find(i)
        m = rail.find(i)

        if memo[n][m] != -1:
            ans[i] = memo[n][m]
        else:
            a = len(road_r[n] & rail_r[m])
            memo[n][m] = a
            ans[i] = a

    return print(*ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

class UnionFind:
    def __init__(self, n):
        self.root = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1] * (n+1)  # The number of nodes under the target node.

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

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

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

def main():
    input = sys.stdin.readline
    N, K, L = map(int, input().split())
    road = UnionFind(N)
    rail = UnionFind(N)

    for _ in range(K):
        p, q = map(int, input().split())
        road.unite(p-1, q-1)

    for _ in range(L):
        r, s = map(int, input().split())
        rail.unite(r-1, s-1)

    road_r = defaultdict(set)
    rail_r = defaultdict(set)
    for i in range(N):
        road_r[road.find(i)].add(i)
        rail_r[rail.find(i)].add(i)

    ans = [0 for _ in range(N)]
    for i in range(N):
        ans[i] = len(road_r[road.root[i]] & rail_r[rail.root[i]])

    return print(*ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]  # グループ番号
        self.rank = [0 for _ in range(n)]

    def find(self, x):
        """
        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 と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)


N, K, L = map(int, input().split())
road = UnionFind(N + 1)
rail = UnionFind(N + 1)
for i in range(K):
    p, q = map(int, input().split())
    road.union(p, q)
for j in range(L):
    r, s = map(int, input().split())
    rail.union(r, s)
ral = [rail.find(l) for l in range(1, N + 1)]
rol = [road.find(l) for l in range(1, N + 1)]
for k in range(N):
    # rak = rail.find(k)
    # rok = road.find(k)
    c = 0
    for l in range(N):
        # print(k, l)
        if ral[k] == ral[l] and rol[k] == rol[l]:
            c += 1
            # print(k,l)
    print(c)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]  # グループ番号
        self.rank = [0 for _ in range(n)]

    def find(self, x):
        """
        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 と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)


N, K, L = map(int, input().split())
road = UnionFind(N + 1)
rail = UnionFind(N + 1)
for i in range(K):
    p, q = map(int, input().split())
    road.union(p, q)
for j in range(L):
    r, s = map(int, input().split())
    rail.union(r, s)
for k in range(1, N + 1):
    rak = rail.find(k)
    rok = road.find(k)
    c = 0
    for l in range(1, N + 1):
        if rak == rail.find(l) and rok == road.find(l):
            c += 1
            # print(k,l)
    print(c)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]  # グループ番号
        self.rank = [0 for _ in range(n)]

    def find(self, x):
        """
        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 と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)


N, K, L = map(int, input().split())
road = UnionFind(N + 1)
rail = UnionFind(N + 1)
for i in range(K):
    p, q = map(int, input().split())
    road.union(p, q)
for j in range(L):
    r, s = map(int, input().split())
    rail.union(r, s)
for k in range(1, N + 1):
    c = 0
    for l in range(1, N + 1):
        if rail.find(k) == rail.find(l) and road.find(k) == road.find(l):
            c += 1
            # print(k,l)
    print(c)

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

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

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

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

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

N, K, L = MAP()

tree_pq = UnionFind(N+1) # N点集合からUnionFind木を作成
tree_rs = UnionFind(N+1)
pq = [LIST() for _ in range(K)]
for p, q in pq:
	tree_pq.union(p, q) # p, qを同じグループに
group_pq = [tree_pq.find(i) for i in range(N+1)]
# print(group_pq)
rs = [LIST() for _ in range(L)]
for r, s in rs:
	tree_rs.union(r, s)
group_rs = [tree_rs.find(i) for i in range(N+1)]
# print(group_rs)
pairs = [(group_pq[i], group_rs[i]) for i in range(N+1)]
for i in range(1, N+1):
	pair = (group_pq[i], group_rs[i])
	print(pairs.count(pair), end=" ")
print()

Submission status: Time Limit Exceeded

Solution code:
n, k, l = map(int, input().split())
load = [-1] * (n + 1)
train = [-1] * (n + 1)

def find_load(x, u = load):
    if u[x] < 0 :
        return x
    else:
        return find_load(u[x])

def find_train(x, u = train):
    if u[x] < 0 :
        return x
    else:
        return find_train(u[x])

for i in range(k):
    p, q = map(int, input().split())
    p, q = map(find_load, [p, q])
    p, q = sorted((p, q))
    if p != q:
        load[q] = p
        load = [p if (x > 0) & (x == load[p]) else x for x in load]
load = [i if x < 0 else x for i, x in enumerate(load)]

for i in range(l):
    r, s = map(int, input().split())
    r, s = map(find_train, [r, s])
    r, s = sorted((r, s))
    if r != s:
        train[s] = r
        train = [r if (x > 0) & (x == train[s]) else x for x in train]
train = [i if x < 0 else x for i, x in enumerate(train)]

keys = []
dic  = {}

for node in range(n):
    key = (find_load(load[node + 1]), find_train(train[node + 1]))
    keys.append(key)
    if key in dic:
        dic[key] += 1
    else:
        dic[key] = 1

ans = [str(dic[key]) for key in keys]
print(" ".join(ans))

Submission status: Time Limit Exceeded

Solution code:
n, k, l = map(int, input().split())
load = list(range(n + 1))
train = list(range(n + 1))

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

for i in range(k):
    p, q = map(int, input().split())
    rp = find(p, load)
    rq = find(q, load)
    if rp != rq:
        root = min(rp, rq)
        load[q] = root
        load[p] = root
        load[rp] = root
        load[rq] = root
load = [find(x,load) for x in load]

for i in range(l):
    r, s = map(int, input().split())
    rr = find(r, train)
    rs = find(s, train)
    if rr != rs:
        root = min(rr, rs)
        train[s] = root
        train[r] = root
        train[rr] = root
        train[rs] = root
train = [find(x,train) for x in train]


ans = []
for x, y in zip(load, train):
    if x == -1 or y == -1:
        ans.append(1)
    else:
        ans.append(sum([(x == X and y == Y) for X, Y in zip(load,train)]))

print(*ans[1:])

Submission status: Time Limit Exceeded

Solution code:
n, k, l = map(int, input().split())
load = list(range(n + 1))
train = list(range(n + 1))

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

for i in range(k):
    p, q = map(int, input().split())
    rp = find(p, load)
    rq = find(q, load)
    if rp != rq:
        root = min(rp, rq)
        load = [root if (x==p)|(x==q)|(x==rq)|(x==rp) else x for x in load]

for i in range(l):
    r, s = map(int, input().split())
    rr = find(r, train)
    rs = find(s, train)
    if rr != rs:
        root = min(rr, rs)
        train = [root if (x==r)|(x==s)|(x==rr)|(x==rs) else x for x in train]

ans = []
for x, y in zip(load, train):
    if x == -1 or y == -1:
        ans.append(1)
    else:
        ans.append(sum([(x == X and y == Y) for X, Y in zip(load,train)]))

print(*ans[1:])

Submission status: Time Limit Exceeded

Solution code:
n, k, l = map(int, input().split())
load = list(range(n + 1))
train = list(range(n + 1))

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

for i in range(k):
    p, q = map(int, input().split())
    rp = find(p, load)
    rq = find(q, load)
    if rp != rq:
        root = min(rp, rq)
        load = [root if (x==p)|(x==q)|(x==rq)|(x==rp) else x for x in load]

for i in range(l):
    r, s = map(int, input().split())
    rr = find(r, train)
    rs = find(s, train)
    if r != s:
        root = min(rr, rs)
        train = [root if (x==r)|(x==s)|(x==rr)|(x==rs) else x for x in train]

ans = []
for x, y in zip(load, train):
    if x == -1 or y == -1:
        ans.append(1)
    else:
        ans.append(sum([(x == X and y == Y) for X, Y in zip(load,train)]))

print(*ans[1:])

Submission status: Time Limit Exceeded

Solution code:
n, k, l = map(int, input().split())
load = [-1] * (n + 1)
train = [-1] * (n + 1)

def find_load(x, u = load):
    if u[x] < 0 :
        return x
    else:
        return find_load(u[x])

def find_train(x, u = train):
    if u[x] < 0 :
        return x
    else:
        return find_train(u[x])

for i in range(k):
    p, q = map(int, input().split())
    p, q = map(find_load, [p, q])
    p, q = sorted((p, q))
    if p != q:
        load[q] = p
        load = [p if (x > 0) & (x == load[p]) else x for x in load]
load = [i if x < 0 else x for i, x in enumerate(load)]

for i in range(l):
    r, s = map(int, input().split())
    r, s = map(find_train, [r, s])
    r, s = sorted((r, s))
    if r != s:
        train[s] = r
        train = [r if (x > 0) & (x == train[s]) else x for x in train]
train = [i if x < 0 else x for i, x in enumerate(train)]

ans = []
for x, y in zip(load, train):
    if x == -1 or y == -1:
        ans.append(1)
    else:
        ans.append(sum([(x == X and y == Y) for X, Y in zip(load,train)]))

print(*ans[1:])

Submission status: Time Limit Exceeded

Solution code:
n, k, l = map(int, input().split())
load = [-1] * (n + 1)
train = [-1] * (n + 1)

def find_load(x, u = load):
    if u[x] < 0 :
        return x
    else:
        return find_load(u[x])

def find_train(x, u = train):
    if u[x] < 0 :
        return x
    else:
        return find_train(u[x])

for i in range(k):
    p, q = map(int, input().split())
    p, q = map(find_load, [p, q])
    p, q = sorted((p, q))
    if p != q:
        load[q] = p

for i in range(l):
    r, s = map(int, input().split())
    r, s = map(find_train, [r, s])
    r, s = sorted((r, s))
    if r != s:
        train[s] = r

load = [i if x < 0 else find_load(x) for i, x in enumerate(load)]

train = [i if x < 0 else find_train(x) for i, x in enumerate(train)]

ans = []
for x, y in zip(load, train):
    if x == -1 or y == -1:
        ans.append(1)
    else:
        ans.append(sum([(x == X and y == Y) for X, Y in zip(load,train)]))

print(*ans[1:])

Submission status: Time Limit Exceeded

Solution code:
n, k, l = map(int, input().split())
load = [-1] * (n + 1)
train = [-1] * (n + 1)

def find_load(x, u = load):
    if u[x] < 0 :
        return x
    else:
        return find_load(u[x])

def find_train(x, u = train):
    if u[x] < 0 :
        return x
    else:
        return find_train(u[x])

for i in range(k):
    p, q = map(int, input().split())
    p, q = map(find_load, [p, q])
    p, q = sorted((p, q))
    if p != q:
        load[p] += load[q]
        load[q] = p

for i in range(l):
    r, s = map(int, input().split())
    r, s = map(find_train, [r, s])
    r, s = sorted((r, s))
    if r != s:
        train[r] += train[s]
        train[s] = r

load = [i if x < 0 else find_load(x) for i, x in enumerate(load)]

train = [i if x < 0 else find_train(x) for i, x in enumerate(train)]

ans = []
for x, y in zip(load, train):
    if x == -1 or y == -1:
        ans.append(1)
    else:
        ans.append(sum([(x == X and y == Y) for X, Y in zip(load,train)]))

print(*ans[1:])

Submission status: Time Limit Exceeded

Solution code:
n, k, l = map(int, input().split())
load = [-1] * (n + 1)
train = [-1] * (n + 1)

def find_load(x, u = load):
    if u[x] < 0 :
        return x
    else:
        return find_load(u[x])

def find_train(x, u = train):
    if u[x] < 0 :
        return x
    else:
        return find_train(u[x])

for i in range(k):
    p, q = map(int, input().split())
    p, q = map(find_load, [p, q])
    p, q = sorted((p, q))
    if p != q:
        load[p] += load[q]
        load[q] = p

for i in range(l):
    r, s = map(int, input().split())
    r, s = map(find_train, [r, s])
    r, s = sorted((r, s))
    if r != s:
        train[r] += train[s]
        train[s] = r

load = [find_load(x) if x > 0 else x for x in load]

train = [find_train(x) if x > 0 else x for x in train]

load = [i if x < 0 else x for i, x in enumerate(load)]

train = [i if x < 0 else x for i, x in enumerate(train)]

ans = []
for x, y in zip(load, train):
    if x == -1 or y == -1:
        ans.append(1)
    else:
        ans.append(sum([(x == X and y == Y) for X, Y in zip(load,train)]))

print(*ans[1:])

Submission status: Time Limit Exceeded

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

class Unionfind:

    __slots__ = ['nodes','size']

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

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

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

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

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

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

for _ in range(K):
    p,q = map(int,input().split())
    p -= 1; q -= 1
    uf1.unite(p,q)

for _ in range(L):
    r,s = map(int,input().split())
    r -= 1; s -= 1
    uf2.unite(r,s)

set1 = [set() for _ in range(N)]
set2 = [set() for _ in range(N)]

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

for node in range(N):
    out = len(set1[node] & set2[node])
    if node == N-1:
        print(out)
    else:
        print(out,end = " ")

Submission status: Time Limit Exceeded

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

class Unionfind:

    __slots__ = ['nodes','size']

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

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

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

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

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

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

for _ in range(K):
    p,q = map(int,input().split())
    p -= 1; q -= 1
    uf1.unite(p,q)

for _ in range(L):
    r,s = map(int,input().split())
    r -= 1; s -= 1
    uf2.unite(r,s)

set1 = [set() for _ in range(N)]
set2 = [set() for _ in range(N)]

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

for node,s1,s2 in zip(range(N),set1,set2):
    out = len(s1 & s2)
    if node == N-1:
        print(out)
    else:
        print(out,end = " ")

Submission status: Time Limit Exceeded

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

class Unionfind:

    __slots__ = ['nodes','size']

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

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

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

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

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

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

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

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

set1 = [set() for _ in range(N)]
set2 = [set() for _ in range(N)]

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

ans = []

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

print(" ".join(ans))

Submission status: Time Limit Exceeded

Solution code:
import collections


class UnitDict(dict):

    def __init__(self, iterable=None, wrapper=lambda x: x):
        super().__init__(self)
        self.wrapper = wrapper
        if iterable is not None:
            self.update(iterable)

    def __missing__(self, key):
        self[key] = self.wrapper(key)
        return self[key]


class UnionFind(object):

    def __init__(self, nodes=None):
        self.par = UnitDict(wrapper=lambda x: x)
        self.rank = collections.defaultdict(int)
        self.groups = UnitDict(wrapper=lambda x: {x})
        if nodes is not None:
            for node in nodes:
                _, _, _ = self.par[node], self.rank[node], self.groups[node]

    def root(self, node):
        if self.par[node] == node:
            return node
        else:
            r = self.root(self.par[node])
            self.par[node] = r
            return r

    def unite(self, node1, node2):
        x = self.root(node1)
        y = self.root(node2)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            self.par[y] = x
            self.groups[x].update(self.groups[y])
            self.groups[y].clear()
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


N, K, L = map(int, input().split())
graph_road = UnionFind(range(N))
graph_train = UnionFind(range(N))
for k in range(K):
    p, q = map(int, input().split())
    graph_road.unite(p-1, q-1)

for l in range(L):
    r, s = map(int, input().split())
    graph_train.unite(r-1, s-1)

pair = collections.defaultdict(int)
for i in range(N):
    road = graph_road.root(i)
    train = graph_train.root(i)
    pair[(road, train)] += 1

for i in range(N):
    road = graph_road.root(i)
    train = graph_train.root(i)
    print(pair[(road, train)])

Submission status: Time Limit Exceeded

Solution code:
import collections


class UnitDict(dict):

    def __init__(self, iterable=None, wrapper=lambda x: x):
        super().__init__(self)
        self.wrapper = wrapper
        if iterable is not None:
            self.update(iterable)

    def __missing__(self, key):
        self[key] = self.wrapper(key)
        return self[key]


class UnionFind(object):

    def __init__(self, nodes=None):
        self.par = UnitDict(wrapper=lambda x: x)
        self.rank = collections.defaultdict(int)
        self.groups = UnitDict(wrapper=lambda x: {x})
        if nodes is not None:
            for node in nodes:
                _, _, _ = self.par[node], self.rank[node], self.groups[node]

    def root(self, node):
        if self.par[node] == node:
            return node
        else:
            r = self.root(self.par[node])
            self.par[node] = r
            return r

    def are_same(self, node1, node2):
        return self.root(node1) == self.root(node2)

    def elements(self, node):
        return self.groups[self.root(node)]

    def size(self, node):
        return len(self.elements(node))

    def unite(self, node1, node2):
        x = self.root(node1)
        y = self.root(node2)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            self.par[y] = x
            self.groups[x].update(self.groups[y])
            self.groups[y].clear()
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def grouper(self):
        roots = [x for x in self.par.keys()]
        groups = []
        for root in roots:
            if list(self.elements(root)) not in groups:
                groups.append(list(self.elements(root)))
        return groups


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


graph_road = UnionFind(range(N))
graph_train = UnionFind(range(N))
for k in range(K):
    p, q = map(int, input().split())
    graph_road.unite(p-1, q-1)

for l in range(L):
    r, s = map(int, input().split())
    graph_train.unite(r-1, s-1)

pair = collections.defaultdict(int)
for i in range(N):
    road = graph_road.root(i)
    train = graph_train.root(i)
    pair[(road, train)] += 1

for i in range(N):
    road = graph_road.root(i)
    train = graph_train.root(i)
    print(pair[(road, train)])

Submission status: Time Limit Exceeded

Solution code:
import collections


class UnitDict(dict):

    def __init__(self, iterable=None, wrapper=lambda x: x):
        super().__init__(self)
        self.wrapper = wrapper
        if iterable is not None:
            self.update(iterable)

    def __missing__(self, key):
        self[key] = self.wrapper(key)
        return self[key]


class UnionFind(object):

    def __init__(self, nodes=None):
        self.par = UnitDict(wrapper=lambda x: x)
        self.rank = collections.defaultdict(int)
        self.groups = UnitDict(wrapper=lambda x: {x})
        if nodes is not None:
            for node in nodes:
                _, _, _ = self.par[node], self.rank[node], self.groups[node]

    def root(self, node):
        if self.par[node] == node:
            return node
        else:
            r = self.root(self.par[node])
            self.par[node] = r
            return r

    def are_same(self, node1, node2):
        return self.root(node1) == self.root(node2)

    def elements(self, node):
        return self.groups[self.root(node)]

    def size(self, node):
        return len(self.elements(node))

    def unite(self, node1, node2):
        x = self.root(node1)
        y = self.root(node2)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            self.par[y] = x
            self.groups[x].update(self.groups[y])
            self.groups[y].clear()
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def grouper(self):
        roots = [x for x in self.par.keys()]
        groups = []
        for root in roots:
            if list(self.elements(root)) not in groups:
                groups.append(list(self.elements(root)))
        return groups


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


graph_road = UnionFind(range(N))
graph_train = UnionFind(range(N))
for k in range(K):
    p, q = map(int, input().split())
    graph_road.unite(p-1, q-1)

for l in range(L):
    r, s = map(int, input().split())
    graph_train.unite(r-1, s-1)

for i in range(N):
    ans = 0
    road = graph_road.elements(i)
    train = graph_train.elements(i)
    ans += len(set(road) & set(train))
    print(ans)