Problem I: Christmas tree Problem I: Christmas tree
Time Limit: 1 Sec Memory Limit: 256 MB Special Judge
Submit: 379 Solved: 71
[Submit][Status][Web Board]Description
To celebrate the 10th anniversary of SUSTech and Christmas, \(Alice\) want to construct a rooted christmas tree \(T\), which root is node \(1\). The tree has \(n\) nodes and the brightness of node \(i\) is \(a_i\). We define \(d_i\) is the depth of node \(i\). Particularly, \(d_1=0\). The darkness of a christmas tree is the number of nodes which brightness value not equal to it's depth. Now \(Alice\) has \(n\) nodes and she want to construct the tree and minimize the darkness of the christmas tree.
Note that \(f(T)=\sum_{i=1}^n[a_i \neq d_i]\)
\(Alice\) wants to minimize \(f(T)\). Can you help her?
Your task is to find the answer and construct the tree \(T\).
Input
The first line contains an integer \(N(2 \leq N \leq 2 \times 10^5)\) indicating the total number of nodes.
The next line contains \(N\) integers \(a_1, a_2, \ldots , a_N(0 \leq a_i < N)\), indicating the brightness value of each node.
Output
You should print two lines.
In first line, print out one integer representing the minimum \(f(T)\).
In second line, print out \(N-1\) integers \(f_2 , \ldots, f_N\). Among them, \(f_i\) represents the parent node of \(i\).
Sample Input
5
1 0 0 4 3
Sample Output
3
3 1 5 2
HINT
[Submit][Status]