Problem:


Score : 400 points

Problem Statement

There are N cities. There are also K roads and L railways, extending between the cities.
The i-th road bidirectionally connects the p_i-th and q_i-th cities, and the i-th railway bidirectionally connects the r_i-th and s_i-th cities.
No two roads connect the same pair of cities. Similarly, no two railways connect the same pair of cities.

We will say city A and B are connected by roads if city B is reachable from city A by traversing some number of roads. Here, any city is considered to be connected to itself by roads.
We will also define connectivity by railways similarly.

For each city, find the number of the cities connected to that city by both roads and railways.

Constraints

2 ≦ N ≦ 2*10^5

1 ≦ K, L≦ 10^5

1 ≦ p_i, q_i, r_i, s_i ≦ N

p_i < q_i

r_i < s_i

When i ≠ j, (p_i, q_i) ≠ (p_j, q_j)

When i ≠ j, (r_i, s_i) ≠ (r_j, s_j)

Input

The input is given from Standard Input in the following format:

N K L
p_1 q_1
:
p_K q_K
r_1 s_1
:
r_L s_L

Output

Print N integers. The i-th of them should represent the number of the cities connected to the i-th city by both roads and railways.

Sample Input 1

4 3 1
1 2
2 3
3 4
2 3

Sample Output 1

1 2 2 1

All the four cities are connected to each other by roads.

By railways, only the second and third cities are connected. Thus, the answers for the cities are 1, 2, 2 and 1, respectively.

Sample Input 2

4 2 2
1 2
2 3
1 4
2 3

Sample Output 2

1 2 2 1

Sample Input 3

7 4 4
1 2
2 3
2 5
6 7
3 5
4 5
3 4
6 7

Sample Output 3

1 1 2 1 2 2 2



Sample input:
4 3 1
1 2
2 3
3 4
2 3


Sample output:
1 2 2 1

Submission status: Time Limit Exceeded

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


class UFT:
    def __init__(self, N):
        self.UFdata = [-1] * (N+1)
        self.rank   = [0]  * (N+1)

    def find(self,x):
        UFdata = self.UFdata
        while UFdata[x] != -1:
            x = UFdata[x]
        return x

    def unite(self,x,y):
        UFdata = self.UFdata
        rank = self.rank 
        find = self.find

        x = find(x)
        y = find(y)
        if x != y:
            if rank[x] < rank[y]:
                x,y = y,x
            if rank[x] == rank[y]:
                rank[x] += 1
            UFdata[y] = x       
            

UF1 = UFT(N)
UF2 = UFT(N)
ans = [1] * (N+1)
MAP= [ [0] * (N+1) for _ in range(N+1)]
import sys
input = sys.stdin.readline
PQ = [ [int(j) for j in input().split()] for _ in range(K)]
RS = [ [int(j) for j in input().split()] for _ in range(L)]

for i in range(K):
    p,q = PQ[i]
    UF1.unite(p,q)
for i in range(L):
    p,q = RS[i]
    UF2.unite(p, q)
counter=[]
for i in range(1,N+1):
  counter.append(UF1.find(i)+UF2.find(i)*10**6)
from collections import Counter  
p=Counter(counter)

ans = [0]*(N+1)
for i in range(1,N+1):
    ans[i] = p[UF1.find(i)+UF2.find(i)*10**6]

del ans[0]
# print(" ".join( map(lambda x: str(x), connected_num[1:])))
print(" ".join( map(lambda x: str(x), ans)))

Submission status: Time Limit Exceeded

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


class UFT:
    def __init__(self, N):
        self.UFdata = [-1] * (N+1)
        self.rank   = [0]  * (N+1)
        self.connected_num = [1] * (N+1)

    def find(self,x):
        UFdata = self.UFdata
        while UFdata[x] != -1:
            x = UFdata[x]
        return x

    def unite(self,x,y):
        UFdata = self.UFdata
        rank = self.rank
        connected_num = self.connected_num
        find = self.find

        x = find(x)
        y = find(y)
        if x != y:
            if rank[x] < rank[y]:
                x,y = y,x
            if rank[x] == rank[y]:
                rank[x] += 1
            UFdata[y] = x       
            

