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():
    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())
Pl = []
Ql = []
Rl = []
Sl = []
for _ in range(K):
    P,Q = map(int,input().split())
    Pl.append(P-1)
    Ql.append(Q-1)
for _ in range(L):
    R,S = map(int,input().split())
    Rl.append(R-1)
    Sl.append(S-1)
UF_road = UnionFind(N)
for i in range(K):
    UF_road.union(Pl[i],Ql[i])
UF_train = UnionFind(N)
for i in range(L):
    UF_train.union(Rl[i],Sl[i])
s  = ""
for i in range(N):
    s += str(len(set(UF_road.members(i)) & set(UF_train.members(i)))) + " "
print(s[:-1])

Submission status: Time Limit Exceeded

Solution code:
import sys

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())
uf_road = UnionFind(N)
uf_train = UnionFind(N)

for i in range(K):
    p,q = map(int,input().split())
    p -= 1
    q -= 1
    uf_road.union(p,q)

for i in range(L):
    p,q = map(int,input().split())
    p -= 1
    q -= 1
    uf_train.union(p,q)
ans = [0] * N
for g in uf_road.roots():
    for i in uf_road.members(g):
        for j in uf_road.members(g):
            if uf_train.same(i,j):
                ans[i] += 1

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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


# union-findを実装
root_road = [-1] * N
root_train = [-1] * N


def find_road(x):
    if root_road[x] < 0:
        return x

    root_road[x] = find_road(root_road[x])
    return root_road[x]


def union_road(x, y):
    x = find_road(x)
    y = find_road(y)
    if x == y:
        return

    root_road[x] += root_road[y]
    root_road[y] = x


def same_road(x, y):
    return find_road(x) == find_road(y)


def find_train(x):
    if root_train[x] < 0:
        return x

    root_train[x] = find_train(root_train[x])
    return root_train[x]


def union_train(x, y):
    x = find_train(x)
    y = find_train(y)
    if x == y:
        return

    root_train[x] += root_train[y]
    root_train[y] = x


def same_train(x, y):
    return find_train(x) == find_train(y)


dc = defaultdict(list)
dt = defaultdict(list)
for _ in range(K):
    p, q = map(int, input().split())
    p -= 1
    q -= 1
    dc[p].append(q)
    dc[q].append(p)
    union_road(p, q)

for _ in range(L):
    r, s = map(int, input().split())
    r -= 1
    s -= 1
    dt[r].append(s)
    dt[s].append(r)
    union_train(r, s)


ans = [0] * N
for i in range(N):
    for j in range(i + 1, N):
        if same_road(i, j):
            if same_train(i, j) and ans[i] <= 1 and ans[j] <= 1:
                ans[i] = 2
                ans[j] = 2
            elif not same_train(i, j) and ans[i] != 2 and ans[j] != 2:
                ans[i] = 1
                ans[j] = 1

        if same_train(i, j):
            if same_road(i, j):
                ans[i] = 2
                ans[j] = 2
            elif not same_road(i, j) and ans[i] != 2 and ans[j] != 2:
                ans[i] = 1
                ans[j] = 1
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
import os
from operator import mul

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")

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 = LI()
pq = [LI() for _ in range(K)]
rs = [LI() for _ in range(L)]

road = UnionFind(N)
for r in pq:
    f = r[0]-1
    t = r[1]-1
    road.union(f,t)

rail = UnionFind(N)
for r in rs:
    f = r[0]-1
    t = r[1]-1
    rail.union(f,t)

ans = [-1]*N
for i in range(N):
    if not ans[i]==-1:
        continue
    road_set = set(road.members(i))
    rail_set = set(rail.members(i))
    group = road_set & rail_set
    count = len(group)
    for j in group:
        ans[j]=count

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
import os
from operator import mul

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")

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 = LI()
pq = [LI() for _ in range(K)]
rs = [LI() for _ in range(L)]

