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())
def maketree(n,k):
    from collections import defaultdict
    road=defaultdict(set)
    roadidx=[-1 for _ in range(n)]
    for i in range(k):
        p,q=map(int,input().split())
        p-=1
        q-=1
        pidx=roadidx[p]
        qidx=roadidx[q]
        if pidx==-1 and qidx==-1:
            road[p]={p,q}
            roadidx[p]=p
            roadidx[q]=p
        elif pidx==-1 and qidx!=-1:
            road[qidx]|={p,}
            roadidx[p]=qidx
        elif pidx!=-1 and qidx==-1:
            road[pidx]|={q,}
            roadidx[q]=pidx
        elif pidx!=qidx:
            road[pidx]=road[pidx]|road[qidx]
            for j in road[qidx]:
                roadidx[j]=pidx
            road.pop(qidx)
    return road,roadidx

roadtree,roadidx=maketree(n,k)
metrotree,metroidx=maketree(n,l)

result=[1 for i in range(n)]
for i in roadtree:
    target=roadtree[i]
    check=target.copy()
    while len(check)>0:
        now=check.pop()
        if metroidx[now]!=-1:
            x=target & metrotree[metroidx[now]]
            if len(x)!=0:
                for j in x:
                    result[j]=len(x)
        else:x={now,}
        check-=x

res=''
for i in range(n):
    res=res+str(result[i])+' '
print(res)

Submission status: Time Limit Exceeded

Solution code:
n,k,l=map(int,input().split())
def maketree(n,k,target):
    from collections import defaultdict
    road=defaultdict(set)
    roadidx=[-1 for _ in range(n)]
    for i in range(len(target)):
        p=target[i][0]
        q=target[i][1]
        pidx=roadidx[p]
        qidx=roadidx[q]
        if pidx==-1 and qidx==-1:
            road[p]={p,q}
            roadidx[p]=p
            roadidx[q]=p
        elif pidx==-1 and qidx!=-1:
            road[qidx]|={p,}
            roadidx[p]=qidx
        elif pidx!=-1 and qidx==-1:
            road[pidx]|={q,}
            roadidx[q]=pidx
        elif pidx!=qidx:
            x=road[pidx]|road[qidx]
            y=min(pidx,qidx)
            z=max(pidx,qidx)
            road[y]=x
            road.pop(z)
            for j in x:
                roadidx[j]=y
    resroad=[]
    idx=[-1 for _ in range(n)]
    count=0
    for i in road:
        resroad.append(road[i])
        for j in road[i]:
            idx[j]=count
        count+=1
    return resroad,idx

road = []
for i in range(k):
        p,q=map(int,input().split())
        p-=1
        q-=1
        road.append([p,q])
metro=[]
for i in range(l):
        r,s=map(int,input().split())
        r-=1
        s-=1
        metro.append([r,s])
roadtree,roadidx=maketree(n,k,road)
metrotree,metroidx=maketree(n,l,metro)

result=[1 for i in range(n)]
for i in roadtree:
    check=i.copy()
    while len(check)>0:
        now=check.pop()
        if metroidx[now]!=-1:
            x=i & metrotree[metroidx[now]]
            if len(x)!=0:
                for j in x:
                    result[j]=len(x)
        else:x={now,}
        check-=x

res=''
for i in range(n):
    res=res+str(result[i])+' '
print(res)

Submission status: Time Limit Exceeded

Solution code:
n,k,l=map(int,input().split())
def maketree(n,k,target):
    from collections import defaultdict
    road=defaultdict(set)
    roadidx=[-1 for _ in range(n)]
    for i in range(len(target)):
        p=target[i][0]
        q=target[i][1]
        pidx=roadidx[p]
        qidx=roadidx[q]
        if pidx==-1 and qidx==-1:
            road[p]={p,q}
            roadidx[p]=p
            roadidx[q]=p
        elif pidx==-1 and qidx!=-1:
            road[qidx]|={p,}
            roadidx[p]=qidx
        elif pidx!=-1 and qidx==-1:
            road[pidx]|={q,}
            roadidx[q]=pidx
        elif pidx!=qidx:
            x=road[pidx]|road[qidx]
            y=min(pidx,qidx)
            z=max(pidx,qidx)
            road[y]=x
            road.pop(z)
            for j in x:
                roadidx[j]=y
    resroad=[]
    for i in road:
        resroad.append(road[i])
    return resroad

