A monochrome tree is a tree in which each vertex is colored either white or black. The score of a monochrome tree is equal to the number of unordered vertex pairs ($u$, $v$) such that:
- Both vertices
$u$and$v$are colored black. - Either
$u$is an ancestor of$v$or$v$is an ancestor of$u$.
You are given a rooted tree of $n$ vertices whose root vertex is $1$.
For each $k$ from $0$ to $n$ (inclusive), you may color the given tree in such a way that there are exactly $k$ black vertices and $n - k$ white vertices. Among all the possible colorings, we denote the lowest score of a coloring as $c_k$.
Find $c_k$ for all $0 \leq k \leq n$.
Input
The first line contains a single integer $n$, the number of vertices in the given tree ($1 \leq n \leq 2 \cdot 10^5$).
The next $n - 1$ lines contain integers $p_2, p_3, \ldots, p_n$, one per line, meaning that the parent of the vertex $i$ is $p_i$ ($1 \leq p_i \leq n$, $p_{i} \neq i$). The resulting graph is a tree rooted at vertex $1$.
Output
On the first and only line, print $n + 1$ integers: $c_0, c_1, c_2, \ldots, c_n$.
Examples
Input 1
3 1 1
Output 1
0 0 0 2
Input 2
3 3 1
Output 2
0 0 1 3
Note
Vertex $x$ is an ancestor of vertex $y$ if $x \neq y$ and there is a sequence of vertices $\{x = a_1, a_2, \ldots a_k = y\}$ where $a_i$ is the parent of $a_{i + 1}$ ($1 \leq i \leq k - 1$).