road = UnionFind(N)
for r in pq:
    f = r[0]-1
    t = r[1]-1
    road.union(f,t)

rail = UnionFind(N)
for r in rs:
    f = r[0]-1
    t = r[1]-1
    rail.union(f,t)

ans = []
for i in range(N):
    road_set = set(road.members(i))
    rail_set = set(rail.members(i))
    count = len(road_set & rail_set)
    ans.append(count)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
N, K, L = map(int, input().split())
links1 = [tuple(map(int, input().split())) for _ in range(K)]
links2 = [tuple(map(int, input().split())) for _ in range(L)]

linked1 = {i: set([i]) for i in range(1, N + 1)}
linked2 = {i: set([i]) for i in range(1, N + 1)}

for p, q in links1:
    set1 = linked1[p]
    set2 = linked1[q]
    set1 |= set2
    for i in set2:
        linked1[i] = set1

for r, s in links2:
    set1 = linked2[r]
    set2 = linked2[s]
    set1 |= set2
    for i in set2:
        linked2[i] = set1

counts = []
for n in range(1, N + 1):
    set1 = linked1[n]
    set2 = linked2[n]
    counts.append(str(len(set1.intersection(set2))))

print(' '.join(counts))

Submission status: Time Limit Exceeded

Solution code:
N, K, L = map(int, input().split())
links1 = [tuple(map(int, input().split())) for _ in range(K)]
links2 = [tuple(map(int, input().split())) for _ in range(L)]

linked1 = {i: set([i]) for i in range(1, N + 1)}
linked2 = {i: set([i]) for i in range(1, N + 1)}

for p, q in links1:
    set1 = linked1[p]
    set2 = linked1[q]
    merged = set1.union(set2)
    for i in merged:
        linked1[i] = merged

for r, s in links2:
    set1 = linked2[r]
    set2 = linked2[s]
    merged = set1.union(set2)
    for i in merged:
        linked2[i] = merged

counts = []
for n in range(1, N + 1):
    set1 = linked1[n]
    set2 = linked2[n]
    counts.append(str(len(set1.intersection(set2))))

print(' '.join(counts))

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.par = [-1]*n 
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)      
        if x==y:
            return        
        if self.par[x] > self.par[y]:
            x, y = y, x       
        self.par[x] += self.par[y]
        self.par[y] = x
    def members(self, x):
        root = self.find(x)
        return set([i for i in range(self.n) if self.find(i) == root])

N, K, L = map(int, input().split())
Uni_1 = UnionFind(N)
Uni_2 = UnionFind(N)
for _ in range(K):
  p,q = map(int, input().split())
  Uni_1.union(p-1, q-1)
for _ in range(L):
  p,q = map(int, input().split())
  Uni_2.union(p-1, q-1)
for i in range(N):
  print(len(Uni_1.members(i)&Uni_2.members(i)), end=" ")

Submission status: Time Limit Exceeded

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

def gp(u,p):
	if u!= p[u]: p[u] = gp(p[u], p)
	return p[u]

def f(n,edges):
	p = {u:u for u in range(1, n+1)}
	s = {u:1 for u in range(1, n+1)}
	for u,v in edges:
		pu,pv = gp(u,p), gp(v,p)
		if pu!= pv:
			p[pv] = pu
			s[pu] += s[pv]
	return s,p
s1,p1 = f(n,[map(int, raw_input().split()) for  _ in range(k)])
s2,p2 = f(n,[map(int, raw_input().split()) for  _ in range(l)])
ans = [1 for i in range(n+1)]
for u in range(1,n + 1):
	for v in range(u+1,n + 1):
		if gp(u,p1) == gp(v,p1) and gp(u,p2) == gp(v,p2):
			ans[u] +=1
			ans[v] +=1
print ' '.join(map(str, ans[1:]))

Submission status: Time Limit Exceeded

Solution code:
N,K,L = [int(i) for i in input().split()]