road = []
for i in range(k):
        p,q=map(int,input().split())
        p-=1
        q-=1
        road.append([p,q])
metro=[]
for i in range(l):
        r,s=map(int,input().split())
        r-=1
        s-=1
        metro.append([r,s])
roadtree=maketree(n,k,road)
metrotree=maketree(n,l,metro)
ans=[]
for i in roadtree:
    for j in metrotree:
        ans.append(i & j)

result=[1 for i in range(n)]
while len(ans)>0:
    x=ans.pop()
    for i in x:
        result[i]=len(x)
        
res=''
for i in range(n):
    res=res+str(result[i])+' '
print(res)

Submission status: Time Limit Exceeded

Solution code:
n,k,l=map(int,input().split())
def maketree(n,k,target):
    road=[]
    roadidx=[-1 for _ in range(n)]
    for i in range(len(target)):
        p=target[i][0]
        q=target[i][1]
        pidx=roadidx[p]
        qidx=roadidx[q]
        if pidx==-1 and qidx==-1:
            road.append({p,q})
            roadidx[p]=len(road)-1
            roadidx[q]=len(road)-1
        elif pidx==-1 and qidx!=-1:
            road[roadidx[q]]|={p,}
            roadidx[p]=qidx
        elif pidx!=-1 and qidx==-1:
            road[roadidx[p]]|={q,}
            roadidx[q]=pidx
        elif pidx!=qidx:
            x=road[roadidx[p]]|road[roadidx[q]]
            y=min(pidx,qidx)
            z=max(pidx,qidx)
            road[y]=x
            road[z]=x
            for j in x:
                roadidx[j]=y
    resroad=[]
    for i in road:
        if i not in resroad:resroad.append(i)
    return resroad

road = []
for i in range(k):
        p,q=map(int,input().split())
        p-=1
        q-=1
        road.append([p,q])
metro=[]
for i in range(l):
        r,s=map(int,input().split())
        r-=1
        s-=1
        metro.append([r,s])
roadtree=maketree(n,k,road)
metrotree=maketree(n,l,metro)
ans=[]
for i in roadtree:
    for j in metrotree:
        ans.append(i & j)

result=[1 for i in range(n)]
while len(ans)>0:
    x=ans.pop()
    for i in x:
        result[i]=len(x)
        
res=''
for i in range(n):
    res=res+str(result[i])+' '
print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


class Node:

    def __init__(self, i):
        self.index = i
        self.parent = self
        self.height = 1

    def root(self):
        if self.parent == self:
            return self.parent
        else:
            self.parent = self.parent.root()
            return self.parent

    def unite(self, other):
        if self.root().height > other.root().height:
            self.root().parent = other.root()
            self.root().height = other.root().height + 1
        else:
            other.root().parent = self.root()
            other.root().height = self.root().height + 1

    def is_unite(self, other):
        return self.root() == other.root()


def solve(N, K, L, PQs, RSs):
    road_cities = [Node(i) for i in range(N + 1)]
    train_cities = [Node(i) for i in range(N + 1)]

    for p, q in PQs:
        road_cities[p].unite(road_cities[q])
    for r, s in RSs:
        train_cities[r].unite(train_cities[s])

    counts = Counter([
        (road_cities[i].root().index, train_cities[i].root().index)
        for i in range(1, N + 1)
    ])

    ans = [
        counts[(road_cities[i].root().index, train_cities[i].root().index)]
        for i in range(1, N + 1)
    ]

    return " ".join([str(c) for c in ans])


if __name__ == "__main__":
    N, K, L = map(int, input().split(" "))
    PQs = []
    RSs = []
    for _ in range(K):
        PQs.append(tuple(map(int, input().split(" "))))
    for _ in range(L):
        RSs.append(tuple(map(int, input().split(" "))))
    print(solve(N, K, L, PQs, RSs))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


class Node:

    def __init__(self, i):
        self.index = i
        self.parent = self

    def root(self):
        if self.parent == self:
            return self.parent
        else:
            self.parent = self.parent.root()
            return self.parent

    def unite(self, other):
        self.root().parent = other.root()

    def is_unite(self, other):
        return self.root() == other.root()


