Once upon a time there was only one router in the well-known company Bmail. Years went by and over time new routers were purchased. Every time they bought a new router, they connected it to one of the routers bought before it. You are given the values $p_i$ — the index of the router to which the $i$-th router was connected after being purchased ($p_i < i$).

There are $n$ routers in Boogle in total now. Print the sequence of routers on the path from the first to the $n$-th router.


-----Input-----

The first line contains integer number $n$ ($2 \le n \le 200000$) — the number of the routers. The following line contains $n-1$ integers $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$), where $p_i$ is equal to index of the router to which the $i$-th was connected after purchase.


-----Output-----

Print the path from the $1$-st to the $n$-th router. It starts with $1$ and ends with $n$. All the elements in the path should be distinct.


-----Examples-----
Input
8
1 1 2 2 3 2 5

Output
1 2 5 8 
Input
6
1 2 3 4 5

Output
1 2 3 4 5 6 
Input
7
1 1 2 3 4 3

Output
1 3 7

Difficulty: interview

Starter code:

Solutions:
def prog():
    n = int(input())
    inp = list(map(int,input().split()))
    temp = []
    while(n!=1):
        temp += [n]
        n = inp[n-2]
    temp += [1]
    temp.reverse()
    for i in temp:
        print(i,end=' ')
prog()

n = int(input())
parent = [*map(int, input().split())]
l = [n]
while l[-1] != 1:
    l.append(parent[l[-1] - 2])
print(' '.join(map(str, l[::-1])))

n = int(input().strip())
route = list(map(int, input().strip().split()))
out = [n]
i = n - 2
while i >= 0:
    out.append(route[i])
    i = route[i] - 2

print(" ".join(map(str, reversed(out))))

n = int(input())
s = list(map(int, input().split()))
r = [n]
while r[-1] != 1:
    r.append(s[r[-1]-2])
print(*reversed(r))

n = int(input())
p = list(map(int, input().split()))

lis = []

i = n

while i != 1:
    lis.append(i)
    i = p[i - 2]

print(*[1] + lis[::-1])

from collections import deque
n = int(input())
a = list(map(int, input().split()))
k = a[-1]
answ = deque()
answ.appendleft(n)
while k != 1:
    answ.appendleft(k)
    k = a[k-2]
answ.appendleft(k)
print(" ".join(str(x) for x in answ))

from collections import deque
n = int(input())
p=[int(x) for x in input().split()]
cur = n
ans = deque()
while cur > 1:
    ans.appendleft(str(cur))
    cur = p[cur-2]
ans.appendleft('1')
print(" ".join(ans))

n = int(input())
prev = [int(x) for x in input().split()]
x = n;
ans = [x];
while x > 1:
    x = prev[x - 2]
    ans.append(x)
ans.reverse()
print(*ans)

n = int ( input ())
a = [ 0 ] + list (map(int,input().split()))
z=[]
while n != 0:
    z +=[n]
    n = a [ n -1 ]
z.reverse()
for i in z:
    print(i,end=" ")



n = int(input())
l = list(map(int,input().split()))
from collections import defaultdict
d = defaultdict(int)

for i in range(2,n+1):
    d[i] = l[i-2]

x = n
ans = []
while(x!=1):
    ans.append(x)
    x = d[x]
ans.append(1)
for i in ans[::-1]:
    print(i,end= ' ')

n=int(input())
arr=list(map(int,input().split()))
res=[n]
while res[-1]!=arr[0]:
	res.append(arr[res[-1]-2])
res.sort()
for i in res:
	print(i,end=" ")

import sys
n = int(sys.stdin.readline())
P = [0,0] + [int(i) for i in sys.stdin.readline().strip().split()]

i = n
s = [n]
while i != 1:
    s.append(P[i])
    i = P[i]
    
print(' '.join([str(i) for i in reversed(s)]))