roads = [[int(i)-1 for i in input().split()] for _ in range(K)]
linears = [[int(i)-1 for i in input().split()] for _ in range(L)]


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

    def unite(self, x, y):
        if self.same(x, y):
            return
        self.par[self.root(x)] = y

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

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


road_uft = UFT(N)
linear_uft = UFT(N)


for road in roads:
    road_uft.unite(road[0], road[1])

for linear in linears:
    linear_uft.unite(linear[0], linear[1])

res = {k: 1 for k in range(N)}

for i in range(N):
    for j in range(i+1, N):
        if road_uft.same(i, j) and linear_uft.same(i, j):
            res[i] += 1
            res[j] += 1

print(" ".join([f"{res[key]}" for key in res.keys()]))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k,l = list(map(int, input().split()))
from collections import defaultdict
ns0 = defaultdict(set)
ns1 = defaultdict(set)
for i in range(k):
    p,q = map(int, input().split())
    p-=1;q-=1
    ns0[p].add(q)
    ns0[q].add(p)
for i in range(l):
    p,q = map(int, input().split())
    p-=1;q-=1
    ns1[p].add(q)
    ns1[q].add(p)
def sub(ns):
    seen = [None]*n
    num = 1
    for i in range(n):
        if seen[i] is not None:
            continue
        q = [i]
        seen[i] = num
        while q:
            u = q.pop()
            for v in ns[u]:
                if seen[v] is not None:
                    continue
                seen[v] = num
                q.append(v)
        num += 1
    return seen
s1 = sub(ns0)
s2 = sub(ns1)
d1 = defaultdict(set)
d2 = defaultdict(set)
for i in range(n):
    d1[s1[i]].add(i)
    d2[s2[i]].add(i)
d = {}
ans = [None]*n
for i in range(n):
    u,v = s1[i], s2[i]
    if (u,v) not in d:
        d[u,v] = len(d1[u] & d2[v])
    ans[i] = d[u,v]
write(" ".join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


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


def main():
    from collections import Counter

    n, k, l = map(int, readline().split())
    uf1 = UnionFind(n + 1)
    uf2 = UnionFind(n + 1)

    for _ in range(k):
        p, q = map(int, readline().split())
        uf1.union(p, q)

    for _ in range(l):
        r, s = map(int, readline().split())
        uf2.union(r, s)

    a = [0] * (n + 1)
    b = [0] * (n + 1)

    for r in uf1.roots():
        for x in uf1.members(r):
            a[x] = r

    for r in uf2.roots():
        for x in uf2.members(r):
            b[x] = r
    c = Counter()
    for i in range(1, n + 1):
        c[(a[i], b[i])] += 1

    res = [0] * (n + 1)
    for i in range(1, n + 1):
        res[i] = c[(a[i], b[i])]

    print(*res[1:])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


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


def main():
    n, k, l = map(int, readline().split())
    uf1 = UnionFind(n + 1)
    uf2 = UnionFind(n + 1)

    for _ in range(k):
        p, q = map(int, readline().split())
        uf1.union(p, q)

    for _ in range(l):
        r, s = map(int, readline().split())
        uf2.union(r, s)

    res = [0] * (n + 1)
    for i in range(1, n + 1):
        if res[i] == 0:
            cnt = 0
            mem = []
            gm = uf2.members(i)
            for x in gm:
                if uf1.same(i, x):
                    cnt += 1
                    mem.append(x)
            for x in mem:
                res[x] = cnt

    print(*res[1:])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():

    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]
        self.rank = [0 for i in range(n)]
        self.mems = [{i} for i in range(n)]

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

    def unite(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if (root_x == root_y):
            return
        else:
            self.parent[root_y] = root_x
            self.mems[root_x] = self.mems[root_x] | self.mems[root_y]
            if self.rank[root_x] == self.rank[root_y]:
                self.rank[root_x] += 1

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

    def memsInGroup(self, x):
        root = self.find(x)
        return self.mems[root]

    def sizeOfGroup(self, x):
        return len(self.memsInGroup(x))


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

road = UnionFind(N)
train = UnionFind(N)

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

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

for i in range(N):
    road.unite(i, i)
    train.unite(i, i)

for i in range(N):
    conByRoad = road.memsInGroup(i)
    conByTrain = train.memsInGroup(i)
    # print(conByRoad, conByTrain)

    ans = len(set(conByRoad) & set(conByTrain))
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():

    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]
        self.rank = [0 for i in range(n)]

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

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

        if (x == y):
            return
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

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

    def sizeOfGroup(self, x):
        return len(self.memsInGroup(x))


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