UF1 = UFT(N)
UF2 = UFT(N)
ans = [1] * (N+1)
MAP= [ [0] * (N+1) for _ in range(N+1)]
import sys
input = sys.stdin.readline
PQ = [ [int(j) for j in input().split()] for _ in range(K)]
RS = [ [int(j) for j in input().split()] for _ in range(L)]

for i in range(K):
    p,q = PQ[i]
    UF1.unite(p,q)
for i in range(L):
    p,q = RS[i]
    UF2.unite(p, q)
counter=[]
for i in range(1,N+1):
  counter.append((UF1.find(i),UF2.find(i)))
from collections import Counter  
p=Counter(counter)

ans = [0]*(N+1)
for i in range(1,N+1):
    ans[i] = p[(UF1.find(i),UF2.find(i))]

del ans[0]
# print(" ".join( map(lambda x: str(x), connected_num[1:])))
print(" ".join( map(lambda x: str(x), ans)))

Submission status: Time Limit Exceeded

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


class UFT:
    def __init__(self, N):
        self.UFdata = [-1] * (N+1)
        self.rank   = [0]  * (N+1)
        self.connected_num = [1] * (N+1)

    def find(self,x):
        UFdata = self.UFdata
        while UFdata[x] != -1:
            x = UFdata[x]
        return x

    def unite(self,x,y):
        UFdata = self.UFdata
        rank = self.rank
        connected_num = self.connected_num
        find = self.find

        x = find(x)
        y = find(y)
        if x != y:
            if rank[x] < rank[y]:
                UFdata[x] = UFdata[y]
                x,y = y,x
            if rank[x] == rank[y]:
                rank[x] += 1
            UFdata[y] = x       
            connected_num[x] += connected_num[y]
            

UF1 = UFT(N)
UF2 = UFT(N)
ans = [1] * (N+1)
MAP= [ [0] * (N+1) for _ in range(N+1)]
import sys
input = sys.stdin.readline
PQ = [ [int(j) for j in input().split()] for _ in range(K)]
RS = [ [int(j) for j in input().split()] for _ in range(L)]

for i in range(K):
    p,q = PQ[i]
    UF1.unite(p,q)
for i in range(L):
    p,q = RS[i]
    UF2.unite(p, q)
counter=[]
for i in range(1,N+1):
  counter.append((UF1.find(i),UF2.find(i)))
from collections import Counter  
p=Counter(counter)

ans = [0]*(N+1)
for i in range(1,N+1):
    ans[i] = p[(UF1.find(i),UF2.find(i))]

del ans[0]
# print(" ".join( map(lambda x: str(x), connected_num[1:])))
print(" ".join( map(lambda x: str(x), ans)))

Submission status: Time Limit Exceeded

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


class UFT:
    def __init__(self, N):
        self.UFdata = [-1] * (N+1)
        self.rank   = [0]  * (N+1)
        self.connected_num = [1] * (N+1)

    def find(self,x):
        UFdata = self.UFdata
        while UFdata[x] != -1:
            x = UFdata[x]
        return x

    def unite(self,x,y):
        UFdata = self.UFdata
        rank = self.rank
        connected_num = self.connected_num
        find = self.find

        x = find(x)
        y = find(y)
        if x != y:
            if rank[x] < rank[y]:
                UFdata[x] = UFdata[y]
                x,y = y,x
            if rank[x] == rank[y]:
                rank[x] += 1
            UFdata[y] = x       
            connected_num[x] += connected_num[y]
            

