← 返回题目列表

Codeforces · 1057/A

A. Bmail计算机网络

中文机器翻译题面 查看原题

曾几何时,知名公司 Bmail 中只有一台路由器。几年过去了,随着时间的推移,人们购买了新的路由器。每次他们购买新路由器时,都会将其连接到之前购买的路由器之一。您将获得值 $$$p_i$$$ — 第 $$$i$$$ 路由器在购买后连接到的路由器的索引 ($$$p_i < i$$$)。

Boogle 中现在总共有 $$$n$$$ 个路由器。打印从第一个到第 $$$n$$$ 个路由器的路径上的路由器序列。

输入

第一行包含整数 $$$n$$$ ($$$2 \le n \le 200000$$$) — 路由器的数量。以下行包含 $$$n-1$$$ 整数 $$$p_2, p_3, \dots, p_n$$$ ($$$1 \le p_i < i$$$),其中 $$$p_i$$$ 等于购买后第 $$$i$$$ 连接到的路由器的索引。

输出

打印从 $$$1$$$-st 到第 $$$n$$$-th 路由器的路径。它以 $$$1$$$ 开头,以 $$$n$$$ 结尾。路径中的所有元素都应该是不同的。

示例

输入 #1

8
1 1 2 2 3 2 5

输出 #1

1 2 5 8

输入 #2

6
1 2 3 4 5

输出 #2

1 2 3 4 5 6

输入 #3

7
1 1 2 3 4 3

输出 #3

1 3 7