def solve(N, K, L, PQs, RSs):
    road_cities = [Node(i) for i in range(N + 1)]
    train_cities = [Node(i) for i in range(N + 1)]

    for p, q in PQs:
        road_cities[p].unite(road_cities[q])
    for r, s in RSs:
        train_cities[r].unite(train_cities[s])

    counts = Counter([
        (road_cities[i].root().index, train_cities[i].root().index)
        for i in range(1, N + 1)
    ])

    ans = [
        counts[(road_cities[i].root().index, train_cities[i].root().index)]
        for i in range(1, N + 1)
    ]

    return " ".join([str(c) for c in ans])


if __name__ == "__main__":
    N, K, L = map(int, input().split(" "))
    PQs = []
    RSs = []
    for _ in range(K):
        PQs.append(tuple(map(int, input().split(" "))))
    for _ in range(L):
        RSs.append(tuple(map(int, input().split(" "))))
    print(solve(N, K, L, PQs, RSs))

Submission status: Time Limit Exceeded

Solution code:
class Node:

    def __init__(self, i):
        self.index = i
        self.parent = self

    def root(self):
        if self.parent == self:
            return self.parent
        else:
            self.parent = self.parent.root()
            return self.parent

    def unite(self, other):
        self.root().parent = other.root()

    def is_unite(self, other):
        return self.root() == other.root()


def solve(N, K, L, PQs, RSs):
    road_cities = [Node(i) for i in range(N + 1)]
    train_cities = [Node(i) for i in range(N + 1)]

    for p, q in PQs:
        road_cities[p].unite(road_cities[q])
    for r, s in RSs:
        train_cities[r].unite(train_cities[s])

    counts = {}
    for i in range(1, N + 1):
        r1 = road_cities[i].root().index
        r2 = train_cities[i].root().index
        if (r1, r2) not in counts:
            counts[(r1, r2)] = 0
        counts[(r1, r2)] += 1

    ans = []
    for i in range(1, N + 1):
        r1 = road_cities[i].root().index
        r2 = train_cities[i].root().index
        ans.append(counts[(r1, r2)])

    return " ".join([str(c) for c in ans])


if __name__ == "__main__":
    N, K, L = map(int, input().split(" "))
    PQs = []
    RSs = []
    for _ in range(K):
        PQs.append(tuple(map(int, input().split(" "))))
    for _ in range(L):
        RSs.append(tuple(map(int, input().split(" "))))
    print(solve(N, K, L, PQs, RSs))

Submission status: Time Limit Exceeded

Solution code:
class Node:

    def __init__(self, i):
        self.index = i
        self.parent = self

    def root(self):
        if self.parent == self:
            return self.parent
        else:
            self.parent = self.parent.root()
            return self.parent

    def unite(self, other):
        self.root().parent = other.root()

    def is_unite(self, other):
        return self.root() == other.root()


def solve(N, K, L, PQs, RSs):
    road_cities = [Node(i) for i in range(N + 1)]
    train_cities = [Node(i) for i in range(N + 1)]

    for p, q in PQs:
        road_cities[p].unite(road_cities[q])

    # print("road")
    # for c in road_cities[1:]:
    #     print(c.index, "-> ", c.root().index)

    for r, s in RSs:
        train_cities[r].unite(train_cities[s])

    # print("train")
    # for c in train_cities[1:]:
    #     print(c.index, "-> ", c.root().index)
    road_roots = {i: [] for i in range(1, N + 1)}
    train_roots = {i: [] for i in range(1, N + 1)}
    for i in range(1, N + 1):
        road_roots[road_cities[i].root().index].append(i)
        train_roots[train_cities[i].root().index].append(i)

    counts = {i: 0 for i in range(1, N + 1)}
    for n1 in range(1, N + 1):
        for n2 in road_roots[road_cities[n1].root().index]:
            if n1 > n2:
                continue
            if train_cities[n1].is_unite(train_cities[n2]):
                counts[n1] += 1
                if n1 != n2:
                    counts[n2] += 1

    return " ".join([str(c) for i, c in counts.items() if i > 0])


if __name__ == "__main__":
    N, K, L = map(int, input().split(" "))
    PQs = []
    RSs = []
    for _ in range(K):
        PQs.append(tuple(map(int, input().split(" "))))
    for _ in range(L):
        RSs.append(tuple(map(int, input().split(" "))))
    print(solve(N, K, L, PQs, RSs))

Submission status: Time Limit Exceeded

Solution code:
class Node:

    def __init__(self, i):
        self.index = i
        self.parent = self

    def root(self):
        if self.parent == self:
            return self.parent
        else:
            self.parent = self.parent.root()
            return self.parent

    def unite(self, other):
        self.root().parent = other.root()

    def is_unite(self, other):
        return self.root() == other.root()


