Минимальный путь между двумя вершинами

import queue
n = int(input())
graph = [[] * n for i in range(n)]
for i in range(n):
    lst = list(map(int, input().split()))
    graph[i] = lst.copy()
prev = [-1] * n
def bfs(s):
    q = queue.Queue()
    dist = [-1] * n
    dist[s] = -1
    q.put(s)
    while not(q.empty()):
        v = q.get()
        for u in range(n):
            if graph[v][u] == 1:
                if dist[u] == -1:
                    q.put(u)
                    global prev
                    dist[u] = dist[v] + 1
                    prev[u] = v
    return dist
a, b = map(int, input().split())
a -= 1
b -= 1
dist = bfs(a)
ans = []
i = b
while i != -1:
    ans.append(i)
    i = prev[i]
ans.reverse()
print(dist[b])
print(*ans)
print(*prev)

from collections import deque

dist[s] = 0

import queue
n = int(input())
graph = [[] * n for i in range(n)]
for i in range(n):
    lst = list(map(int, input().split()))
    graph[i] = lst.copy()
prev = [-1] * n
def bfs(s):
    q = queue.Queue()
    dist = [-1] * n
    dist[s] = 0
    q.put(s)
    while not(q.empty()):
        v = q.get()
        for u in range(n):
            if graph[v][u] == 1:
                if dist[u] == -1:
                    q.put(u)
                    global prev
                    dist[u] = dist[v] + 1
                    prev[u] = v
    return dist
a, b = map(int, input().split())
a -= 1
b -= 1
dist = bfs(a)
ans = []
i = b
while i != -1:
    ans.append(i + 1)
    i = prev[i]
ans.reverse()
if len(ans) == 0:
    ans = [-1]
print(dist[b])
print(*ans)