Bytelandian Tree Factory 生产用于各种工业应用的树木。您的任务是优化特定类型树木的生产,以满足特别大且重要的订单。
所讨论的树是一棵有根树,其 $$$n$$$ 顶点标记有从 $$$0$$$ 到 $$$n - 1$$$ 的不同整数。标记为 $$$0$$$ 的顶点是树的根,对于任何非根顶点 $$$v$$$,其父顶点 $$$p(v)$$$ 的标签小于 $$$v$$$ 的标签。
工厂里的所有树木都是由竹坯制成的。竹子是一棵有根树,除了没有子节点的单个叶顶点外,每个顶点都只有一个子节点。在开始加工之前,可以对竹毛坯的顶点进行任意标记。
要将竹子处理成另一棵树,可以进行单一类型的操作:选择任意非根顶点 $$$v$$$ ,使其父节点 $$$p(v)$$$ 也不是根。该操作包括将 $$$v$$$ 的父级更改为其父级的父级 $$$p(p(v))$$$。请注意,所有其他顶点的父节点保持不变,特别是 $$$v$$$ 的子树不会改变。
效率至关重要,因此您必须最大限度地减少操作次数,才能从竹毛坯中制作出所需的树。构造任何最佳操作序列以生成所需的树。
请注意,生成的树的标签必须与所需树的标签一致。形式上,根的标签必须相等,并且对于具有相同标签的非根顶点,其父节点的标签应该相同。
保证对于此问题中存在的任何测试都存在答案,并且进一步,最佳序列最多包含 $$$10^6$$$ 操作。请注意,任何不满足这些条件的 hack 都将无效。
输入
第一行包含一个整数 $$$n$$$ — 树中的顶点数 ($$$2 \leq n \leq 10^5$$$)。
第二行包含 $$$n - 1$$$ 整数 $$$p(1), \ldots, p(n - 1)$$$ - 分别为 $$$1, \ldots, n - 1$$$ 的父顶点索引 ($$$0 \leq p(i) < i$$$)。
输出
在第一行中,打印 $$$n$$$ 不同的整数 $$$id_1, \ldots, id_n$$$ - 从根顶点开始的竹毛坯的初始标签 ($$$0 \leq id_i < n$$$)。
在第二行中,打印单个整数 $$$k$$$ — 序列中的操作数 ($$$0 \leq k \leq 10^6$$$)。
在第三行打印 $$$k$$$ 整数 $$$v_1, \ldots, v_k$$$ 按顺序描述操作。第 $$$i$$$ 操作包括将 $$$p(v_i)$$$ 更改为 $$$p(p(v_i))$$$。每个操作都应该是有效的,即 $$$v_i$$$ 和 $$$p(v_i)$$$ 都不能是此时树的根。
示例
输入 #1
5 0 0 1 1
输出 #1
0 2 1 4 3 2 1 3
输入 #2
4 0 1 2
输出 #2
0 1 2 3 0