题目描述

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 \le n \le 100 000)$ .

The following line contains $n − 1$ integers $p_{2}, p_{3},$ . . . , $p_{n},$ where $p_{i}$ is the supervisor of employee $i (0 \le p_{i} \le 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.

题目大意

题目简述

有一棵大小为 $n$ 的有根树，根为 $1$，其中若干结点的父亲没有确定。试求出所有可能构成的以 $1$ 为根的有根树中，最大匹配的最大值是多少，并输出构造方案。保证数据有解。

输入格式

第一行输入一个整数 $n$。

第二行输入 $n-1$ 个整数 $p_2,p_3,\cdots,p_n$，分别表示 $2,3,\cdots,n$ 的父亲。其中 $p_i = 0$ 表示点 $i$ 的父亲未确定，$p_i \neq 0$ 表示点 $i$ 的父亲已确定。

输出格式

第一行输出一个整数表示最大匹配的最大值。

第二行输出 $n-1$ 个整数 $p'_2,p'_3,\cdots,p'_n$，分别表示 $2,3,\cdots,n$ 的父亲。

6
3 1 0 4 4

2
3 1 2 4 4

6
3 1 0 6 4

3
3 1 1 6 4

提示

Time limit: 3 s, Memory limit: 512 MB.