UF1 = UFT(N)
UF2 = UFT(N)
ans = [1] * (N+1)
MAP= [ [0] * (N+1) for _ in range(N+1)]
import sys
input = sys.stdin.readline
PQ = [ [int(j) for j in input().split()] for _ in range(K)]
RS = [ [int(j) for j in input().split()] for _ in range(L)]

for i in range(K):
    p,q = PQ[i]
    if UF1.find(p) != -1 and UF1.find(p) != UF1.find(q)  or UF1.find(p) == UF1.find(q) == -1:
        UF1.unite(p,q)

    

for i in range(L):
    p,q = RS[i]

    if UF1.find(p) != -1 and UF1.find(p) == UF1.find(q) :
        UF2.unite(p, q)

ans = [0]*(N+1)
par_idx = [0]*(N+1)
for i in range(1,N+1):
    par_idx[i] = UF2.find(i)
for i in range(1,N+1):
    ans[i] = UF2.connected_num[par_idx[i]]

del ans[0]
# print(" ".join( map(lambda x: str(x), connected_num[1:])))
print(" ".join( map(lambda x: str(x), ans)))

Submission status: Time Limit Exceeded

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


class UFT:
    def __init__(self, N):
        self.UFdata = [-1] * (N+1)
        self.rank   = [0]  * (N+1)
        self.connected_num = [1] * (N+1)

    def find(self,x):
        UFdata = self.UFdata
        while UFdata[x] != -1:
            x = UFdata[x]
        return x

    def unite(self,x,y):
        UFdata = self.UFdata
        rank = self.rank
        connected_num = self.connected_num
        find = self.find

        x = find(x)
        y = find(y)
        if x != y:
            if rank[x] < rank[y]:
                UFdata[x] = UFdata[y]
                x,y = y,x
            if rank[x] == rank[y]:
                rank[x] += 1
            UFdata[y] = x       
            connected_num[x] += connected_num[y]
            

UF1 = UFT(N)
UF2 = UFT(N)
ans = [1] * (N+1)
MAP= [ [0] * (N+1) for _ in range(N+1)]
import sys
input = sys.stdin.readline
PQ = [ [int(j) for j in input().split()] for _ in range(K)]
RS = [ [int(j) for j in input().split()] for _ in range(L)]

for i in range(K):
    p,q = PQ[i]
    if UF1.find(p) != -1 and UF1.find(p) != UF1.find(q)  or UF1.find(p) == UF1.find(q) == -1:
        UF1.unite(p,q)

    

for i in range(L):
    p,q = RS[i]

    if UF1.find(p) != -1 and UF1.find(p) == UF1.find(q) :
        UF2.unite(p, q)

ans = [0]*(N+1)
for i in range(1,N+1):
    # ans.append (  UF2.connected_num[ UF2.find( i) ] )
    ans[i] = UF2.connected_num[UF2.find(i)]

del ans[0]
# print(" ".join( map(lambda x: str(x), connected_num[1:])))
print(" ".join( map(lambda x: str(x), ans)))

Submission status: Time Limit Exceeded

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


class UFT:
    def __init__(self, N):
        self.UFdata = [-1] * (N+1)
        self.rank   = [0]  * (N+1)
        self.connected_num = [1] * (N+1)

    def find(self,x):
        UFdata = self.UFdata
        while UFdata[x] != -1:
            x = UFdata[x]
        return x

    def unite(self,x,y):
        UFdata = self.UFdata
        rank = self.rank
        connected_num = self.connected_num
        find = self.find

        x = find(x)
        y = find(y)
        if x != y:
            if rank[x] < rank[y]:
                UFdata[x] = UFdata[y]
                x,y = y,x
            if rank[x] == rank[y]:
                rank[x] += 1
            UFdata[y] = x       
            connected_num[x] += connected_num[y]
            

UF1 = UFT(N)
UF2 = UFT(N)
ans = [1] * (N+1)
MAP= [ [0] * (N+1) for _ in range(N+1)]
import sys
input = sys.stdin.readline
PQ = [ [int(j) for j in input().split()] for _ in range(K)]
RS = [ [int(j) for j in input().split()] for _ in range(L)]

