Tree

Problem Description

There is a rooted tree with $n$ nodes, rooted at node $1$. You may perform several operations on this tree; in each operation you may choose a node and delete all edges connecting this node to its sons.

For every $k$ ($1 \le k \le n$), you want to know the minimum number of operations required so that the graph has exactly $k$ connected components.

Input Format

The first line contains a positive integer $n$.

The second line contains $n-1$ integers $f_1, f_2, \dots, f_{n-1}$, where $f_i$ is the father of node $i+1$. It is guaranteed that $1 \le f_i \le i$.

Output Format

Output $n$ integers. The $i$-th integer is the answer when $k = i$; if it is impossible to make the graph have exactly $i$ connected components, output -1.

Sample Input

6
1 2 1 1 2

Sample Output

0 -1 1 1 -1 2

Constraints

There are $10$ test cases in total.

Test cases $1, 2, 3$ satisfy $n \le 20$.

Test cases $4, 5, 6$ satisfy $n \le 100$.

For all data, $1 \le n \le 3000$.

Hint

See the distributed files.