Fake Supervisors

Helena works as a psychologist in a big company whose employees (except for the Big boss) each have exactly one supervisor. Thus the employee‐supervisor relations form a rooted tree (with the Big boss as the root). For a team building game, teams of two must be formed, and every team must consist of an employee and their supervisor.

Helena collected supervisor IDs from every employee except the Big boss. Unfortunately, some employees did not reply. In order to create as many teams as possible, she will assign a fake supervisor for each employee that did not reply. The final supervisor assignment – including both the real and fake assignments – must form a valid tree (i.e. every employee except the Big boss has exactly one supervisor, and the Big boss has no supervisor).

Your task is to help Helena: Given the partial tree information, assign a fake supervisor to each employee who did not reply so that the maximum number of teams (i.e. the maximum matching in the tree) is achieved. A valid team is a pair consisting of some employee and their own supervisor and no person can participate in more than one team. It can be shown that the maximum number of teams that can be formed is at most \(\lfloor \frac{n}{2} \rfloor\), where \(n\) is the total number of employees.

Input details: The first line contains a single integer \(n\) representing the number of employees. The employees are numbered from 1 to \(n\), where employee 1 is the Big boss. The second line contains \(n-1\) space-separated integers, where the \(i\)th integer (for \(i=2,3,\ldots,n\)) is the supervisor ID reported by employee \(i\). If an employee did not reply, the corresponding integer will be 0, and you need to assign a fake supervisor for that employee. Note that if an employee’s supervisor was reported (i.e. nonzero), you must keep that assignment. For any fake assignment you make, you must assign a supervisor with an index strictly less than the employee’s index (so that no cycle is created and the tree remains rooted at 1).

inputFormat

The first line contains an integer \(n\) (\(2 \le n \le 10^5\)). The second line contains \(n-1\) space-separated integers \(p_2, p_3, \ldots, p_n\). For each \(i\) (\(2 \le i \le n\)), if \(p_i=0\) then employee \(i\) did not reply and you must assign a fake supervisor; otherwise, \(p_i\) (with \(1 \le p_i .

outputFormat

Output two lines. The first line should contain a single integer: the maximum number of teams (i.e. the size of the maximum matching in the final tree). The second line should contain \(n-1\) space‐separated integers. For each employee \(i\) (with \(2 \le i \le n\)), if the input supervisor ID is nonzero, output that value; if it was 0, output your assigned fake supervisor (which must be a number in the range \([1, i-1]\)). The assignment must yield a tree that maximizes the number of teams.

sample

4
0 1 0

2
1 1 3