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: EASY
Tags: Tree algorithms

Graph traversal

Starter code:

Solutions:
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])


parent = [0, 1]
n = int(input())
parent += list(map(int, input().split()))
ls = []
x = n
while parent[x] != x:
	ls.append(x)
	x = parent[x]
ls.append(x)
for i in range(len(ls)):
	print(ls.pop(), end=' ')


n = int(input())
li = list(map(int, input().split()))
d = {}
for (i, x) in enumerate(li, 2):
	d[i] = x
ans = [n]
while True:
	last = ans[-1]
	p = d[last]
	ans.append(p)
	if p == 1:
		break
ans.reverse()
print(*ans)


def printv(a, sep='\n'):
	print(sep.join(map(str, a)))

def bruh():
	n = int(input())
	a = [int(i) for i in input().split()]
	ans = []
	cur = n
	while cur != 1:
		ans += [cur]
		cur = a[cur - 2]
	ans += [1]
	printv(ans[::-1], ' ')
bruh()


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)


import sys
readline = sys.stdin.readline

def i1():
	return int(readline())

def nl():
	return [int(s) for s in readline().split()]

def nn(n):
	return [int(readline()) for i in range(n)]

def nnp(n, x):
	return [int(readline()) + x for i in range(n)]

def nmp(n, x):
	return (int(readline()) + x for i in range(n))

def nlp(x):
	return [int(s) + x for s in readline().split()]

def nll(n):
	return [[int(s) for s in readline().split()] for i in range(n)]

def mll(n):
	return ([int(s) for s in readline().split()] for i in range(n))

def s1():
	return readline().rstrip()

def sl():
	return [s for s in readline().split()]

def sn(n):
	return [readline().rstrip() for i in range(n)]

def sm(n):
	return (readline().rstrip() for i in range(n))

def redir(s):
	global readline
	import os
	fn = sys.argv[0] + f'/../in-{s}.txt'
	readline = open(fn).readline if os.path.exists(fn) else readline
redir('a')
path = [s1()]
arr = sl()
while path[-1] != '1':
	path.append(arr[int(path[-1]) - 2])
print(' '.join(path[::-1]))


z = int(input())
l = list(map(int, input().split()))
k = [z, l[-1]]
a = 2
i = l[-1]
while i != 1:
	k.append(l[i - 2])
	i = l[i - 2]
	a += 1
for i in range(1, a + 1):
	print(k[-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])))


n = int(input())
p = [int(x) for x in input().split()]
now = n
ans = [str(now)]
while now > 1:
	now = p[now - 2]
	ans.append(str(now))
print(' '.join(ans[::-1]))


import sys
sys.setrecursionlimit(99999999)
from collections import defaultdict
graph = defaultdict(set)
n = int(input())
arr = list(map(int, input().split()))
for i in range(len(arr)):
	graph[arr[i]].add(i + 2)
parent = [-1] * (n + 1)

def bfs():
	from collections import deque
	q = deque()
	q.append(1)
	visited = set()
	while q:
		u = q.popleft()
		visited.add(u)
		for v in graph[u]:
			if v not in visited:
				parent[v] = u
				q.append(v)
bfs()
path = [n]
v = n
while v != 1:
	v = parent[v]
	path.append(v)
path.reverse()
for x in path:
	print(x, end=' ')


n = int(input())
sp = [0] + list(map(int, input().split()))
t = n
r = [t]
while t > 1:
	r.append(sp[t - 1])
	t = sp[t - 1]
print(*r[::-1])


n = int(input())
graph = [0] + [int(i) for i in input().split()]
t = n
ans = []
while graph[t - 1] != 0:
	ans.append(t)
	t = graph[t - 1]
ans.append(1)
for i in range(len(ans) - 1, -1, -1):
	print(ans[i], end=' ')


n = int(input())
array = list(map(int, input().split()))
i = n - 2
result = []
while True:
	q = i + 2
	result.append(q)
	i = array[i] - 2
	if q <= 1:
		break
result.reverse()
print(' '.join(map(str, result)))


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())
a = [0, 0, *map(int, input().split())]
x = len(a) - 1
r = [x]
while x != 1:
	x = a[x]
	r += [x]
print(*r[::-1])


ans = [int(input())]
way = [int(i) for i in input().split()]
while ans[-1] != 1:
	ans.append(way[ans[-1] - 2])
print(*ans[::-1])


n = int(input())
a = [0]
a = a + list(map(int, input().split()))
b = []
i = n - 1
b.append(a[n - 1])
while a[i] != 1:
	i = a[i] - 1
	b.append(a[i])
b = b[::-1]
b.append(n)
print(' '.join(map(str, b)))


n = int(input())
p = [0, 0, *map(int, input().split())]
r = []
while n:
	r.append(n)
	n = p[n]
print(*reversed(r))


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())
A = list(map(int, input().split()))
B = []
B.append(n)
i = n - 2
while A[i] != 1:
	B.append(A[i])
	i = A[i] - 2
B.reverse()
print(1, end=' ')
for i in B:
	print(i, end=' ')


n = int(input())
parents = list(map(int, input().strip().split()))
cur = parents[-1] - 2
path = [n]
while 1:
	path.append(cur + 2)
	if cur == -1:
		break
	cur = parents[cur] - 2
path.reverse()
for i in path:
	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())
a = list(map(int, input().split()))
ans = []
ans.append(n)
x = n - 2
while a[x] != 1:
	ans.append(a[x])
	x = a[x] - 2
ans.append(1)
ans = ans[::-1]
for i in range(len(ans)):
	print(ans[i], end=' ')
print()


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


router_count = int(input())
router_connections = [int(val) - 1 for val in input().split()]
router_connections.insert(0, -1)
next_router = router_count - 1
path_from_last_to_first = []
while next_router >= 0:
	path_from_last_to_first.append(next_router + 1)
	next_router = router_connections[next_router]
path_from_last_to_first.reverse()
print(' '.join([str(x) for x in path_from_last_to_first]))


n = int(input())
p = list(map(int, input().split()))
ls = [n]
while n > 1:
	n = p[n - 2]
	ls.append(n)
print(*ls[::-1])


n = int(input())
a = [int(i) for i in input().split()]
ins = []
cur = n - 2
while a[cur] != 1:
	ins.append(a[cur])
	cur = a[cur] - 2
print(1, *ins[::-1], n)


N = int(input())
L = [int(s) for s in input().split(' ')]
R = [N]
i = N
while i != 1:
	R.append(L[i - 2])
	i = L[i - 2]
i = len(R) - 1
while i > 0:
	print(R[i], end=' ')
	i -= 1
print(R[i])


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


n = int(input())
a = [int(s) for s in input().split()]
b = [[] for i in range(n + 2)]
ans = []
for i in range(n - 1):
	b[i + 2].append(a[i])
prev = n
while len(b[prev]):
	ans.append(prev)
	prev = b[prev][0]
ans.append(1)
print(*reversed(ans))


t = int(input())
k = [int(w) for w in input().split(' ')]
a = [t, k[-1]]
i = k[-1]
while a[-1] != 1:
	a.append(k[i - 2])
	i = k[i - 2]
a.reverse()
ans = ''
for x in a:
	ans += str(x) + ' '
print(ans[:-1])


