树

题目描述

有一棵 $n$ 个节点的以 $1$ 号点为根的有根树。现在可以对这棵树进行若干次操作，每一次操作可以选择树上的一个点然后删掉连接这个点和它的儿子的所有边。

现在我们想知道对于每一个 $k$ $(1 \le k \le n)$，最少需要多少次操作能让图中恰好存在 $k$ 个联通块。

输入格式

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

第二行输入 $n-1$ 个整数 $f_1, f_2, ..., f_{n-1}$，$f_i$ 表示 $i+1$ 号点的父亲，保证 $1 \leq f_i \leq i$。

输出格式

输出 $n$ 个整数，第 $i$ 个数表示 $k=i$ 时的答案，如果无法让图中恰好存在 $i$ 个联通块，则输出 -1。

样例输入

6
1 2 1 1 2

样例输出

0 -1 1 1 -1 2

数据范围

共 $10$ 个测试点。

测试点 $1, 2, 3$ 满足 $n\leq 20$。

测试点 $4, 5, 6$ 满足 $n\leq 100$。

对于所有数据，满足 $1\leq n\leq 3000$。

提示

见下发文件。