아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Color the Tree

시간 제한2초메모리 제한512 MB

요약
정점이 20개 이하인 루트 트리에서, 트리가 아름다운 상태를 유지하면서 이전에 나온 적 없는 색 배치만 등장하도록 색을 바꾸는 최장 수열을 구합니다.
난이도

보통10점 중 7점

유형
트리, DFS, 조합론, 백트래킹
정답자
아직 제출이 없습니다

문제

Christina has a rooted tree with nn 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.

입력

The first line contains an integer nn (1≤n≤201 \le n \le 20) --- the number of vertices in the tree.

The second line contains n−1n - 1 integers p_ip\_i (1≤p_i≤i1 \le p\_i \le i for 1≤i≤n−11 \le i \le n - 1), denoting parent vertices in the tree. The vertices in the tree are numbered from 11 to nn, the root has number 11, the ii-th vertex has parent p_i−1p\_{i-1} for 2≤i≤n2 \le i \le n.

출력

On the first line output an integer mm --- the maximum number of operations. 

On the second line output mm integers o_io\_i (2≤o_i≤n)2 \le o\_i \le n). o_io\_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.

예제5

  1. 예제 1

    입력
    4
    1 1 1
    
    예상 출력
    7
    4 3 4 2 4 3 4
    
  2. 예제 2

    입력
    4
    1 2 3
    
    예상 출력
    3
    2 3 4
    
  3. 예제 3

    입력
    6
    1 1 2 2 2
    
    예상 출력
    17
    3 2 3 6 3 5 3 6 3 4 3 6 3 5 3 6 3
    
  4. 예제 4

    입력
    5
    1 2 1 1
    
    예상 출력
    11
    5 4 5 2 5 4 5 3 5 4 5
    
  5. 예제 5

    입력
    5
    1 1 2 3
    
    예상 출력
    8
    3 5 2 5 3 4 3 5