for i in range(K):
    p,q = PQ[i]
    if UF1.find(p) != -1 and UF1.find(p) != UF1.find(q)  or UF1.find(p) == UF1.find(q) == -1:
        UF1.unite(p,q)

    

for i in range(L):
    p,q = RS[i]

    if UF1.find(p) != -1 and UF1.find(p) == UF1.find(q) :
        UF2.unite(p, q)

ans = []
for i in range(1,N+1):
    ans.append (  UF2.connected_num[ UF2.find( i) ] )

# print(" ".join( map(lambda x: str(x), connected_num[1:])))
print(" ".join( map(lambda x: str(x), ans)))

Submission status: Time Limit Exceeded

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


class UFT:
    def __init__(self, N):
        self.UFdata = [-1] * (N+1)
        self.rank   = [0]  * (N+1)
        self.connected_num = [1] * (N+1)

    def find(self,x):
        UFdata = self.UFdata
        while UFdata[x] != -1:
            x = UFdata[x]
        return x

    def unite(self,x,y):
        UFdata = self.UFdata
        rank = self.rank
        connected_num = self.connected_num
        find = self.find

        x = find(x)
        y = find(y)
        if x != y:
            if rank[x] < rank[y]:
                UFdata[x] = UFdata[y]
                x,y = y,x
            if rank[x] == rank[y]:
                rank[x] += 1
            UFdata[y] = x       
            connected_num[x] += connected_num[y]
            

UF1 = UFT(N)
UF2 = UFT(N)
ans = [1] * (N+1)
MAP= [ [0] * (N+1) for _ in range(N+1)]
import sys
input = sys.stdin.readline
PQ = [ [int(j) for j in input().split()] for _ in range(K)]
RS = [ [int(j) for j in input().split()] for _ in range(L)]

for i in range(K):
    # p,q = map(int, input().split())
    p,q = PQ[i]
    mn, mx = min(p,q), max(p,q)
    if UF1.find(p) != -1 and UF1.find(p) != UF1.find(q)  or UF1.find(p) == UF1.find(q) == -1:
        UF1.unite(p,q)

    

for i in range(L):
    # p,q = map(int, input().split())
    p,q = RS[i]
    mn, mx = min(p,q), max(p,q)

    if UF1.find(p) != -1 and UF1.find(p) == UF1.find(q) :
        UF2.unite(mn, mx)

ans = []
for i in range(1,N+1):
    ans.append (  UF2.connected_num[ UF2.find( i) ] )

# print(" ".join( map(lambda x: str(x), connected_num[1:])))
print(" ".join( map(lambda x: str(x), ans)))

Submission status: Time Limit Exceeded

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


class UFT:
    def __init__(self, N):
        self.UFdata = [-1] * (N+1)
        self.rank   = [0]  * (N+1)
        self.connected_num = [1] * (N+1)

    def find(self,x):
        UFdata = self.UFdata
        while UFdata[x] != -1:
            x = UFdata[x]
        return x

    def unite(self,x,y):
        UFdata = self.UFdata
        rank = self.rank
        connected_num = self.connected_num
        find = self.find

        x = find(x)
        y = find(y)
        if x != y:
            if rank[x] < rank[y]:
                UFdata[x] = UFdata[y]
                x,y = y,x
            if rank[x] == rank[y]:
                rank[x] += 1
            UFdata[y] = x       
            connected_num[x] += connected_num[y]
            

UF1 = UFT(N)
UF2 = UFT(N)
ans = [1] * (N+1)
MAP= [ [0] * (N+1) for _ in range(N+1)]

for i in range(K):
    p,q = map(int, input().split())
    mn, mx = min(p,q), max(p,q)
    if UF1.find(p) != -1 and UF1.find(p) != UF1.find(q)  or UF1.find(p) == UF1.find(q) == -1:
        UF1.unite(p,q)

    