def main():
	n = int(input())
	a = [int(i) for i in input().split()]
	ans = []
	cur = n
	while cur != 1:
		ans += [cur]
		cur = a[cur - 2]
	print(1, *ans[::-1])
main()


import sys
data1 = sys.stdin.read()
data = data1.split('\n')
data.remove('')
n = int(data[0])
k = list(map(int, data[1].split(' ')))
p1 = n
p2 = 2
solve = [n]
while p1 > 1 and p2 > 1:
	p2 = k[p1 - 2]
	solve.append(p2)
	p2 = p2 - 2
	p1 = k[p2]
	if p1 >= 1 and p2 >= 1:
		solve.append(p1)
if solve.count(1) == 0:
	solve.append(1)
solve.reverse()
print(*solve)


n = int(input())
arr = list(map(int, input().split()))
stack = [n]
curr = arr[-1]
while True:
	stack.append(curr)
	if curr == 1:
		break
	curr = arr[curr - 2]
while len(stack) > 0:
	print(stack.pop(), end=' ')


n = int(input())
a = list(map(int, input().split()))
if len(set(a)) == n:
	a.append(n)
	print(*a)
else:
	a.insert(0, 0)
	b = [n]
	x = n
	while x != 1:
		b.append(a[x - 1])
		x = a[x - 1]
	print(*b[::-1])


n = int(input())
l = list(map(int, input().split()))
a = [n]
i = n - 2
while i >= 0:
	a.append(l[i])
	i = l[i] - 2
print(*a[::-1])


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


router_count = int(input())
router_connections = [int(x) for x in input().split(' ')]
router_path = [router_count]
current_index = router_count
while True:
	router_path.append(router_connections[current_index - 2])
	current_index = router_connections[current_index - 2]
	if current_index == 1:
		break
print(*router_path[::-1])


def Solution():
	routers = []
	path = []
	n = int(input())
	lis = input().split()
	i = n
	while i != 1:
		path.append(i)
		next_element = int(lis[i - 2])
		i = next_element
	path.append(1)
	x = ''
	for i in range(0, len(path)):
		if x != '':
			x = x + ' '
		x = x + str(path.pop())
	print(x)
Solution()


n = int(input())
p = [0, 0] + list(map(int, input().split()))
ans = [n]
i = p[n]
while i != 0:
	ans.append(i)
	i = p[i]
print(*ans[::-1])


n = int(input())
p = [0] + list(map(int, input().split()))
t = n
r = [t]
while t > 1:
	r.append(p[t - 1])
	t = p[t - 1]
print(*reversed(r))


n = int(input())
p = list(map(int, input().split()))
p = [0, 0] + p
path = []
cur = n
while cur != 0:
	path.append(cur)
	cur = p[cur]
for i in reversed(path):
	print(i, end=' ')


routing = [input()]
network = input().split()
while routing[-1] != '1':
	routing.append(network[int(routing[-1]) - 2])
print(' '.join(reversed(routing)))


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


n = int(input())
a = [-1, 0] + list(map(int, input().split()))
x = n
b = [n]
while a[x] != 1:
	x = a[x]
	b.append(x)
b.append(1)
for i in range(len(b) - 1, -1, -1):
	print(b[i], end=' ')


n = int(input())
routers = list(map(int, input().split(' ')))
ans = [n]
i = n - 2
while routers[i] != 1:
	ans.append(routers[i])
	i = routers[i] - 2
ans.append(1)
ans.reverse()
print(*ans)


import sys

def minp():
	return sys.stdin.readline().strip()
n = int(minp())
p = [None] * n
i = 0
for a in map(int, minp().split()):
	i += 1
	p[i] = a - 1
r = []
x = n - 1
while x != 0:
	r.append(x)
	x = p[x]
print(1, end='')
for i in range(len(r) - 1, -1, -1):
	print('', r[i] + 1, end='')


n = int(input())
p1 = input().split()
p = [int(x) for x in p1]
p.insert(0, 0)
ind = [x + 1 for x in range(n)]
ci = ind[-1]
cp = p[-1]
arr = []
while cp != 0:
	arr.append(ci)
	ci = ind[cp - 1]
	cp = p[cp - 1]
arr.append(1)
l = len(arr)
for i in range(l):
	(print(arr[l - i - 1], end=' '),)


n = int(input())
nums = list(map(int, input().split()))
nums = [0] + nums
routers = []
index = n
while index != 1:
	routers.append(index)
	index = nums[index - 1]
routers.append(1)
for i in reversed(range(len(routers))):
	print(routers[i], end=' ')


n = int(input())
l = [0]
l.extend(list(map(int, input().split())))
i = len(l) - 1
ans = []
while i > -1:
	ans.append(i + 1)
	i = l[i] - 1
ans.reverse()
print(' '.join((str(i) for i in ans)))


n = int(input())
a = [0] + [0] + [int(x) for x in input().strip().split()]
b = []
while a[n] >= 1:
	b.append(n)
	n = a[n]
b.append(1)
b.reverse()
b_new = (str(x) for x in b)
print(' '.join(b_new))


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)


import sys

def find_path(p_list):
	curr = len(p_list) + 1
	path = [curr]
	while curr != 1:
		curr = p_list[curr - 2]
		path.append(curr)
	path.reverse()
	return path
n = int(input())
p_list = list(map(int, sys.stdin.readline().split()))
path = find_path(p_list)
print(*path, sep=' ')


r = int(input())
l = list(map(int, input().split(' ')))
x = []
a = len(l) - 1
while l[a] != 1:
	x.append(a + 2)
	a = l[a] - 2
x.append(a + 2)
x.append(1)
x.reverse()
for i in x:
	print(i, end=' ')


n = int(input())
p = list(map(lambda x: int(x), input().split()))
path = [n]
t = n
while t != 1:
	t = p[t - 2]
	path.append(t)
print(path[len(path) - 1], end='', sep='')
for i in range(len(path) - 2, -1, -1):
	print(' ', path[i], end='', sep='')


import math
import time
from collections import defaultdict, deque
from sys import stdin, stdout
from bisect import bisect_left, bisect_right
n = int(input())
a = list(map(int, stdin.readline().split()))
ans = deque()
ans.appendleft(n)
while ans[0] != 1:
	ans.appendleft(a[ans[0] - 2])
print(*ans)


input_0 = input()
input_1 = input()
value = int(input_0)
tree = [0]
i = 0
wow = ''
for j in range(len(input_1)):
	if input_1[j] == ' ':
		tree.append(int(wow))
		wow = ''
	elif j == len(input_1) - 1:
		wow = wow + input_1[j]
		tree.append(int(wow))
	else:
		wow = wow + input_1[j]
ans = []
element = value
while element > 0:
	ans.append(element)
	element = tree[element - 1]
real_ans = ''
yee = len(ans)
for j in range(yee):
	part = yee - 1 - j
	if j > 0:
		real_ans = real_ans + ' '
	real_ans = real_ans + str(ans[part])
print(real_ans)


n = int(input())
P = list(map(int, input().split(' ')))
path = [n]
i = n
while P[i - 2] != 1:
	path.append(P[i - 2])
	i = P[i - 2]
path.append(1)
answer = ' '.join(list(map(str, path[::-1])))
print(answer)


from collections import deque
from collections import OrderedDict
import math
import sys
import os
from io import BytesIO
import threading
import bisect
import heapq
input = lambda : sys.stdin.readline().rstrip('\r\n')
n = int(input())
ar = [0, 0] + list(map(int, input().split()))
value = n
answer = []
while value != 0:
	answer.append(value)
	value = ar[value]
answer.reverse()
for i in range(len(answer)):
	print(answer[i], end=' ')


n = int(input())
d = {}
st = input().split()
for i in range(0, len(st)):
	d[str(i + 2)] = st[i]
cur = str(n)
answ = []
while 1:
	answ.append(cur)
	cur = d[cur]
	if cur == '1':
		answ.append('1')
		break
print(' '.join(answ[::-1]))


n = int(input())
parents = [0, 0] + list(map(int, input().split()))
cur = n
ans = []
while cur > 1:
	ans += [cur]
	cur = parents[cur]
ans += [1]
for i in range(len(ans) - 1, -1, -1):
	print(ans[i], end=' ')


n = int(input())
a = list(map(int, input().split()))
s = {q + 2: a[q] for q in range(len(a))}
answer = [n]
q1 = n
while q1 != 1:
	q1 = s[q1]
	answer.append(q1)
print(*answer[::-1])


n = int(input())
s = list(map(int, input().split()))
s = [0, 0] + s
ans = []
while n != 1:
	ans.append(n)
	n = s[n]
ans.append(1)
ans.reverse()
print(*ans)


n = int(input())
a = list(map(int, input().split()))
a.insert(0, 0)
res = [len(a)]
i = len(a) - 1
while True:
	if i == 0:
		break
	res.append(a[i])
	i = a[i] - 1
print(' '.join(map(str, reversed(res))))


n = int(input())
lst = {i: int(x) for (i, x) in enumerate(input().split())}
(res, a) = ([n], n)
while a != 1:
	a = lst[a - 2]
	res.append(a)
res.reverse()
print(*res)


n = input()
arr = input().split()
arr = list(map(int, arr))
res = []
res.append(int(n))
j = 0
while res[j] != 1:
	res.append(arr[res[j] - 2])
	j += 1
arr = list(map(str, arr))
print(' '.join(list(map(str, res[::-1]))))


from sys import stdin, stdout
n = int(stdin.readline())
a = list(map(int, stdin.readline().split()))
last = n - 2
ans = []
while a[last] != 1:
	last = a[last]
	ans.append(last)
	last -= 2
ans = [1] + ans[::-1] + [n]
for node in ans:
	stdout.write('{} '.format(node))


n = int(input())
a = list(map(int, input().split()))
b = [n]
i = n - 2
while a[i] != 1:
	b.append(a[i])
	i = a[i] - 2
b.append(1)
b.reverse()
print(*b)


from sys import stdin, stdout, setrecursionlimit
import heapq
from math import gcd, ceil, sqrt
from collections import Counter, deque
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations
ii1 = lambda : int(stdin.readline().strip())
is1 = lambda : stdin.readline().strip()
iia = lambda : list(map(int, stdin.readline().strip().split()))
isa = lambda : stdin.readline().strip().split()
setrecursionlimit(100000)
mod = 1000000007
n = ii1()
arr = [0] + iia()
res = []
while n != 0:
	res.append(n)
	n = arr[n - 1]
print(*res[::-1])


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())
ar = [0, 0] + list(map(int, input().split()))
cur = n
ans = []
while cur > 1:
	ans.append(cur)
	cur = ar[cur]
ans.append(1)
print(*ans[::-1])


n = int(input())
connections = list(map(int, input().split()))
path = [n]
i = n - 2
while i >= 0:
	i = connections[i]
	path.append(i)
	i -= 2
m = len(path)
for i in range(m - 1, -1, -1):
	print(path[i], end=' ')


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())
ls = list(map(int, input().split()))
parent = [0] + ls
cur = N - 1
ans = [N]
while parent[cur] != 0:
	ans.append(parent[cur])
	cur = parent[cur] - 1
ans.reverse()
for i in ans:
	print(i, end=' ')
print()


n = int(input())
l = [0, 0] + list(map(int, input().split()))
ans = []
while n:
	ans.append(n)
	n = l[n]
print(*reversed(ans))


count = int(input())
routers = list(map(int, input().split()))
output = []
count1 = count
while count1 != 1:
	count1 = routers[count1 - 2]
	output.append(count1)
print(*output[::-1], end=' ')
print(count)


import os
import sys
from io import BytesIO, IOBase
import math
from decimal import *
getcontext().prec = 25
MOD = pow(10, 9) + 7
BUFSIZE = 8192
from collections import defaultdict

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
n = int(input())
l = [0, 0] + list(map(int, input().split(' ')))
r = []
while n:
	r.append(n)
	n = l[n]
print(*reversed(r))


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


amount = int(input())
c = input()
new = c.split(' ')
for y in range(amount - 1):
	new[y] = int(new[y])
routers = new
largest = 0
num = amount
path = [amount]
while num != 1:
	num = routers[num - 2]
	path.append(num)
path.reverse()
ans = ''
for printer in range(len(path)):
	ans += str(path[printer]) + ' '
print(ans)


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


n = int(input())
a = list(map(int, input().split()))
l = [n, a[-1]]
p = a[-1]
while a[p - 2] != 1:
	l.append(a[p - 2])
	p = a[p - 2]
if l[-1] != 1:
	l.append(1)
l.reverse()
print(*l)


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))))


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()


def input_ints():
	return list(map(int, input().split()))

class Tree:

	def __init__(self, parent=None):
		self.parent = parent
		if parent is not None:
			parent.add_child(self)
		self.children = list()

	def add_child(self, child):
		self.children.append(child)
n = int(input())
prevs = input_ints()
t = Tree()
nodes = [t]
setattr(nodes[-1], 'id', 1)
for (id, parent_id) in enumerate(prevs):
	nodes.append(Tree(nodes[parent_id - 1]))
	setattr(nodes[-1], 'id', id + 2)
route = [nodes[-1]]
while route[-1].parent is not None:
	route.append(route[-1].parent)
print(' '.join(map(lambda x: str(x.id), reversed(route))))


n = int(input())
masukan = [int(item) for item in input().split(' ')]
dictRouter = dict(zip([i + 2 for i in range(n - 1)], masukan))
res = []

def cari(n):
	while dictRouter[n] != 1:
		res.append(n)
		n = dictRouter[n]
	res.append(n)
	res.append(1)
cari(n)
print(' '.join([str(i) for i in sorted(res)]))


class Node(object):

	def __init__(self, data, children=[], father=None):
		self.data = data
		self.children = children
		self.father = father

	def add_child(self, obj):
		self.children.append(obj)

	def __str__(self):
		exp = str(self.data) + ' ' + str(self.father) + '\n'
		for i in self.children:
			exp += '\n' + str(i.data)
		return exp

class Tree(dict):

	def __add_element__(self, item):
		self.tree.append(item)
n = int(input())
attach = [int(i) for i in input().split()]
tree = Tree()
tree.__setitem__(1, Node(1))
for i in range(len(attach)):
	tree.__setitem__(i + 2, Node(i + 2, [], attach[i]))
	tree.__getitem__(attach[i]).add_child(Node(i + 2))
