407801: GYM102896 C Color the Tree

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

C. Color the Treetime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

Christina has a rooted tree with $$$n$$$ vertices. Initially, all vertices are colored green, except for the root, which is colored red. Christina thinks that the tree is beautiful if two rules are satisfied:

  • The root is colored red.
  • If the vertex is colored red, all vertices on the shortest path between it and the root are also red.

Christina repeatedly performs the following operation on the tree — chooses a vertex and changes its color (if it was red, colors it green; if it was green, colors it red). The following rules must be satisfied while performing the operations:

  • The tree should stay beautiful.
  • The coloring of vertices should be unique. That means there is no moment in the past when each vertex had the same color as it has right now.

Your task is to help Christina build the longest possible sequence of operations following the rules.

Input

The first line contains an integer $$$n$$$ ($$$1 \le n \le 20$$$) — the number of vertices in the tree.

The second line contains $$$n - 1$$$ integers $$$p_i$$$ ($$$1 \le p_i \le i$$$ for $$$1 \le i \le n - 1$$$), denoting parent vertices in the tree. The vertices in the tree are numbered from $$$1$$$ to $$$n$$$, the root has number $$$1$$$, the $$$i$$$-th vertex has parent $$$p_{i-1}$$$ for $$$2 \le i \le n$$$.

Output

On the first line output an integer $$$m$$$ — the maximum number of operations.

On the second line output $$$m$$$ integers $$$o_i$$$ ($$$2 \le o_i \le n)$$$. $$$o_i$$$ is the number of the vertex that changes color during the corresponding operation.

If there are several possible longest sequences, output any one of them.

ExamplesInput
4
1 1 1
Output
7
4 3 4 2 4 3 4 
Input
4
1 2 3
Output
3
2 3 4 
Input
6
1 1 2 2 2
Output
17
3 2 3 6 3 5 3 6 3 4 3 6 3 5 3 6 3 
Input
5
1 2 1 1
Output
11
5 4 5 2 5 4 5 3 5 4 5 
Input
5
1 1 2 3
Output
8
3 5 2 5 3 4 3 5 

加入题单

上一题 下一题 算法标签: