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

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


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

    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 unite(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 get_size(self, x):
        return -self.parents[self.find(x)]

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

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

    def get_members(self, x):
        parent = self.find(x)
        return [i for i in range(self.n_nodes) if self.find(i) == parent]

    def get_members_dict(self):
        return {par: self.get_members(par) for par in self.get_parent_list()}


def main():
    N, K, L = map(int, input().split())
    tree_road = UnionFind(N)
    tree_subway = UnionFind(N)

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

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

    d1 = tree_road.get_members_dict()
    d2 = tree_subway.get_members_dict()

    for i in range(N):
        p1 = tree_road.find(i)
        p2 = tree_subway.find(i)
        m1 = set(d1[p1])
        m2 = set(d2[p2])
        print(len(m1 & m2), end=" ")


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


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

    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 unite(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 get_size(self, x):
        return -self.parents[self.find(x)]

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

    def get_members(self, x):
        parent = self.find(x)
        return [i for i in range(self.n_nodes) if self.find(i) == parent]


def main():
    N, K, L = map(int, input().split())
    tree_road = UnionFind(N)
    tree_subway = UnionFind(N)

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

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

    for i in range(N):
        m1 = set(tree_road.get_members(i))
        m2 = set(tree_subway.get_members(i))
        print(len(m1 & m2), end=" ")


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np


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


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

    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
        if self.rank[x] > self.rank[y]:
            self.parent[y] = x
            self.size[x] += self.size[y]
        else:
            self.parent[x] = y
            self.size[y] += self.size[x]
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

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

    def get_parent_list(self):
        return [i for i in range(self.n_nodes) if self.find(i) == i]

    def get_n_groups(self):
        return len(self.get_parent_list())

    def get_members(self, x):
        parent = self.find(x)
        return [i for i in range(self.n_nodes) if self.find(i) == parent]

    def get_members_dict(self):
        return {par: self.get_members(par) for par in self.get_parent_list()}


def main():
    N, K, L = map(int, input().split())
    Tree_road = UnionFind(N)
    Tree_train = UnionFind(N)
    for _ in range(K):
        p, q = map(int, input().split())
        Tree_road.unite(p - 1, q - 1)
    for _ in range(L):
        p, q = map(int, input().split())
        Tree_train.unite(p - 1, q - 1)
    road = Tree_road.get_members_dict()
    train = Tree_train.get_members_dict()
    answer = []
    for i in range(N):
        R = np.array(road[Tree_road.find(i)])
        T = np.array(train[Tree_train.find(i)])
        answer.append(len(np.intersect1d(R, T)))
    print(*answer, sep=" ")


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N,K,L = map(int, input().split())
Klist = [list(map(int, input().split())) for _ in range(K)]
Llist = [list(map(int, input().split())) for _ in range(L)]

inf = float("inf")
dpk = [inf]*N

for i in range(0,K):
    dpk[Klist[i][0]-1] = min(i,dpk[Klist[i][0]-1],dpk[Klist[i][1]-1])
    dpk[Klist[i][1]-1] = min(i,dpk[Klist[i][0]-1],dpk[Klist[i][1]-1])

dpl = [inf]*N
for j in range(0,L):
    dpl[Llist[j][0]-1] = min(j,dpl[Llist[j][0]-1],dpl[Llist[j][1]-1])
    dpl[Llist[j][1]-1] = min(j,dpl[Llist[j][0]-1],dpl[Llist[j][1]-1])

for m in range(0,N):
    res = 1
    if dpk[m] == inf:
        pass
    else:
        for n in range(0,N):
            if dpl[n] == inf:
                pass
            elif m == n :
                pass
            else:
                if dpk[m] == dpk[n] and dpl[m] == dpl[n]:
                    res = res+1
    print(res)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self,n):
        self.par = [i for i in range(n+1)]  #親のノード番号
        self.rank = [0]*(n+1)
    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 same_check(self,x,y):  #x,yが同じグループか否か
        return self.find(x) == self.find(y)
    def union(self,x,y):  #x,yの属するグループの併合
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        elif self.rank[x] > self.rank[y]:
            self.par[y] = x
        else:
            self.par[y] = x
            self.rank[x] += 1

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

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

for i in range(K):
    road.union(A[i][0],A[i][1])
for i in range(L):
    train.union(B[i][0],B[i][1])

pair = [(road.find(i),train.find(i)) for i in range(1,N+1)]

from collections import Counter

#根が同じなら道路or鉄道でつなげる

c = Counter(pair)
ans = str(c[(road.find(1),train.find(1))])
for i in range(2,N+1):
    ans = ans + ' ' + str(c[(road.find(i),train.find(i))])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from collections import defaultdict

def main():
    N, K, L = (int(_) for _ in input().split())
    road = defaultdict(list)
    train = defaultdict(list)
    for i in range(K):
        p, q = (int(_) for _ in input().split())
        road[p].append(q)
        road[q].append(p)
    for i in range(L):
        p, q = (int(_) for _ in input().split())
        train[p].append(q)
        train[q].append(p)
    visited_r = [0] * (N+1)
    gn = 1
    for p in range(1, N+1):
        if visited_r[p] != 0:
            continue
        d = deque()
        d.append(p)
        while d:
            q = d.popleft()
            visited_r[q] = gn
            if q in road:
                for r in road[q]:
                    if visited_r[r] == 0:
                        d.append(r)
        gn += 1
    visited_t = [0] * (N+1)
    gn = 1
    for p in range(1, N+1):
        if visited_t[p] != 0:
            continue
        d = deque()
        d.append(p)
        while d:
            q = d.popleft()
            visited_t[q] = gn
            if q in train:
                for r in train[q]:
                    if visited_t[r] == 0:
                        d.append(r)
        gn += 1
    dict = defaultdict(int)
    for i in range(1, N+1):
        dict[(visited_r[i], visited_t[i])] += 1
    for i in range(1, N+1):
        print(dict[(visited_r[i], visited_t[i])], end=' ')
    print('')
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def main():
    N, K, L = (int(_) for _ in input().split())
    road = {}
    train = {}
    for i in range(K):
        p, q = (int(_) for _ in input().split())
        if p in road:
            road[p].append(q)
        else:
            road[p] = [q]
        if q in road:
            road[q].append(p)
        else:
            road[q] = [p]
    for i in range(L):
        p, q = (int(_) for _ in input().split())
        if p in train:
            train[p].append(q)
        else:
            train[p] = [q]
        if q in train:
            train[q].append(p)
        else:
            train[q] = [p]
    visited_r = [0] * (N+1)
    gn = 1
    for p in range(1, N+1):
        if visited_r[p] != 0:
            continue
        d = deque()
        d.append(p)
        while d:
            q = d.popleft()
            visited_r[q] = gn
            if q in road:
                for r in road[q]:
                    if visited_r[r] == 0:
                        d.append(r)
        gn += 1
    visited_t = [0] * (N+1)
    gn = 1
    for p in range(1, N+1):
        if visited_t[p] != 0:
            continue
        d = deque()
        d.append(p)
        while d:
            q = d.popleft()
            visited_t[q] = gn
            if q in train:
                for r in train[q]:
                    if visited_t[r] == 0:
                        d.append(r)
        gn += 1
    dict = {}
    for i in range(1, N+1):
        if (visited_r[i], visited_t[i]) in dict:
            dict[(visited_r[i], visited_t[i])] += 1
        else:
            dict[(visited_r[i], visited_t[i])] = 1
    for i in range(1, N+1):
        print(dict[(visited_r[i], visited_t[i])], end=' ')
    print('')
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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

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

for i in range(K):
    uf_road.union(pq[i][0]-1,pq[i][1]-1)
for i in range(L):
    uf_train.union(rs[i][0]-1,rs[i][1]-1)

# 各都市に連結しているroadとtrainの積集合の探索はTLE
# ans = []
# for i in range(N):
#   ans.append(len(set(uf_road.members(i)) & set(uf_train.members(i))))
# print(*ans)

# road,trainの根のペアで同じペアを持つ都市は連結している
ans = []
pair = [(uf_road.find(i), uf_train.find(i)) for i in range(N)]
for i in range(N):
    ans.append(pair.count(pair[i]))
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    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=list(map(int,input().split()))
pq=[list(map(int,input().split())) for i in range(K)]
rs=[list(map(int,input().split())) for i in range(L)]

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

for i in range(K):
    uf_road.union(pq[i][0]-1,pq[i][1]-1)
for i in range(L):
    uf_train.union(rs[i][0]-1,rs[i][1]-1)

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

Submission status: Time Limit Exceeded

Solution code:
N, K, L = map(int, input().split())
road = []
for i in range(K):
  road.append(list(map(int, input().split())))
train = []
for i in range(L):
  train.append(list(map(int, input().split())))

road2 = []
train2 = []
 
for i in range(K):
  r = road[i][1]
  if r == N:
    pass
  else:
    for j in range(i+1, K):
      if road[j][0] == r and road[i][0] < road[j][1]:
        road2.append([road[i][0], road[j][1]])
      else:
        pass

for i in range(K):
  r = road[i][1]
  if r <= 3:
    pass
  else:
    for j in range(i+1, K):
      if road[j][1] == r and road[i][0] < r:
        road2.append([road[i][0], r])
      else:
        pass

for i in range(K):
  r = road[i][0]
  for j in range(i+1, K):
    if road[j][0] == r and road[i][1] < road[j][1]:
      road2.append([road[i][1], road[j][1]])
      
for x in road2:
  if not x in road:
    road.append(x)
    
for i in range(L):
  t = train[i][1]
  if t == N:
    pass
  else:
    for j in range(i+1, L):
      if train[j][0] == t and train[i][0] < train[j][1]:
        train2.append([train[i][0], train[j][1]])
      else:
        pass

for i in range(L):
  t = train[i][1]
  if t <= 3:
    pass
  else:
    for j in range(i+1, L):
      if train[j][1] == t and train[i][0] < t:
        train2.append([train[i][0], t])
      else:
        pass

for i in range(L):
  t = train[i][0]
  for j in range(i+1, L):
    if train[j][0] == t and train[i][1] < train[j][1]:
      train2.append([train[i][1], train[j][1]])
      
for x in train2:
  if not x in train:
    train.append(x)
  
def f(li1, li2):
  city2 = []
  for x in li1:
    if x in li2:
      city2.append(x)
  return city2

if len(road) >= len(train):
  c = f(road, train)
else:
  c = f(train, road)
  
for i in range(1, N+1):
  result = 1
  for j in range(len(c)):
    if c[j][0] == i or c[j][1] == i:
      result += 1
  print(result, end = " ")

Submission status: Time Limit Exceeded

Solution code:
# Union Find

# xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]


# xとyの属する集合の併合
def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return False
    else:
        # sizeの大きいほうがx
        if par[x] > par[y]:
            x, y = y, x
        par[x] += par[y]
        par[y] = x
        return True


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


# xが属する集合の個数
def size(x):
    return -par[find(x)]



def exfind(x):
    if train[x] < 0:
        return x
    else:
        train[x] = exfind(train[x])
        return train[x]


# xとyの属する集合の併合
def exunite(x, y):
    x = exfind(x)
    y = exfind(y)
    if x == y:
        return False
    else:
        # sizeの大きいほうがx
        if train[x] > train[y]:
            x, y = y, x
        train[x] += train[y]
        train[y] = x
        return True


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


# 初期化
# 根なら-size,子なら親の頂点
import itertools

n, k, l = map(int,input().split())
par = [-1] * n
train = [-1] * n
for i in range(k):
    p,q=map(int,input().split())
    p-=1
    q-=1
    unite(p,q)
for i in range(l):
    p, q = map(int, input().split())
    p -= 1
    q -= 1
    exunite(p, q)


que = [i for i in range(n)]
ans = [1]*n
for s,t in itertools.combinations(que,2):
    if exsame(s,t) and same(s,t):
        ans[s] += 1
        ans[t] += 1
for i in range(n-1):
    print(ans[i],end=" ")
else:
    print(ans[n-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, y):
        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()}


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

road = UnionFind(N+1)
railway = UnionFind(N+1)

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

for _ in range(L):
    p, q = map(int, input().split())
    railway.union(p, q)

ans = []
for i in range(1, N+1):
    ans.append(len(set(road.members(i)) & set(railway.members(i))))
print(" ".join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
# Union Find

# xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]


# xとyの属する集合の併合
def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return False
    else:
        # sizeの大きいほうがx
        if par[x] > par[y]:
            x, y = y, x
        par[x] += par[y]
        par[y] = x
        return True


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


# xが属する集合の個数
def size(x):
    return -par[find(x)]



def exfind(x):
    if train[x] < 0:
        return x
    else:
        train[x] = exfind(train[x])
        return train[x]


# xとyの属する集合の併合
def exunite(x, y):
    x = exfind(x)
    y = exfind(y)
    if x == y:
        return False
    else:
        # sizeの大きいほうがx
        if train[x] > train[y]:
            x, y = y, x
        train[x] += train[y]
        train[y] = x
        return True


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


# 初期化
# 根なら-size,子なら親の頂点

n, k, l = map(int,input().split())
par = [-1] * n
train = [-1] * n
for i in range(k):
    p,q=map(int,input().split())
    p-=1
    q-=1
    unite(p,q)
for i in range(l):
    p, q = map(int, input().split())
    p -= 1
    q -= 1
    exunite(p, q)
for s in range(n):
    ans = 1
    for t in range(n):
        if s!=t:
            if exsame(s,t) and same(s,t):
                ans += 1
    if s != n-1:
        print(ans,end=" ")
    else:
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import Counter
from pprint import pprint

def myinput():
    return map(int,input().split())

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

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 = myinput()
# pq = [ list(myinput()) for _ in range(k) ]
# rs = [ list(myinput()) for _ in range(l) ]

uf1 = UnionFind(n)
for i in range(k):
    p,q = myinput()
    uf1.union(p-1,q-1)

uf2 = UnionFind(n)
for i in range(l):
    r,s = myinput()
    uf2.union(r-1,s-1)

for i in range(n):
    ls1 = uf1.members(i)
    # print(ls1)
    ls2 = uf2.members(i)
    # print(ls2)
    ans = len( set(ls1) & set(ls2) )
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import Counter
from pprint import pprint

def myinput():
    return map(int,input().split())

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

n,k,l = myinput()
pq = [ list(myinput()) for _ in range(k) ]
rs = [ list(myinput()) for _ in range(l) ]

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

uf1 = UnionFind(n)
for i in range(k):
    p = pq[i][0] - 1
    q = pq[i][1] - 1
    uf1.union(p,q)

uf2 = UnionFind(n)
for i in range(l):
    r = rs[i][0] - 1
    s = rs[i][1] - 1
    uf2.union(r,s)

for i in range(n):
    ls1 = uf1.members(i)
    # print(ls1)
    ls2 = uf2.members(i)
    # print(ls2)
    ans = len( set(ls1) & set(ls2) )
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
  def __init__(self,n):
    self.n=n
    self.parents=[-1]*n
  def find(self,x):
    if self.parents[x]<0:
      return x
    else:
      self.parents[x]=self.find(self.parents[x])
      return self.parents[x]
  def unite(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 -size.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()}
n,k,l=map(int,input().split())
uf1=UnionFind(n)
for _ in range(k):
  u,v=map(int,input().split())
  uf1.unite(u-1,v-1)
uf2=UnionFind(n)
for _ in range(l):
  u,v=map(int,input().split())
  uf2.unite(u-1,v-1)
r=[[] for i in range(n)]
for i in range(n):
  if len(r[i])==0:
    x=uf1.members(i)
    for j in x:
      r[j]=set(x)
t=[[] for i in range(n)]
for i in range(n):
  if len(t[i])==0:
    x=uf2.members(i)
    for j in x:
      t[j]=set(x)
ans=[]
for i in range(n):
  ans.append(len(r[i]&t[i]))
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class UnionFind:
    def __init__(self, n):
        self.state = [-1] * n
        self.size_table = [set([i]) for i in range(n)]
        # cntはグループ数
        # self.cnt = n

    def root(self, u):
        v = self.state[u]
        if v < 0: return u
        self.state[u] = res = self.root(v)
        return res

    def merge(self, u, v):
        ru = self.root(u)
        rv = self.root(v)
        if ru == rv: return
        du = self.state[ru]
        dv = self.state[rv]
        if du > dv: ru, rv = rv, ru
        if du == dv: self.state[ru] -= 1
        self.state[rv] = ru
        # self.cnt -= 1
        self.size_table[ru] |= self.size_table[rv]
        return

    # グループの要素数
    def size(self, u):
        return self.size_table[self.root(u)]

def main():
    n,k,l=MI()
    road=UnionFind(n)
    train=UnionFind(n)
    for _ in range(k):
        u,v=MI1()
        road.merge(u,v)
    for _ in range(l):
        u,v=MI1()
        train.merge(u,v)
    ans=[len(road.size(i)&train.size(i)) for i in range(n)]
    print(*ans)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class UnionFind:
    def __init__(self, n):
        self.state = [-1] * n
        self.size_table = [1<<i for i in range(n)]
        # cntはグループ数
        # self.cnt = n

    def root(self, u):
        v = self.state[u]
        if v < 0: return u
        self.state[u] = res = self.root(v)
        return res

    def merge(self, u, v):
        ru = self.root(u)
        rv = self.root(v)
        if ru == rv: return
        du = self.state[ru]
        dv = self.state[rv]
        if du > dv: ru, rv = rv, ru
        if du == dv: self.state[ru] -= 1
        self.state[rv] = ru
        # self.cnt -= 1
        self.size_table[ru] |= self.size_table[rv]
        return

    # グループの要素数
    def size(self, u):
        return self.size_table[self.root(u)]

def main():
    n,k,l=MI()
    road=UnionFind(n)
    train=UnionFind(n)
    for _ in range(k):
        u,v=MI1()
        road.merge(u,v)
    for _ in range(l):
        u,v=MI1()
        train.merge(u,v)
    ans=[bin(road.size(i)&train.size(i)).count("1") for i in range(n)]
    print(*ans)

main()