father = tree.__getitem__(n).father
path = [father]
while father != 1 and father is not None:
	father = tree.__getitem__(father).father
	path.append(father)
exp = ''
for i in range(len(path) - 1, -1, -1):
	exp += str(path[i]) + ' '
exp += str(n)
print(exp)


n = int(input())
d = {}
l = list(map(int, input().split()))
for i in range(len(l)):
	d[i + 2] = l[i]
x = 0
l = [n]
while x == 0:
	if d.get(l[-1]) == 1:
		l.append(1)
		break
	l.append(d.get(l[-1]))
l.reverse()
print(*l)


class CodeforcesTask1057ASolution:

	def __init__(self):
		self.result = ''
		self.n = 0
		self.routers = []

	def read_input(self):
		self.n = int(input())
		self.routers = [int(x) for x in input().split(' ')]

	def process_task(self):
		s = [self.n]
		x = self.n
		while x != 1:
			step = self.routers[x - 2]
			x = step
			s.append(step)
		while s:
			print(s.pop(-1), end=' ')

	def get_result(self):
		return self.result
Solution = CodeforcesTask1057ASolution()
Solution.read_input()
Solution.process_task()
print(Solution.get_result())


from sys import stdin, stdout
import math, sys, heapq
from itertools import permutations, combinations
from collections import defaultdict, deque, OrderedDict
from os import path
import random
import bisect as bi

def yes():
	print('YES')

def no():
	print('NO')
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

	def I():
		return int(input())

	def In():
		return map(int, input().split())
else:

	def I():
		return int(stdin.readline())

	def In():
		return map(int, stdin.readline().split())

def dict(a):
	d = {}
	for x in a:
		if d.get(x, -1) != -1:
			d[x] += 1
		else:
			d[x] = 1
	return d

def find_gt(a, x):
	i = bi.bisect_left(a, x)
	if i != len(a):
		return i
	else:
		return -1

def main():
	try:
		n = I()
		l = [0, 0] + list(In())
		path = []
		i = n
		while l[i] != 0:
			path.append(i)
			i = l[i]
		path.append(1)
		print(*path[::-1])
	except:
		pass
M = 998244353
P = 1000000007
for _ in range(1):
	main()


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=' ')


n = int(input())
arr = list(map(int, input().split()))
graph = {}
for (marsh, prev_marsh) in enumerate(arr, 2):
	graph[marsh] = prev_marsh
cur_vertex = n
path = [n]
while cur_vertex != 1:
	cur_vertex = graph[cur_vertex]
	path.append(cur_vertex)
print(' '.join(map(str, reversed(path))))


from collections import Counter
import heapq
from collections import Counter
n = int(input())
p = list(map(int, input().split()))
pa = n
ans = []
while True:
	ans.append(pa)
	if pa == 1:
		break
	pa = p[pa - 2]
print(*ans[::-1])


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())
way = list(map(int, input().split()))
N = list()
m = max(way)
for i in range(m + 1):
	N.append(set())
for i in range(n - 2, -1, -1):
	N[way[i]].add(i + 2)
tree = list()
value = n
tree.append(n)
for i in range(m, 0, -1):
	if value in N[i]:
		tree.append(i)
		value = i
for num in reversed(tree):
	print(str(num) + ' ', end='')


n = int(input())
fa = [0, 0] + list(map(int, input().split()))
ans = []
while n:
	ans += [n]
	n = fa[n]
print(*ans[::-1])


n = int(input())
l = list(map(int, input().split()))
ans = [n]
i = n - 2
while l[i] != 1:
	ans.append(l[i])
	i = l[i] - 2
ans.append(1)
ans.reverse()
for x in ans:
	print(x, end=' ')


n = int(input())
a = list(map(int, input().split()))
b = [n]
i = len(a) - 1
while i > 0:
	b.append(a[i])
	i = a[i] - 2
if b[len(b) - 1] != 1:
	print(1, *b[::-1])
else:
	print(*b[::-1])


import math
x = int(input())
p = list(map(int, input().split()))
ans = []
sz = 0
while x > 1:
	ans.append(x)
	x = p[x - 2]
	sz += 1
ans.append(1)
sz += 1
for i in range(1, sz + 1):
	print(ans[sz - i])


n = int(input())
l = list(map(int, input().split()))
l1 = [n]
i = n - 2
while l[i] != 1:
	l1.append(l[i])
	i = l[i] - 2
l1.append(1)
l1.reverse()
print(*l1)


n = int(input())
l = list(map(int, input().split()))
way = [n]
last = l[len(l) - 1]
way.append(last)
while last != 1:
	ind_l = last - 2
	last = l[ind_l]
	way.append(last)
way = way[::-1]
for i in way:
	print(i, end=' ')


n = int(input())
pi = list(map(int, input().split()))
path = [n]
i = pi[-1]
while i != 1:
	path += [i]
	i = pi[i - 2]
path += [1]
for i in range(len(path) - 1, -1, -1):
	print(path[i], end=' ')


from collections import defaultdict as dd
from collections import deque
import bisect
import heapq

def ri():
	return int(input())

def rl():
	return list(map(int, input().split()))
n = ri()
pp = rl()
aa = [-1] + [x - 1 for x in pp]
path = [n - 1]
i = n - 1
while i > 0:
	router = aa[i]
	path.append(router)
	i = router
print(' '.join([str(x + 1) for x in path[::-1]]))


n = int(input())
par = [None] * 2 + list(map(int, input().split(' ')))
i = len(par) - 1
stack = []
while par[i] != 1:
	i = par[i]
	stack.append(i)
print('1 ' + ' '.join(list(map(str, stack[::-1]))) + ' ' + str(len(par) - 1))


n = input()
p = list(map(int, input().split()))
d = [n]
c = p[-1]
while True:
	if d[-1] != '1 ':
		d.append(str(c) + ' ')
		c = p[c - 2]
	else:
		break
b = ''
for x in d[::-1]:
	b += x
print(b)


n = int(input())
l = list(map(int, input().strip().split(' ')))
v = n
route = [v]
while v != 1:
	v = l[v - 2]
	route.append(v)
print(*route[::-1])


n = int(input())
x = list(map(int, input().split()))
y = []
y.append(n)
i = n - 2
while x[i] != 1:
	y.append(x[i])
	i = x[i] - 2
y.append(1)
print(*y[::-1])


def findRoot(n, network):
	vertex = []
	vertex.append(n)
	while network[str(n)] != 0:
		vertex.append(network[str(n)])
		n = network[str(n)]
	return vertex
n = int(input())
pathDict = {'1': 0}
pathArr = list(map(int, input().rstrip().split()))
for i in range(n - 1):
	pathDict[str(i + 2)] = pathArr[i]
findedVertex = findRoot(n, pathDict)
sortedVertex = sorted(findedVertex)
print(*sortedVertex, sep=' ')


def main():
	n = int(input())
	p = list(map(int, input().split()))
	path = [n]
	parent = n - 2
	while p[parent] != 1:
		path.append(p[parent])
		parent = p[parent] - 2
	path.append(p[parent])
	answer = ''
	path.reverse()
	for pa in path:
		answer += str(pa) + ' '
	print(answer)
main()