road = UnionFind(N)
train = UnionFind(N)

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

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

for i in range(N):
    conByRoad = road.memsInGroup(i)
    conByTrain = train.memsInGroup(i)

    ans = len(set(conByRoad) & set(conByTrain))
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K, L = map(int, input().split())
A = []
B = []
ans = [1 for i in range(N)]
for i in range(K):
    X = set(int(x) for x in input().split())
    for j in range(len(A)):
        if len(A[j] & X) != 0:
            A[j] = A[j] | X
            break
    else:
        A.append(X)
for i in range(L):
    Y = set(int(y) for y in input().split())
    for j in range(len(B)):
        if len(B[j] & Y) != 0:
            B[j] = B[j] | Y
            break
    else:
        B.append(Y)
for a in A:
    for b in B:
        if len(a & b) != 0:
            n = len(a & b)
            for i in a & b:
                ans[i-1] = n
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
N, K, L = map(int, input().split())
A = []
B = []
ans = [1 for i in range(N)]
for i in range(K):
    X = set(int(x)-1 for x in input().split())
    for j in range(len(A)):
        if len(A[j] & X) != 0:
            A[j] = A[j] | X
            break
    else:
        A.append(X)
#print(A)
for i in range(L):
    Y = set(int(y)-1 for y in input().split())
    for j in range((len(B)+1)//2):
        if len(B[j] & Y) != 0:
            B[j] = B[j] | Y
            break
    else:
        B.append(Y)
#print(B)
for a in A:
    for b in B:
        if len(a & b) != 0:
            n = len(a & b)
            for i in a & b:
                ans[i] = n
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
N, K, L = map(int, input().split())
ans = [1 for i in range(N)]
setA = []
setB = []
for i in range(K):
    X = set(int(x)-1 for x in input().split())
    for A in setA:
        if len(A & X) != 0:
            setA.remove(A)
            setA.append(A | X)
            break
    else:
        setA.append(X)
#print(setA)
for i in range(L):
    Y = set(int(y)-1 for y in input().split())
    for B in setB:
        if len(B & Y) != 0:
            setB.remove(B)
            setB.append(B | Y)
            break
    else:
        setB.append(Y)
#print(setB)
for A in setA:
    for B in setB:
        for i in A & B:
            ans[i] = len(A & B)
for i in range(N):
    print(ans[i], end=" ")

Submission status: Time Limit Exceeded

Solution code:
N, K, L = map(int, input().split())
city = [{"path":{i},"train":{i}} for i in range(N)]
for i in range(K):
    p, q = map(int, input().split())
    join = city[p-1]["path"] | city[q-1]["path"]
    for j in join:
        city[j]["path"] = join
for i in range(L):
    r, s = map(int, input().split())
    join = city[r-1]["train"] | city[s-1]["train"]
    for j in join:
        city[j]["train"] = join
else:
    del join
for k in range(N):
    print(len(city[k]["path"]&city[k]["train"]), end=" ")

Submission status: Time Limit Exceeded

Solution code:
n,k,l=map(int,input().split())
el=[set() for _ in range(n+1)]
et=[set() for _ in range(n+1)]
ela=[set() for _ in range(n+1)]
eta=[set() for _ in range(n+1)]
eml=[0]*(n+1)
emt=[0]*(n+1)
ans=[0]*(n+1)
for _ in range(k):
  p,q=map(int,input().split())
  el[p].add(q)
  el[q].add(p)
j=0
for i in range(n+1):
  if eml[i]:continue
  eml[i]=j
  ela[j].add(i)
  q=[i]
  while q:
    now=q.pop()
    eml[now]=j
    for to in el[now]:
      if eml[to]:continue
      ela[j].add(to)
      q+=[to]
  j+=1
for _ in range(l):
  p,q=map(int,input().split())
  et[p].add(q)
  et[q].add(p)
j=0
for i in range(n+1):
  if emt[i]:continue
  emt[i]=j
  eta[j].add(i)
  q=[i]
  while q:
    now=q.pop()
    emt[now]=j
    for to in et[now]:
      if emt[to]:continue
      eta[j].add(to)
      q+=[to]
  j+=1
for i in range(n+1):
  ans[i]=len(eta[emt[i]]&ela[eml[i]])
print(*ans[1:])

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy

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

road = [[] for i in range(n+1)]
rail = [[] for i in range(n+1)]

for i in range(k):
    p, q = list(map(int, input().split()))
    road[p].append(q)
    road[q].append(p)

for i in range(l):
    r, s = list(map(int, input().split()))
    rail[r].append(s)
    rail[s].append(r)

seen = [0 for i in range(n+1)]

def dfs_stack(u, al):
    stack = deque([u])
    seen[u] = 1
    visited = []

    while len(stack) > 0:
        v = stack.pop()
        ###
        visited.append(v)
        ###

        for w in al[v]:
            if seen[w] == 0:
                stack.append(w)
                seen[w] = 1

        if stack == []: break

    return visited

road_c = []
rail_c = []
for i in range(1,n+1):
    if seen[i] == 0:
        road_c.append(dfs_stack(i, road))

seen = [0 for i in range(n+1)]

for i in range(1,n+1):
    if seen[i] == 0:
        rail_c.append(dfs_stack(i, rail))

ans = [0 for i in range(n+1)]
for a in road_c:
    for b in rail_c:
        intersection = set(a) & set(b)
        for i in intersection:
            ans[i] = str(len(intersection))

print(' '.join(ans[1:]))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

from sys import stdin, setrecursionlimit


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

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

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

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

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

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


def main():
    input = stdin.buffer.readline
    n, k, l = map(int, input().split())

    fk = UnionFindTree(n)
    for _ in range(k):
        p, q = map(int, input().split())
        fk.union(p - 1, q - 1)

    fl = UnionFindTree(n)
    for _ in range(l):
        r, s = map(int, input().split())
        fl.union(r - 1, s - 1)

    ans = []
    roots_k = fk.roots()
    roots_l = fl.roots()

    members_k = [fk.members(i) for i in roots_k]
    members_l = [fl.members(i) for i in roots_l]
    for i in range(n):
        ans.append(len(set(members_k[roots_k.index(fk.find(i))]) & set(members_l[roots_l.index(fl.find(i))])))

    print(*ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

from sys import stdin, setrecursionlimit


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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        p = self.parent
        if x != y:
            if x > y:
                x, y = y, x
            p[x], p[y] = p[x] + p[y], x

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

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

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


def main():
    input = stdin.buffer.readline
    n, k, l = map(int, input().split())

    fk = UnionFindTree(n)
    for _ in range(k):
        p, q = map(int, input().split())
        fk.union(p - 1, q - 1)

    fl = UnionFindTree(n)
    for _ in range(l):
        r, s = map(int, input().split())
        fl.union(r - 1, s - 1)

    ans = []
    for i in range(n):
        ans.append(len(set(fk.members(i)) & set(fl.members(i))))

    print(*ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()