[これがコードテスト]BFS-特定距離を探す都市

BFS
まずナビゲーション幅.隣接ノードからナビゲーションを開始するアルゴリズム
動作原理-キュー/実装方法-キューリソース構造の使用
白駿18352号です.
に質問
一部の国では1~N番都市とM本の一方通行道路が存在している.すべての道路の距離は1です.ある都市Xから、到達可能なすべての都市のうち、最短距離Kのすべての都市の番号を出力するプログラムを作成してください.なお、出発都市Xから出発都市Xまでの最短距離は常にゼロであると仮定する.
到達可能な都市のうち、最短距離Kの都市が1つもない場合、−1が出力される.
入力例1
4 4 2 1
1 2
1 3
2 3
2 4
出力例1
4
入力例2
4 3 2 1
1 2
1 3
1 4
出力例1
-1
私のやり方
DFSで再帰関数にアクセスし利用した.
サンプルの出力は正しいが、タイムアウト、再帰エラーが発生した.

N, M, K, X = map(int, input().split())

graph = [[] for _ in range(N+1)]
least_distance = [M] * (N+1)
visited = [False] * (N+1)

for i in range(M):
    a, b = map(int, input.split())
    graph[a].append(b)

def dfs(graph, v, visited, count):
    visited[v] = True
    least_distance[v] = count
    count += 1
    for i in graph[v]:
        if visited[i] == True:
        	# 여기서 최단 거리 저장
            least_distance[i] = count
            break
        dfs(graph, i, visited, count)
    count = 0

dfs(graph, X, visited, 0)

if K not in least_distance:
    print(-1)
else:
    for i in range (1, len(least_distance)):
        if least_distance[i] == K:
            print(i)

問題の説明
「すべての道路の距離は1」なので、「幅優先」(BFS)を使用して問題を簡単に解決できます.

from collections import deque

N, M, K, X = map(int, input().split())

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

for i in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)

# 방문 하지 않은 도시는 -1로 표시(distance[0]은 사용하지 않음)
distance = [-1] * (N+1)
distance[X] = 0

queue = deque()
queue.append(X)

while queue:
    now = queue.popleft()
    for next_node in graph[now]:
        if distance[next_node] == -1:
            distance[next_node] = distance[now] + 1
            queue.append(next_node)

if K not in distance:
    print(-1)
else:
    for i in range(len(distance)):
        if distance[i] == K:
            print(i)