def fun(l):
	l.insert(0, 0)
	l.insert(0, 0)
	x = []
	i = len(l) - 1
	while i != 0:
		x.append(i)
		i = l[i]
	x.reverse()
	return x
n = input()
l = [int(x) for x in list(input().split())]
for i in fun(l):
	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=' ')


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)]))


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))


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


def findfirst(n, p):
	if p == list(range(1, n)):
		p.append(n)
		p = list(map(str, p))
		return ' '.join(p)
	else:
		ans = [str(n)]
		start = len(p) - 1
		while ans[0] != '1':
			ans.insert(0, str(p[start]))
			start = p[start] - 2
		return ' '.join(ans)
n = int(input())
p = list(map(int, input().split()))
print(findfirst(n, p))


from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict

def find_path(start, end, parents):
	(path, parent) = ([], end)
	while parent != parents[start]:
		path.append(parent)
		parent = parents[parent]
	return path[::-1]
router_count = int(input())
connections = list(map(int, input().split()))
graph = defaultdict()
graph[1] = 0
for (node, parent) in enumerate(connections, 2):
	graph[node] = parent
paths = find_path(1, router_count, graph)
print(*paths)


n = int(input())
p = [int(i) for i in input().split(' ')]
res = [n]
while n > 0:
	n -= 2
	if n < 0:
		break
	res.append(p[n])
	if n <= 0:
		break
	n = p[n]
res = res[::-1]
st = ''
for i in res:
	if st == '':
		st = str(i)
	else:
		st += ' ' + str(i)
print(st)


n = int(input())
a = list(map(int, input().split()))
i = n - 2
ans = [n]
while a[i] != 1:
	ans.append(a[i])
	i = a[i] - 2
print(1, *ans[::-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)))


n = int(input())
lst = [0 for i in range(n)]
lst[0] = -1
exc = []
cur = input().split()
for i in range(n - 1):
	lst[i + 1] = int(cur[i]) - 1
temp = n - 1
while temp != -1:
	exc.append(temp + 1)
	temp = lst[temp]
for i in reversed(range(exc.__len__())):
	print(exc[i], end=' ')


n = int(input())
a = list(map(int, input().split()))
b = []
a = [1] + a
i = len(a)
b.append(i)
while i != 1:
	m = a[i - 1]
	b.append(m)
	i = m
b.reverse()
print(*b)


def solve(n, a):
	res = [str(n)]
	index = n
	while index != 1:
		index = a[index - 2]
		res.append(str(index))
	return ' '.join(res[::-1])

def main():
	n = int(input())
	a = [int(i) for i in input().split()]
	print(solve(n, a))
main()


from collections import deque
(n, P) = (int(input()), [0, 0, *map(int, input().split())])
(i, path) = (n, deque())
while i:
	path.appendleft(i)
	i = P[i]
print(*path)


n = int(input())
a = list(map(int, input().split()))
i = n - 2
l = [n]
while i > 0 and a[i] != 1:
	l.append(a[i])
	i = a[i] - 2
l.append(1)
for i in range(len(l) - 1, -1, -1):
	print(l[i], end=' ')
print()


n = int(input())
x = [int(i) for i in input().split()]
a = set()
a.add(n)
i = n - 2
while i > 0:
	a.add(x[i])
	i = x[i] - 2
a.add(1)
a = sorted(a)
for i in a:
	print(i, end=' ')


n = int(input())
p = [int(s) for s in input().split()]
ans = [n]
while ans[-1] != 1:
	ans.append(p[ans[-1] - 2])
print(*reversed(ans))


n = int(input())
p = list(map(int, input().split()))
output = [n]
i = n - 2
while i >= 0:
	output.append(p[i])
	i = p[i] - 2
print(*output[::-1])


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())
routers = [int(s) for s in input().split(' ')]
current = n
path = [current]
while current != 1:
	current = routers[current - 2]
	path.append(current)
new_path = []
for i in range(len(path)):
	new_path.append(path[len(path) - 1 - i])
print(' '.join([str(x) for x in new_path]))


a = [0, 0, *map(int, [*open(0)][1].split())]
x = len(a) - 1
r = [x]
while x != 1:
	x = a[x]
	r += [x]
print(*r[::-1])


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


n = int(input())
l = list(map(int, input().split()))
ans = []
ptr = l[-1]
ans.append(n)
while True:
	ans.append(ptr)
	if ans[-1] == 1:
		break
	ptr = l[ptr - 2]
ans.reverse()
for i in range(len(ans)):
	print(ans[i], end=' ')


from sys import stdin, stdout
from math import gcd, sqrt
from collections import deque
input = stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\n')
L = lambda : list(R())
P = lambda x: stdout.write(x)
hg = lambda x, y: (y + x - 1) // x * x
pw = lambda x: 1 if x == 1 else 1 + pw(x // 2)
chk = lambda x: chk(x // 2) if not x % 2 else True if x == 1 else False
N = 10 ** 6 + 7
n = I()
p = [0] + L()
i = n - 1
ans = []
while p[i] != 0:
	ans += (i + 1,)
	i = p[i] - 1
print(1, *ans[::-1])


import sys
from collections import deque
input = sys.stdin.readline

def main():
	n = int(input())
	a = list(map(int, input().split()))
	graph = {i + 1: set() for i in range(n)}
	for i in range(n - 1):
		graph[a[i]].add(i + 2)
		graph[i + 2].add(a[i])
	start_vertex = 1
	end_vertex = n
	distances = [None] * (n + 1)
	parents = [None] * (n + 1)
	distances[start_vertex] = 0
	queue = deque([start_vertex])
	while queue:
		cur_v = queue.popleft()
		for neigh_v in graph[cur_v]:
			if distances[neigh_v] is None:
				parents[neigh_v] = cur_v
				distances[neigh_v] = distances[cur_v] + 1
				queue.append(neigh_v)
	path = [end_vertex]
	parent = parents[end_vertex]
	while not parent is None:
		path.append(parent)
		parent = parents[parent]
	print(*path[::-1])
main()


from sys import stdin
getc = lambda : stdin.read(1)

def alph():
	a = list(range(65, 91))
	b = list(range(97, 123))
	return set([chr(i) for i in a + b])

def cin(T='int'):
	d = {'int': {'1', '2', '3', '4', '5', '6', '7', '8', '9', '0'}, 'str': alph()}
	a = getc()
	res = ''
	while a in d[T]:
		res += a
		a = getc()
	if T == 'int':
		return int(res)
	return res

def printv(a, sep='\n'):
	print(sep.join(map(str, a)))

def bruh():
	n = cin('int')
	a = [cin('int') for i in range(n - 1)]
	ans = []
	cur = n
	while cur != 1:
		ans += [cur]
		cur = a[cur - 2]
	ans += [1]
	printv(ans[::-1], ' ')
bruh()


n = int(input())
a = [0] + [int(s) for s in input().split()]
i = n - 1
b = []
while a[i] != 0:
	b.append(str(i + 1))
	i = a[i] - 1
b.append('1')
b = b[::-1]
print(' '.join(b))


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())
p = tuple(map(int, input().split()))
path = [n]
while path[-1] != 1:
	path.append(p[path[-1] - 2])
print(*reversed(path))


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())
arr = list(map(int, input().split()))
ans = [n]
currNode = n - 2
while arr[currNode] != 1:
	ans.append(arr[currNode])
	currNode = arr[currNode] - 2