n=int(input())
l=input().split(" ")
l=[int(x) for x in l]
route=[]
route.append(n)
current=l[-1]
while True:
    route.append(current)
    if current==1:
        break
    current=l[current-2]
for i in range(len(route)):
    print(route[len(route)-i-1],end=" ")


n = int(input())

zi = [int(x) for x in input().split()]



g = n
res = []
while g!=1:
    res.append(g)
 
    g = zi[g-2]

res.append(1)

zz = reversed(res)

zs = [str(x) for x in zz]

s = ' '.join(zs)

print(s)





def __starting_point():
    N = int(input())
    connect = [ int(x) for x in input().split(' ')]


    M = [0]*(N+2)
    for index, i in enumerate(connect):
        M[index+2] = i

    i = N
    ans = [i]
    while i!= 1:
        ans.append(M[i])
        i = M[i]

    ans.reverse()
    ans = [str(x) for x in ans]
    print(" ".join(ans))

__starting_point()

n = int(input())
p = list(map(int, input().split()))
o = []
c = n
while c!=1:
    o.append(c)
    c = p[c-2]
o.append(1)
o = reversed(o)
print(*o)


n = int(input())
arr = list(map(int, input().split()))
c = n
path = [n]

while c!=1:
    c = arr[c-2]
    path.append(c)

path = path[::-1]
print(*path)


def __starting_point():
	n = int(input())
	P = list(map(int, input().rstrip().split()))

	path = [n]
	while n != 1:
		n = P[n - 2]
		path.append(n)
	path.reverse()
	print(' '.join(map(str, path)))
__starting_point()

n=int(input())
ar1=str(input()).split(' ')
wok={}
out=[]
out.append(n)
out.append(int(ar1[n-2]))
new=int(ar1[n-2])
i=0

while new !=1:
    out.append(int(ar1[new-2]))   
    new=int(ar1[new-2])
for el in sorted(out):
    print(el, end=' ')

n = int(input())
lst = [int(i) for i in input().split(' ')]
curi = -1
ans = [n]
while(lst[curi] != 1):
	ans.append(lst[curi])
	curi = lst[curi] - 2
ans.append(1)
ans = ans[::-1]
for i in ans:
	print(i,end = ' ')

n = int(input())
d = {1: 0}
j = 2
for i in map(int, input().split()):
    d[j] = i
    j += 1
a = [n]
while d[n] != 0:
    a.append(d[n])
    n = d[n]
for i in range(len(a)-1, -1, -1):
    print(a[i], end=' ')

n = int(input())
p = list(map(int, input().split()))
l = []
x = n
while x != 1:
    l.append(x)
    x = p[x-2]
l.append(1)
print(' '.join(map(str, l[::-1])))


def bfs(start,end,g):
    vis = {start:-1}
    q = [start]
    found = False
    while q and not found:
        curr = q.pop(0)
        if curr == end:
            break
        for v in g[curr]:
            if v not in vis:
                vis[v] = curr
                q.append(v)
                if v == end:
                    found = True
                    break
    ans = []
    init = end
    while init != -1:
        ans.append(init)
        init = vis[init]
    return ans


n = int(input())
graph = [[] for _ in range(n)]
routers = [int(i) for i in input().split()]
for i in range(len(routers)):
    graph[routers[i]-1].append(i+1)
ans = bfs(0,n-1,graph)
i = 0
j = len(ans) - 1
while i <= j:
    ans[i],ans[j] = ans[j]+1,ans[i]+1
    i+=1
    j-=1
print(*ans)

n = int(input())
b = [n]
a = list(map(int,input().split()))
while n != 1:
    b.append(a[n-2])
    n = a[n-2]
if b[len(b)-1] != 1:
    b.append(1)
b = reversed(b)
print(*b , end = ' ')

n = int(input())
l = [0]+ list(map(int,input().split()))
c = n-1
k=[n]
while(l[c] != 1):
    k.append(l[c])
    c = l[c]-1
k.append(1)
for i in k[::-1]:
    print(i,end=' ')