15138번 - Hidden Supervisors 스페셜 저지다국어

Helena works in a big company as a psychologist. Her task is to organize a team building game to enhance social relations between employees. Each employee except the Big boss has a single supervisor. So, employees of the company form a tree where each employee is a node, and the parent of that node is their supervisor. The root of the tree is the Big boss.

A team building game requires teams of two people. Every team should consist of an employee and their supervisor.

Helena asked every employee except the Big boss to send their supervisor ID. Some of them didn’t reply. She is going to assign a fake supervisor to every employee that didn’t reply, so that she could arrange as many teams as possible. And, of course, fake and real supervisors must form a tree.

Helena had a difficult, but a successful day organizing the event. Will you be able to assign fake supervisors?

The first line of the input contains a single integer n — the number of employees in the company (2 ≤ n ≤ 100 000).

The following line contains n − 1 integers p₂, p₃, . . . , p_n, where p_i is the supervisor of employee i (0 ≤ p_i ≤ n). If employee i didn’t reply to Helena, p_i equals zero, and she needs to assign a fake supervisor to that employee. The Big boss has the number 1.

It’s possible to assign a fake supervisor to each employee that didn’t reply to Helena so that all employees will form a tree having the Big boss as a root.

In the first line output a single integer m — the maximum possible number of arranged teams.

The next line should contain supervisors: n−1 integers, i-th of which denoting the supervisor of employee i + 1 (either fake or real). Of course, all real supervisors should be preserved, and employees must form a tree. It should be possible to arrange m teams using specified supervisors.