ans.append(1)
l = len(ans)
for i in range(l - 1, -1, -1):
	print(ans[i], end=' ')


n = int(input())
connection_history = input().split()
out_list = [str(n)]
curr = connection_history[-1]
while curr != '1':
	out_list.append(curr)
	curr = connection_history[int(curr) - 2]
out_str = '1'
out_list.reverse()
for el in out_list:
	out_str += ' ' + el
print(out_str)


N = int(input())
m = [0, 0] + list(map(int, input().split()))
d = N
ans = [N]
while d > 1:
	d = m[d]
	ans.append(d)
print(' '.join(map(str, ans[::-1])))


(Answer, N, Sequence) = ([], int(input()), list(map(int, input().split())))
Answer.append(N)
Index = N - 2
while Sequence[Index] != 1:
	Answer.append(Sequence[Index])
	Index = Sequence[Index] - 2
print(1, *Answer[::-1])


N = int(input())
P = list(map(int, input().split()))
rec = []
P = [0, 0] + P
while N > 0:
	rec.append(N)
	N = P[N]
print(' '.join(map(str, rec[::-1])))


tar = int(input())
arr = input().split()
p = dict()
for (idx, num) in enumerate(map(int, arr), 2):
	p[idx] = num
path = [tar]
while tar != 1:
	path.append(p[tar])
	tar = p[tar]
print(' '.join(map(str, path[::-1])))


n = int(input())
pl = list(map(int, input().split()))
ll = [n]
while ll[-1] > 1:
	ll.append(pl[ll[-1] - 2])
ll.reverse()
print(*ll)


n = int(input())
p = list(map(int, input().split()))
rec = []
p = [0, 0] + p
while n > 0:
	rec.append(n)
	n = p[n]
print(' '.join(map(str, rec[::-1])))


from collections import defaultdict as defdic
from collections import deque

class Graph:

	def __init__(self):
		self.graph = defdic(list)

	def addedge(self, u, v):
		self.graph[u].append(v)

	def BFS(self, u):
		visited = defdic(int)
		qu = deque()
		qu.append(u)
		visited[u] = True
		x = []
		while qu:
			s = qu.popleft()
			x.append(s)
			for i in self.graph[s]:
				if visited[i] == 0:
					qu.append(i)
					visited[i] = True

	def DFSUtil(self, s, visited, k):
		stack = []
		dpt = {}
		stack.append(s)
		while len(stack) != 0:
			s = stack[-1]
			if not visited[s]:
				k.add(s)
				visited[s] = True
				dpt[s] = len(k)
			else:
				s = stack.pop()
				k.remove(s)
				continue
			if s == self.lens:
				k = sorted(k)
				for j in k:
					print(j, end=' ')
				return 0
			l = 0
			for i in self.graph[s]:
				if not visited[i]:
					stack.append(i)
					l += 1
		return 1

	def DFS(self):
		k = set()
		visited = defdic(int)
		for i in self.graph:
			if not visited[i]:
				x = self.DFSUtil(i, visited, k)
				if x == 0:
					return
n = int(input())
s = list(map(int, input().split()))
g = Graph()
for i in range(2, n):
	g.addedge(s[i - 2], i)
g.addedge(s[n - 2], n)
g.lens = n
k = g.DFS()


n = int(input())
li = list(map(int, input().split()))
q = li[n - 2]
path = [n]
while q > 1:
	path.append(q)
	q = li[q - 2]
print(1, end=' ')
for i in range(len(path) - 1, -1, -1):
	print(path[i], end=' ')


n = int(input())
a = list(map(int, input().split(' ')))
x = a[len(a) - 1]
b = {n, a[0]}
while x - 1 > 0:
	b.add(x)
	x = a[x - 2]
print(' '.join([str(i) for i in sorted(b)]))


from sys import stdin
getc = lambda : stdin.read(1)

def cin(T='int'):
	a = getc()
	res = ''
	while a in {'1', '2', '3', '4', '5', '6', '7', '8', '9', '0'}:
		res += a
		a = getc()
	if T == 'int':
		return int(res)
	return res

def printv(a, sep='\n'):
	print(sep.join(map(str, a)))

def bruh():
	n = cin('int')
	a = [cin('int') for i in range(n - 1)]
	ans = []
	cur = n
	while cur != 1:
		ans += [cur]
		cur = a[cur - 2]
	ans += [1]
	printv(ans[::-1], ' ')
bruh()


n = int(input())
routers = list(map(int, input().split()))
output = []
output.append(n)
i = n - 2
while routers[i] != 1:
	output.append(routers[i])
	i = routers[i] - 2
output.append(1)
print(*output[::-1], sep=' ')


N = int(input())
arr = [int(x) for x in input().split()]
d = {1: 0}
nodes = []
for (index, num) in enumerate(arr):
	d[index + 2] = num
while N:
	nodes.append(N)
	N = d[N]
print(*nodes[::-1])


n = int(input())
index = list(map(int, input().split()))
key = index[n - 2]
k = 0
final = [n, key]
while k == 0:
	key = index[key - 2]
	final.append(key)
	if key == 1:
		k = 1
		break
final = list(set(final))
final.sort()
print(*final)


n = int(input())
p = dict(zip(range(2, n + 1), (int(x) for x in input().split())))
r = [n]
k = n
while k != 1:
	k = p[k]
	r.append(k)
r.reverse()
print(*r)


n = int(input())
a = list(map(int, input().split()))
c = [n]
i = a[n - 2]
while i != 1:
	c.append(i)
	i = a[i - 2]
c.append(i)
c.reverse()
for i in c:
	print(i, end=' ')
print()


n = int(input())
l1 = [1] + [int(x) for x in input().split()]
targ = n
places = []
while targ != 1:
	places.append(targ)
	targ = l1[targ - 1]
places.append(1)
places.reverse()
print(*places)


import collections
N = int(input())
A = [-1, -1] + [int(x) for x in input().split()]
ans = []
s = N
while s > 0:
	ans.append(s)
	s = A[s]
print(' '.join(map(str, reversed(ans))))


N = int(input())
nums = [0] + list(map(int, input().split()))
path = []
idx = N - 1
while idx != 0:
	path.append(idx + 1)
	idx = nums[idx] - 1
path.append(1)
path.reverse()
print(' '.join(map(str, path)))


from collections import deque

class Graph:

	def __init__(self, n):
		self.size = n
		self.g = [[] for _ in range(n)]

	def addEdge(self, u, v):
		self.g[u].append(v)
		self.g[v].append(u)

	def findPath(self, _from, _to):
		queue = deque()
		visited = [False] * self.size
		parent = [i for i in range(self.size)]
		queue.append(_from)
		while queue:
			u = queue.popleft()
			visited[u] = True
			if u == _to:
				break
			for v in self.g[u]:
				if not visited[v]:
					parent[v] = u
					queue.append(v)
		path = []
		curr = _to
		while curr != parent[curr]:
			path.append(curr)
			curr = parent[curr]
		path.append(_from)
		path.reverse()
		return path

