Վերականգնել Ամենակարճ Ուղին

start = int(input())                    # սկիզբ գագաթ
d = [-1] * n                            # հեռավորությունը սկիզբ գագաթից
p = [-1] * n                            # ծնող գագաթ
q = deque([start])                      # գագաթների հերթ
d[start] = 0                            # սկիզբ գագաթից մինչեւ սկիզբ գագաթ հեռավորությունը 0 է

while q:                                # քանի դեռ հերթը դատարկ չէ
    v = q.popleft()                     # հերթից հանել գագաթը
    print(v, end=' ')                   # տպել գագաթը
    for to in g[v]:                     # բոլոր գագաթների համար, որոնք միացված են v-ին
        if d[to] == -1:                 # եթե գագաթը դեռ չի այցելվել
            d[to] = d[v] + 1            # (start -> to) = (start -> v) + 1
            p[to] = v                   # գագաթի ծնողը v-ն է
            q.append(to)                # գագաթը ավելացնել հերթի մեջ

# Ուղու վերականգնում սկիզբից մինչեւ ավարտ
end = int(input())                      # ավարտ գագաթ
path = []                               # ուղի սկիզբից մինչեւ ավարտ
while end != -1:                        # քանի դեռ գոյություն ունի ծնող գագաթ
    path.append(end)                    # գագաթը ավելացնել ուղու մեջ
    end = p[end]                        # անցնել ծնող գագաթին

print(*path[::-1], sep=' -> ')          # տպել ուղին հակադարձ հերթականությամբ