def solve(N, K, L, PQs, RSs):
    road_cities = [Node(i) for i in range(N + 1)]
    train_cities = [Node(i) for i in range(N + 1)]

    for p, q in PQs:
        road_cities[p].unite(road_cities[q])

    # print("road")
    # for c in road_cities[1:]:
    #     print(c.index, "-> ", c.root().index)

    for r, s in RSs:
        train_cities[r].unite(train_cities[s])

    # print("train")
    # for c in train_cities[1:]:
    #     print(c.index, "-> ", c.root().index)

    counts = []

    for n1 in range(1, N + 1):
        count = 0
        for n2 in range(1, N + 1):
            if n1 == n2:
                count += 1
            elif road_cities[n1].is_unite(road_cities[n2]) and \
                    train_cities[n1].is_unite(train_cities[n2]):
                count += 1
        counts.append(str(count))
    return " ".join(counts)


if __name__ == "__main__":
    N, K, L = map(int, input().split(" "))
    PQs = []
    RSs = []
    for _ in range(K):
        PQs.append(tuple(map(int, input().split(" "))))
    for _ in range(L):
        RSs.append(tuple(map(int, input().split(" "))))
    print(solve(N, K, L, PQs, RSs))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

# Union-Find木
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        # 1-indexedのままでOK、その場合は[0]は未使用
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0）
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        # 根ならその番号を返す
        if self.par[x] == x:
            return x
        else:
            # 走査していく過程で親を書き換える
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        # 根を探す
        x = self.find(x)
        y = self.find(y)
        # 木の高さを比較し、低いほうから高いほうに辺を張る
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            # 木の高さが同じなら片方を1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

N, K, L = map(int, input().split())
uf1 = UnionFind(N)
uf2 = UnionFind(N)
for i in range(K):
    p, q = map(int, input().split())
    uf1.union(p, q)
for i in range(L):
    p, q = map(int, input().split())
    uf2.union(p, q)

ans = [1] * N
for i in range(N):
    for j in range(i+1, N):
        if uf1.same(i+1, j+1) and uf2.same(i+1, j+1):
            ans[i] += 1
            ans[j] += 1
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
def find(parents, x):
    if parents[x] == x:
        return x
    else:
        parents[x] = find(parents, parents[x])
        return parents[x]

def union(parents, x1, x2):
    y1 = find(parents, x1)
    y2 = find(parents, x2)
    if y1 != y2:
        parents[y1] = y2


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

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

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

counter = [1] * n
for i in range(n):
    for j in range(i + 1, n):
        if find(parents1, i) == find(parents1, j) and find(parents2, i) == find(parents2, j):
            counter[i] += 1
            counter[j] += 1
print(' '.join(map(str, counter)))

Submission status: Time Limit Exceeded

Solution code:
def find(x):
  if x==Tree[x]:
      return x
  else:
      Tree[x]=find(Tree[x])
      return Tree[x]
def unite(x,y):
  s1=find(x)
  s2=find(y)
  if s1!=s2:
    Tree[s2]=s1
def find2(x):
  if x==Tree2[x]:
      return x
  else:
      Tree2[x]=find2(Tree2[x])
      return Tree2[x]
def unite2(x,y):
  s1=find2(x)
  s2=find2(y)
  if s1!=s2:
    Tree2[s2]=s1
N,K,L=map(int,input().split())
Tree=[i for i in range(N)]
Tree2=[i for i in range(N)]
ans=[]
for i in range(K):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  unite(a,b)
for i in range(L):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  unite2(a,b)
l=[[find(i),find2(i)] for i in range(N)]
for i in range(N):
  ans.append(l.count(l[i]))
print(" ".join(map(str,ans)))

Submission status: Time Limit Exceeded

Solution code:
def find(x):
  if x==Tree[x]:
      return x
  else:
      Tree[x]=find(Tree[x])
      return Tree[x]
def unite(x,y):
  s1=find(x)
  s2=find(y)
  if s1!=s2:
    Tree[s2]=s1
def find2(x):
  if x==Tree2[x]:
      return x
  else:
      Tree2[x]=find2(Tree2[x])
      return Tree2[x]
def unite2(x,y):
  s1=find2(x)
  s2=find2(y)
  if s1!=s2:
    Tree2[s2]=s1