for i in range(L):
    p,q = map(int, input().split())
    mn, mx = min(p,q), max(p,q)

    if UF1.find(p) != -1 and UF1.find(p) == UF1.find(q) :
        UF2.unite(mn, mx)

ans = []
for i in range(1,N+1):
    ans.append (  UF2.connected_num[ UF2.find( i) ] )

# print(" ".join( map(lambda x: str(x), connected_num[1:])))
print(" ".join( map(lambda x: str(x), ans)))

Submission status: Time Limit Exceeded

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class UnionFind:
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[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.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

    def __str__(self):
        ret = "parents\n"
        ret += " ".join(map(str, self.parent))
        ret += '\n'
        ret += " ".join(map(str, self.rank))
        return ret


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


def solve1():
    root = UnionFind(N)
    train = UnionFind(N)

    for _ in range(K):
        a, b = map(lambda x: int(x)-1, input().split())
        root.union(a, b)

    for _ in range(L):
        a, b = map(lambda x: int(x)-1, input().split())
        train.union(a, b)
    ans = [1]*N
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            else:
                if root.same(i, j) and train.same(i, j):
                    ans[i] += 1
    print(" ".join(map(str, ans)))


def solve2():
    ans = [0]*N
    root = UnionFind(N)
    train = UnionFind(N)
    for _ in range(K):
        a, b = map(lambda x: int(x)-1, input().split())
        root.union(a, b)

    for _ in range(L):
        a, b = map(lambda x: int(x)-1, input().split())
        train.union(a, b)

    par = [0]*N
    d = 10**6
    for i in range(N):
        par[i] = root.find(i)+train.find(i)*d
    s = set(par)
    nums = dict()
    for c in s:
        nums[c] = par.count(c)
    for i in range(N):
        ans[i] = nums[root.find(i)+train.find(i)*d]

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


solve2()

Submission status: Time Limit Exceeded

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class UnionFind:
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[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.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

    def __str__(self):
        ret = "parents\n"
        ret += " ".join(map(str, self.parent))
        ret += '\n'
        ret += " ".join(map(str, self.rank))
        return ret


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


def solve1():
    root = UnionFind(N)
    train = UnionFind(N)

    for _ in range(K):
        a, b = map(lambda x: int(x)-1, input().split())
        root.union(a, b)

    for _ in range(L):
        a, b = map(lambda x: int(x)-1, input().split())
        train.union(a, b)
    ans = [1]*N
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            else:
                if root.same(i, j) and train.same(i, j):
                    ans[i] += 1
    print(" ".join(map(str, ans)))


def solve2():
    ans = [0]*N
    root = UnionFind(N)
    train = UnionFind(N)
    for _ in range(K):
        a, b = map(lambda x: int(x)-1, input().split())
        root.union(a, b)

    for _ in range(L):
        a, b = map(lambda x: int(x)-1, input().split())
        if root.same(a, b):
            train.union(a, b)

    parent = [0]*N
    for i in range(N):
        p = train.find(i)
        parent[p] += 1
    for i in range(N):
        ans[i] = parent[train.find(i)]
    print(" ".join(map(str, ans)))


solve1()
#solve2()

Submission status: Time Limit Exceeded

Solution code:
import sys

n,k,l=map(int,sys.stdin.readline().split())
pk=list(range(n))
rk=[set([i]) for i in range(n)]
pl=pk[:]
rl=rk[:]

def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]

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

def union(x,y,parent,road):
    x,y = find(x,parent),find(y,parent)
    parent[y] = x
    road[x] = road[x] | road[y]
    road[y] = road[x]


for i in range(k):
    a,b = LI_()
    if find(a,pk) != find(b,pk):
        union(a,b,pk,rk)

for i in range(l):
    a,b = LI_()
    if find(a,pl) != find(b,pl):
        union(a,b,pl,rl)

for i in range(n):
    print(len(rk[find(i,pk)] & rl[find(i,pl)]),end=" ")
print()

Submission status: Time Limit Exceeded

Solution code:
import sys

n,k,l=map(int,sys.stdin.readline().split())
pk=list(range(n))
rk=[set([i]) for i in range(n)]
pl=pk[:]
rl=rk[:]

def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]

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