def main():
	n = int(input())
	g = Graph(n)
	for (u, v) in enumerate(map(int, input().split())):
		g.addEdge(u + 1, v - 1)
	path = g.findPath(0, n - 1)
	print(*(i + 1 for i in path))
main()


import sys, bisect
from sys import stdin, stdout
from bisect import bisect_left, bisect_right, bisect, insort, insort_left, insort_right
from math import gcd, ceil, floor, sqrt
from collections import Counter, defaultdict, deque, OrderedDict
from queue import Queue, PriorityQueue
from string import ascii_lowercase
from heapq import *
from itertools import islice
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 998244353
mod = 10 ** 9 + 7

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	for i in range(5, ceil(sqrt(n)) + 1, 6):
		if n % i == 0 or n % (i + 2) == 0:
			return False
	return True

def st():
	return list(stdin.readline().strip())

def inp():
	return int(stdin.readline())

def li():
	return list(map(int, stdin.readline().split()))

def mp():
	return map(int, stdin.readline().split())

def pr(n):
	stdout.write(str(n) + '\n')

def DFS(dictionary, vertex, visited):
	visited[vertex] = True
	stack = [vertex]
	print(vertex)
	while stack:
		a = stack.pop()
		for i in dictionary[a]:
			if not visited[i]:
				print(i)
				visited[i] = True
				stack.append(i)

def BFS(dictionary, vertex, visited):
	visited[vertex] = True
	q = deque()
	q.append(vertex)
	while q:
		a = q.popleft()
		for i in dictionary[a]:
			if not visited[i]:
				visited[i] = True
				q.append(i)
				print(i)

def soe(limit):
	l = [1] * (limit + 1)
	l[0] = 0
	l[1] = 0
	prime = []
	for i in range(2, limit + 1):
		if l[i]:
			for j in range(i * i, limit + 1, i):
				l[j] = 0
	for i in range(2, limit + 1):
		if l[i]:
			prime.append(i)
	return prime

def segsoe(low, high):
	limit = int(high ** 0.5) + 1
	prime = soe(limit)
	n = high - low + 1
	l = [0] * (n + 1)
	for i in range(len(prime)):
		lowlimit = low // prime[i] * prime[i]
		if lowlimit < low:
			lowlimit += prime[i]
		if lowlimit == prime[i]:
			lowlimit += prime[i]
		for j in range(lowlimit, high + 1, prime[i]):
			l[j - low] = 1
	for i in range(low, high + 1):
		if not l[i - low]:
			if i != 1:
				print(i)

def gcd(a, b):
	while b:
		a = a % b
		(b, a) = (a, b)
	return a

def power(a, n):
	r = 1
	while n:
		if n & 1:
			r = r * a
		a *= a
		n = n >> 1
	return r

def dfs(d, i, n, par, visited):
	visited[i] = True
	stack = [i]
	while stack:
		a = stack.pop()
		if a == n:
			break
		for i in d[a]:
			if not visited[i]:
				visited[i] = True
				par[i] = a
				stack.append(i)
	x = n
	l = [n]
	while par[x] != -1:
		l.append(par[x])
		x = par[x]
	for i in range(len(l) - 1, -1, -1):
		print(l[i], end=' ')

def solve():
	n = inp()
	l = li()
	d = {i: [] for i in range(1, n + 1)}
	par = {i: -1 for i in range(1, n + 1)}
	for i in range(n - 1):
		d[i + 2].append(l[i])
		d[l[i]].append(i + 2)
	visited = [False for i in range(n + 1)]
	dfs(d, 1, n, par, visited)
for _ in range(1):
	solve()


n = int(input())
graf = [[] for i in range(n)]
acc_index = 1
numbers = list(map(int, input().split()))
for index in numbers:
	graf[index - 1].append(acc_index)
	acc_index += 1
close = [-1 for i in range(n)]
close[0] = 0
bfs = [0]
for val in bfs:
	for node in graf[val]:
		if close[node] == -1:
			close[node] = val
			bfs.append(node)
path = []
acc_node = n - 1
while acc_node != 0:
	path.append(acc_node)
	acc_node = close[acc_node]
path.append(0)
path.reverse()
for val in path:
	print(val + 1)


n = int(input())
m = [int(i) for i in input().split()]
idxs = [j for j in range(2, n + 1)]
temp = []
for (k, v) in zip(m[::-1], idxs[::-1]):
	temp.append((k, v))
res = []
res.append(n)
num = temp[0][0]
for i in temp:
	if i[1] == num:
		res.append(num)
		num = i[0]
res.append(1)
s = ' '.join((str(i) for i in res[::-1]))
print(s)


n = int(input())
a = list(map(int, input().split()))
vertex = n
guys = []
while vertex > 1:
	guys.append(vertex)
	vertex = a[vertex - 2]
guys.append(1)
guys.reverse()
one = ''
for i in guys:
	one += str(i) + ' '
print(one[:-1])


n = int(input().strip())
x = [0, 0]
x.extend(map(int, input().strip().split()))
ans = [n]
cur = n
while cur != 1:
	cur = x[cur]
	ans.append(cur)
ans.reverse()
print(' '.join(map(str, ans)))


from collections import deque
n = int(input())
conn = [int(num) for num in input().split()]
conn.insert(0, 0)
conn.insert(0, 0)
output = deque(str(n))
current = n
while current != 1:
	current = conn[current]
	output.extendleft(' ' + str(current)[::-1])
print(''.join(output))


n = int(input())
l = list(map(int, input().split()))
d = [n]
x = n - 2
while l[x] != 1:
	d.append(l[x])
	x = l[x] - 2
d.append(1)
print(*d[::-1])


import sys
n = int(input())
a = input().split()
d = {}
for (k, v) in enumerate(a):
	d[k + 2] = int(v)
r = []
next = n
while next != 1:
	r.append(str(next))
	next = d[next]
r.reverse()
print('1', ' '.join(r))


n = int(input())
path = list(map(int, input().split(' ')))
res = [n]
index = -1
while True:
	index = path[index] - 2
	if index <= -1:
		break
	res.append(index + 2)
print(1, end=' ')
for i in reversed(res):
	print(i, end=' ')


n = int(input())
l = list(map(int, input().split()))
d = dict()
for i in range(n - 1):
	d[i + 2] = l[i]
ans = []
pos = n
while pos != 1:
	ans.append(pos)
	pos = d[pos]
ans.append(1)
print(*reversed(ans))


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=' ')


n = int(input())
answ = []
fl = n
put = list(map(int, input().split()))
while fl != put[0]:
	answ.append(fl)
	fl = put[fl - 2]
answ.append(fl)
print(*reversed(answ))


n = int(input())
tree = list(map(int, input().split()))
n -= 2
path = []
while n > 0:
	path.append(n + 2)
	n = tree[n] - 2
path.append(n + 2)
if path[-1] != 1:
	path.append(1)
for i in path[::-1]:
	print(i, end=' ')


import queue