N,K,L=map(int,input().split())
Tree=[i for i in range(N)]
Tree2=[i for i in range(N)]
for i in range(K):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  unite(a,b)
for i in range(L):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  unite2(a,b)
ans=[1 for i in range(N)]
for i in range(N):
  for j in range(i+1,N):
    if find(i)==find(j):
      if find2(i)==find2(j):
        ans[i]+=1
        ans[j]+=1
        
print(" ".join(map(str,ans)))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 5)


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

    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 union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        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 check_same(self, x, y):
        return self.find(x) == self.find(y)


N, K, L = map(int, input().split())
r_union_find = UnionFind(N)
t_union_find = UnionFind(N)
for i in range(K):
    p, q = map(int, input().split())
    r_union_find.union(p, q)

for i in range(L):
    r, s = map(int, input().split())
    t_union_find.union(r, s)

answers = []

for i in range(1, N + 1):
    count = 0
    r_p = r_union_find.find(i)
    t_p = t_union_find.find(i)
    for j in range(1, N + 1):
        if r_p == r_union_find.find(j) and t_p == t_union_find.find(j):
            count += 1
    answers.append(count)
answers = map(str, answers)
print(" ".join(answers))

Submission status: Time Limit Exceeded

Solution code:

import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def bfs(N, path, res):
    is_visited = [False for i in range(N + 1)]
    for i in range(1, N + 1):
        if is_visited[i] == True:
            continue
        que = deque([i])
        res[i] = set([i])
        while 1:
            if len(que) <= 0:
                break

            p = que.popleft()
            is_visited[p] = True

            for q in path[p]:
                if is_visited[q] == False:
                    is_visited[q] = True
                    res[i].add(q)
                    res[q] = res[i]
                    que.append(q)



def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, K, L] = [int(input_raw[0]), int(input_raw[1]), int(input_raw[2])]
    road = {}
    train = {}
    for i in range(1, N + 1):
        road[i] = []
        train[i] = []

    for i in range(K):
        input_raw = read_func().strip().split()
        [p, q] = [int(input_raw[0]), int(input_raw[1])]
        road[p].append(q)
        road[q].append(p)
    res_road = {}
    bfs(N, road, res_road)

    for i in range(L):
        input_raw = read_func().strip().split()
        [p, q] = [int(input_raw[0]), int(input_raw[1])]
        train[p].append(q)
        train[q].append(p)

    res_train = {}
    bfs(N, train, res_train)

    for i in range(1, N + 1):
        print len(res_road[i] & res_train[i]),




if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def bfs(N, path, res):
    is_visited = [False for i in range(N + 1)]
    for i in range(1, N + 1):
        if is_visited[i] == True:
            continue
        que = deque([i])
        is_visited[i] = True
        res[i] = set([i])
        while 1:
            if len(que) <= 0:
                break

            p = que.popleft()
            is_visited[p] = True

            for q in path[p]:
                if is_visited[q] == False:
                    is_visited[q] = True
                    res[i].add(q)
                    res[q] = res[i]
                    que.append(q)



def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, K, L] = [int(input_raw[0]), int(input_raw[1]), int(input_raw[2])]
    road = {}
    train = {}
    for i in range(1, N + 1):
        road[i] = []
        train[i] = []

    for i in range(K):
        input_raw = read_func().strip().split()
        [p, q] = [int(input_raw[0]), int(input_raw[1])]
        road[p].append(q)
        road[q].append(p)
    res_road = {}
    bfs(N, road, res_road)

    for i in range(L):
        input_raw = read_func().strip().split()
        [p, q] = [int(input_raw[0]), int(input_raw[1])]
        train[p].append(q)
        train[q].append(p)

    res_train = {}
    bfs(N, train, res_train)

    for i in range(1, N + 1):
        print len(res_road[i] & res_train[i]),




if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def bfs(N, path, res):
    is_visited = [False for i in range(N + 1)]
    for i in range(1, N + 1):
        if is_visited[i] == True:
            continue
        que = deque([i])
        is_visited[i] = True
        res[i] = set([i])
        while 1:
            if len(que) <= 0:
                break

            p = que.popleft()
            is_visited[p] = True

            for q in path[p]:
                if is_visited[q] == False:
                    is_visited[q] = True
                    res[i].add(q)
                    res[q] = res[i]
                    que.append(q)