def union(x,y,parent,road):
    x,y = find(x,parent),find(y,parent)
    parent[y] = x
    road[x] = road[x] | road[y]
    road[y] = road[x] | road[y]


for i in range(k):
    a,b = LI_()
    if find(a,pk) != find(b,pk):
        union(a,b,pk,rk)

for i in range(l):
    a,b = LI_()
    if find(a,pl) != find(b,pl):
        union(a,b,pl,rl)

for i in range(n):
    print(len(rk[find(i,pk)] & rl[find(i,pl)]),end=" ")
print()

Submission status: Time Limit Exceeded

Solution code:
import sys

n,k,l=map(int,sys.stdin.readline().split())
pk=list(range(n))
rk=[set([i]) for i in range(n)]
pl=list(range(n))
rl=[set([i]) for i in range(n)]

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

def union(x,y,parent,road):
    x,y = find(x,parent),find(y,parent)
    parent[y] = x
    road[x] = road[x] | road[y]
    road[y] = road[x] | road[y]


for i in range(k):
    a,b = map(int,sys.stdin.readline().split())
    if find(a-1,pk) != find(b-1,pk):
        union(a-1,b-1,pk,rk)

for i in range(l):
    a,b = map(int,sys.stdin.readline().split())
    if find(a-1,pl) != find(b-1,pl):
        union(a-1,b-1,pl,rl)

for i in range(n):
    print(len(rk[find(i,pk)] & rl[find(i,pl)]),end=" ")

Submission status: Time Limit Exceeded

Solution code:
import sys

n,k,l=map(int,sys.stdin.readline().split())
klist = [[] for i in range(k)]
llist = [[] for i in range(l)]
for i in range(k):
    a,b = map(int,sys.stdin.readline().split())
    klist[i] = [a-1,b-1]
for i in range(l):
    a,b = map(int,sys.stdin.readline().split())
    llist[i] = [a-1,b-1]

pk=list(range(n))
rk=[0]*n
pl=list(range(n))
rl=[0]*n

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

def union(x,y,parent,road):
    x,y = find(x,parent),find(y,parent)
    if road[y] > road[x]: x,y = y,x
    parent[y] = x
    road[x] += road[x] == road[y]
    
def research(x,parent):
    x = find(x,parent)
    res = set()
    for i in range(n):
        if x == parent[i]:
            res.add(i)
    return res

for a,b in klist:
    if find(a,pk) != find(b,pk):
        union(a,b,pk,rk)

for a,b in llist:
    if find(a,pl) != find(b,pl):
        union(a,b,pl,rl)

for i in range(n):
    tmp1 = research(i,pk)
    tmp2 = research(i,pl)
    tmp3 = tmp1 & tmp2
    print(len(research(i,pk) & research(i,pl)))

Submission status: Time Limit Exceeded

Solution code:
import sys

n,k,l=map(int,sys.stdin.readline().split())
klist = [[] for i in range(k)]
llist = [[] for i in range(l)]
for i in range(k):
    a,b = map(int,sys.stdin.readline().split())
    klist[i] = [a-1,b-1]
for i in range(l):
    a,b = map(int,sys.stdin.readline().split())
    llist[i] = [a-1,b-1]

pk=list(range(n))
rk=[0]*n
pl=list(range(n))
rl=[0]*n

def findk(x):
    if pk[x] != x:
        pk[x] = findk(pk[x])
    return pk[x]

def unionk(x,y):
    x,y = findk(x),findk(y)
    if rk[x] < rk[y]: x,y=y,x
    pk[y] = x
    rk[x] += rk[x] == rk[y]