def bfs(graph, v_source, n_vertex):
	INF = 2 ** 31 - 1
	v_dest = n_vertex - 1
	q = queue.Queue()
	visited = [False for i in range(n_vertex)]
	shortest_dists = [INF for i in range(n_vertex)]
	parents = [None for i in range(n_vertex)]
	shortest_dists[v_source] = 0
	visited[v_source] = True
	q.put(v_source)
	while not q.empty():
		v_from = q.get()
		for v_to in graph[v_from]:
			if not visited[v_to]:
				visited[v_to] = 1
				q.put(v_to)
				shortest_dists[v_to] = shortest_dists[v_from] + 1
				parents[v_to] = v_from
	end = v_dest
	shortes_path = []
	while end is not None:
		shortes_path.append(end + 1)
		end = parents[end]
	return shortes_path[::-1]
n = int(input())
p = [int(e) - 1 for e in input().split()]
graph = [[] for e in range(n)]
for (ix, e) in enumerate(p):
	graph[e].append(ix + 1)
print(' '.join([str(e) for e in bfs(graph, 0, n)]))


n = int(input())
L = [0] + list(map(int, input().split()))
M = [n]
count = n
while count > 1:
	M.append(L[count - 1])
	count = L[count - 1]
print(' '.join((str(i) for i in M[::-1])))


import math as mt
import sys, string
input = sys.stdin.readline
L = lambda : list(map(int, input().split()))
Ls = lambda : list(input().split())
M = lambda : map(int, input().split())
I = lambda : int(input())
from collections import defaultdict

def dfs(n, dx):
	vis[n] = 1
	dis[n] = dx
	for i in adj[n]:
		if vis[i] == 0:
			dfs(i, dx + 1)
n = I()
l = [0] + L()
ans = []
i = n - 1
while l[i] != 0:
	ans.append(i + 1)
	i = l[i] - 1
print(1, *ans[::-1])


import sys
sys.setrecursionlimit(250000)
n = int(input())
A = list(map(int, input().split()))
B = []
i = n
while True:
	B.append(i)
	if i == 1:
		break
	i = A[i - 2]
print(*reversed(B))


n = int(input())
l = list(map(int, input().split()))
k = [n]
i = n - 2
temp = 0
while temp != 1:
	k.append(l[i])
	i = l[i] - 2
	temp = l[i]
print(*sorted(set([1] + k)))


n = int(input())
s = list(map(int, input().split()))
d = dict()
for i in range(n - 1):
	d[i + 2] = s[i]
l = n
k = list()
while l > 1:
	k.append(str(l))
	l = d[l]
k.append('1')
k.reverse()
print(' '.join(k))


n = int(input())
a = [int(x) for x in input().split()]
ans = [n]
i = n - 2
while i >= 0:
	ans.append(a[i])
	i = a[i] - 2
print(*reversed(ans))


n = int(input())
arr = []
arr = list(map(int, input().split()))
arr.insert(1, 1)
arr2 = [n]
while n != 1:
	arr2.append(arr[n - 1])
	n = arr[n - 1]
arr2.sort()
for i in range(len(arr2)):
	print(arr2[i], end=' ')


n = int(input())
arr = input().split()
final = [str(n)]
while final[-1] != '1':
	final.append(arr[int(final[-1]) - 2])
print(' '.join(final[::-1]))


n = int(input())
sequence = [0]
inp = input()
sequence.extend([int(i) for i in inp.split(' ')])
path = []
current_node = 0
while current_node != 1:
	current_node = sequence[current_node - 1]
	path.append(current_node)
for i in path[::-1]:
	print(i, end=' ')
print(n)


n = int(input())
m = list(map(int, input().split()))
pos = n - 2
ans = list()
while pos >= 0:
	ans.append(m[pos])
	pos = m[pos] - 2
print(*reversed(ans), n)


def con(n):
	l = []
	for s in n:
		s = str(s)
		l.append(s)
	return ' '.join(l)
n = int(input())
p = list(map(int, input().split()))
p.insert(0, 0)
p.insert(0, 0)
k = []
while n != 1:
	k.append(n)
	n = p[n]
k.append(1)
k.sort()
print(con(k))


N = int(input())
s = [int(i) for i in input().split()]
Node = N
path = [N]
parent = s[-1]
path.append(parent)
while parent != 1:
	Node = parent
	parent = s[Node - 2]
	path.append(parent)
path = path[::-1]
answer = ''
for i in range(len(path)):
	answer += str(path[i]) + ' '
print(answer[:-1])


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())
input_str = str(input())
input_str = '0 ' + input_str
L = input_str.split()
for i in range(len(L)):
	L[i] = int(L[i])

def find_path(l):
	k = len(l)
	output_list = [k]
	while not k == 1:
		k = l[k - 1]
		output_list.append(k)
	output_str = str(output_list[len(output_list) - 1])
	for i in range(len(output_list) - 2, -1, -1):
		output_str += ' '
		output_str += str(output_list[i])
	return output_str
print(find_path(L))


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())
lis = list(map(int, input().split(' ')))
lis.insert(0, None)
lis.insert(1, None)
l = []
i = n
while lis[i] != None:
	l.append(lis[i])
	i = lis[i]
if l[-1] == None:
	l.pop()
for i in l[::-1]:
	print(i, end=' ')
print(n)


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())
arr = list(map(int, input().split()))
path = []
path.append(n)
path.append(arr[-1])
while True:
	if path[-1] == 1:
		break
	path.append(arr[path[-1] - 2])
print(*path[::-1])


a = input()
b = input()
b = b.split(' ')
fin = [a]
i = len(b) - 1
while i >= 0:
	fin.append(str(b[i]))
	i = int(b[i]) - 2
fin = ' '.join(list(reversed(fin)))
print(fin)


n = int(input())
s = list(input().split())
path = [str(n)]
while path[-1] != '1':
	path.append(s[int(path[-1]) - 2])
path = path[::-1]
print(' '.join(path))


n = int(input())
Tree = [0 for i in range(n + 1)]
Arr = list(map(int, input().split()))
Tree[1] = 1
for i in range(2, n + 1):
	Tree[i] = Arr[i - 2]
Nodes = []
Key = n
while Tree[Key] != Key:
	Nodes.append(Key)
	Key = Tree[Key]
Nodes.append(1)
Nodes.reverse()
for num in Nodes:
	print(num, end=' ')


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)


n = int(input())
rod = {1: 0}
k = 2
res = [str(n)]
for i in map(int, input().split()):
	rod[k] = i
	k += 1
z = rod[n]
if z == 1:
	print(1, n)
else:
	while z != 0:
		res.append(str(z))
		z = rod[z]
	print(' '.join(res[::-1]))


n = int(input())
a = [0] * (n + 1)
i = 2
for s in input().split():
	a[i] = int(s)
	i += 1
ans = [n]
while True:
	n = a[n]
	if n == 0:
		break
	ans.append(n)
print(*ans[::-1])


n = int(input())
L = list(map(int, input().split()))
M = [n]
a = n
while True:
	M.append(L[a - 2])
	if M[-1] == 1:
		break
	a = M[-1]
for i in M[::-1]:
	print(i, end=' ')


n = int(input())
A = list(map(int, input().split()))
A = [0] + [0] + A
ANS = [n]
while n != 0:
	ANS.append(A[n])
	n = A[n]
for i in range(len(ANS) - 1, -1, -1):
	if ANS[i] != 0:
		print(ANS[i], end=' ')


n = int(input())
p = [int(x) for x in input().split(' ')]
r = [n]
while r[-1] != 1:
	r.append(p[r[-1] - 2])
print(*r[::-1])