def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, K, L] = [int(input_raw[0]), int(input_raw[1]), int(input_raw[2])]
    road = {}
    train = {}
    for i in range(1, N + 1):
        road[i] = []
        train[i] = []

    for i in range(K):
        input_raw = read_func().strip().split()
        [p, q] = [int(input_raw[0]), int(input_raw[1])]
        if p not in road:
            road[p] = [q]
        else:
            road[p].append(q)

        if q not in road:
            road[q] = [p]
        else:
            road[q].append(p)
    res_road = {}
    bfs(N, road, res_road)

    for i in range(L):
        input_raw = read_func().strip().split()
        [p, q] = [int(input_raw[0]), int(input_raw[1])]
        if p not in train:
            train[p] = [q]
        else:
            train[p].append(q)

        if q not in train:
            train[q] = [p]
        else:
            train[q].append(p)

    res_train = {}
    bfs(N, train, res_train)

    for i in range(1, N + 1):
        print len(res_road[i] & res_train[i]),




if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def bfs(N, path, res):
    is_visited = [False for i in range(N + 1)]
    for i in range(1, N + 1):
        if is_visited[i] == True:
            continue
        que = deque([i])
        is_visited[i] = True
        res[i] = set([i])
        while 1:
            if len(que) <= 0:
                break
            p = que.popleft()

            for q in path[p]:
                if is_visited[q] == False:
                    is_visited[q] = True
                    res[i].add(q)
                    res[q] = res[i]
                    que.append(q)



def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, K, L] = [int(input_raw[0]), int(input_raw[1]), int(input_raw[2])]
    road = {}
    train = {}
    for i in range(1, N + 1):
        road[i] = []
        train[i] = []

    for i in range(K):
        input_raw = read_func().strip().split()
        [p, q] = [int(input_raw[0]), int(input_raw[1])]
        if p not in road:
            road[p] = [q]
        else:
            road[p].append(q)

        if q not in road:
            road[q] = [p]
        else:
            road[q].append(p)
    res_road = {}
    bfs(N, road, res_road)

    for i in range(L):
        input_raw = read_func().strip().split()
        [p, q] = [int(input_raw[0]), int(input_raw[1])]
        if p not in train:
            train[p] = [q]
        else:
            train[p].append(q)

        if q not in train:
            train[q] = [p]
        else:
            train[q].append(p)

    res_train = {}
    bfs(N, train, res_train)

    for i in range(1, N + 1):
        print len(res_road[i] & res_train[i]),




if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def bfs(N, path, res):
    is_visited = [False for i in range(N + 1)]
    for i in range(1, N + 1):
        if is_visited[i] == True:
            continue
        que = deque([i])
        res[i] = set([i])
        while 1:
            if len(que) <= 0:
                break
            p = que.popleft()
            for q in path[p]:
                if is_visited[q] == False:
                    is_visited[q] = True
                    res[i].add(q)
                    res[q] = res[i]
                    que.append(q)







def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, K, L] = [int(input_raw[0]), int(input_raw[1]), int(input_raw[2])]
    road = {}
    train = {}
    for i in range(1, N + 1):
        road[i] = []
        train[i] = []

    for i in range(K):
        input_raw = read_func().strip().split()
        [p, q] = [int(input_raw[0]), int(input_raw[1])]
        if p not in road:
            road[p] = [q]
        else:
            road[p].append(q)

        if q not in road:
            road[q] = [p]
        else:
            road[q].append(p)
    res_road = {}
    bfs(N, road, res_road)

    for i in range(L):
        input_raw = read_func().strip().split()
        [p, q] = [int(input_raw[0]), int(input_raw[1])]
        if p not in train:
            train[p] = [q]
        else:
            train[p].append(q)

        if q not in train:
            train[q] = [p]
        else:
            train[q].append(p)

    res_train = {}
    bfs(N, train, res_train)

    for i in range(1, N + 1):
        print len(res_road[i] & res_train[i]),




if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
 
sys.setrecursionlimit(10000)

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

#print(N,K,L,D,T)

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

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

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

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

def execOne(num, uf):
    for _ in range(num):
        d0, d1 = map(int, input().split())
        d0 = d0 - 1
        d1 = d1 - 1
        uf.union(d0, d1)

uf_D = UnionFind(N)
uf_T = UnionFind(N)

execOne(K, uf_D)
execOne(L, uf_T)

res = [0] * N
for i in range(N):
    for j in range(N):
        if (uf_D.same_check(i,j) and uf_T.same_check(i,j)):
            res[i] += 1
#print(*(res[i] for i in range(N)))
print(" ".join([str(i) for i in res]))