def researchk(x):
    x = findk(x)
    res = set()
    for i in range(n):
        if x == pk[i]:
            res.add(i)
    return res

def findl(x):
    if pl[x] != x:
        pl[x] = findl(pl[x])
    return pl[x]

def unionl(x,y):
    x,y = findl(x),findl(y)
    if rl[x] < rl[y]: x,y=y,x
    pl[y] = x
    rl[x] += rl[x] == rl[y]

def researchl(x):
    x = findl(x)
    res = set()
    for i in range(n):
        if x == pl[i]:
            res.add(i)
    return res

for a,b in klist:
    if findk(a) != findk(b):
        unionk(a,b)

for a,b in llist:
    if findl(a) != findl(b):
        unionl(a,b)

for i in range(n):
    tmp1 = researchk(i)
    tmp2 = researchl(i)
    tmp3 = tmp1 & tmp2
    print(len(researchk(i) & researchl(i)))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(1000000)
N, K, L = map(int, input().split())
pq = [list(map(int, input().split())) for _ in range(K)]
rs = [list(map(int, input().split())) for _ in range(L)]

G_r = [[] for _ in range(N+1)]
for elem in pq:
    G_r[elem[0]].append(elem[1])
    G_r[elem[1]].append(elem[0])
G_t = [[] for _ in range(N+1)]
for elem in rs:
    G_t[elem[0]].append(elem[1])
    G_t[elem[1]].append(elem[0])


field_r = [[] for _ in range(N+1)]


def dfs_r(i):
    q = deque()
    q.append(i)
    field_r[i].append(i)
    while q:
        tmp = q.pop()
        for pos in G_r[tmp]:
            if pos not in field_r[i]:
                field_r[i].append(pos)
                q.append(pos)
            else:
                continue
for i in range(1, N+1):
    if not field_r[i]:
        dfs_r(i)

field_t = [[] for _ in range(N+1)]
cnt = [1 for _ in range(N+1)]


def dfs_t(i):
    q = deque()
    q.append(i)
    field_t[i].append(i)
    while q:
        tmp = q.pop()
        for pos in G_t[tmp]:
            if pos not in field_t[i]:
                field_t[i].append(pos)
                if pos in field_r[i]:
                    cnt[i] += 1
                q.append(pos)
            else:
                continue
for i in range(1, N+1):
    if not field_t[i]:
        dfs_t(i)

ans = []
for i in range(1, N+1):
    ans.append(cnt[i])
print(' '.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

class UnionFind:
    def __init__(self, node:int) -> None:
        self.n = node
        self.par = [i for i in range(self.n)]
        self.rank = [0 for i in range(self.n)]
        
    def find(self, x:int) -> int:
        if x == self.par[x]:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    def unite(self, x:int, y:int) -> bool:
        if self.isSame(x,y):
            #print("x and y has already united")
            return False
        
        rx = self.find(x)
        ry = self.find(y)
        
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = self.par[ry]
        else:
            self.par[ry] = self.par[rx]
            
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1
                
        return True
                
    def isSame(self, x:int, y:int) -> bool:
        return self.find(x) == self.find(y)
    
n,k,l = li()
pq = []
rs = []

for _ in range(k):
    pq.append(tuple(li_()))
    
for _ in range(l):
    rs.append(tuple(li_()))

road = UnionFind(n)
rail = UnionFind(n)

for p,q in pq:
    road.unite(p,q)
    
for r,s in rs:
    rail.unite(r,s)
    
for i in range(n):
    road.find(i)
    
for i in range(n):
    rail.find(i)
    
road_dic = {i:set() for i in range(n)}
rail_dic = {i:set() for i in range(n)}

for i in range(n):
    road_dic[road.par[i]].add(i)
    rail_dic[rail.par[i]].add(i)
    
ans = []
for i in range(n):
    ans.append(len(road_dic[road.par[i]] & rail_dic[rail.par[i]]))
    
print(*ans)

Submission status: Time Limit Exceeded

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

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

uf1 = UnionFind(N)
for p,q in P:
    p,q = p-1,q-1
    if uf1.is_same(p,q): continue
    uf1.unite(p,q)

uf2 = UnionFind(N)
for r,s in R:
    r,s = r-1,s-1
    if uf2.is_same(r,s): continue
    uf2.unite(r,s)

r1 = [set() for i in range(N)]
for i in range(N):
    r = uf1.root(i)
    r1[r].add(i)

r2 = [set() for i in range(N)]
for i in range(N):
    r = uf2.root(i)
    r2[r].add(i)

ans = []
for i in range(N):
    a = uf1.root(i)
    b = uf2.root(i)
    ans.append(len(r1[a] & r2[b]))
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

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

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

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


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

road = UnionFind(n)
train = UnionFind(n)

for _ in range(k):
	a, b = map(int, input().split())
	road.union(a - 1, b - 1)

for _ in range(l):
	a, b = map(int, input().split())
	train.union(a - 1, b - 1)

road_root = []
for i in range(n):
	num = road.find(i)
	road_root.append(num)

train_root = []
for i in range(n):
	num = train.find(i)
	train_root.append(num)

count = defaultdict(int)
for i in range(n):
	count[road_root[i] * (10 ** 6) +  train_root[i]] += 1

ans = []
for i in range(n):
	ans.append(count[road_root[i] * (10 ** 6) +  train_root[i]])

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import queue
N,K,L=map(int,input().split())
G=[[] for i in range(N)]
H=[[] for i in range(N)]
#T=[-1 for i in range(N)]
#B=[-1 for i in range(N)]
for i in range(K):
    p,q=map(int,input().split())
    G[p-1].append(q-1)
    G[q-1].append(p-1)
for i in range(L):
    r,s=map(int,input().split())
    H[r-1].append(s-1)
    H[s-1].append(r-1)
def bfs(A):
    k=1
    q=queue.Queue()
    reached=[0 for i in range(N)]
    res=[0 for i in range(N)]
    for i in range(N):
        if reached[i]==1:
            continue
        q.put(i)
        while(not(q.empty())):
            r=q.get()
            res[r]=k
            for p in A[r]:
                if reached[p]==1:
                    continue
                q.put(p)
                reached[p]=1
        k+=1
    return res
T=bfs(G)
B=bfs(H)
TB=[(T[i],B[i]) for i in range(N)]
D=dict()
for i in range(N):
    if TB[i] in D:
        D[TB[i]]+=1
    else:
        D[TB[i]]=1
ans=[str(D[TB[i]]) for i in range(N)]
print(" ".join(ans))

Submission status: Time Limit Exceeded

Solution code:
import queue
N,K,L=map(int,input().split())
G=[[] for i in range(N)]
H=[[] for i in range(N)]
#T=[-1 for i in range(N)]
#B=[-1 for i in range(N)]
for i in range(K):
    p,q=map(int,input().split())
    G[p-1].append(q-1)
    G[q-1].append(p-1)
for i in range(L):
    r,s=map(int,input().split())
    H[r-1].append(s-1)
    H[s-1].append(r-1)
def bfs(A):
    k=0
    q=queue.Queue()
    reached=[0 for i in range(N)]
    res=[-1 for i in range(N)]
    for i in range(N):
        if reached[i]==1:
            continue
        q.put(i)
        while(not(q.empty())):
            r=q.get()
            res[r]=k
            for p in A[r]:
                if reached[p]==1:
                    continue
                q.put(p)
                reached[p]=1
        k+=1
    return res
T=bfs(G)
B=bfs(H)
TB=[(T[i],B[i]) for i in range(N)]
D=dict()
for i in range(N):
    if TB[i] in D:
        D[TB[i]]+=1
    else:
        D[TB[i]]=1
ans=[str(D[TB[i]]) for i in range(N)]
print(" ".join(ans))