一个单色树是指每个顶点都被染成白色或黑色的树。一个单色树的得分等于满足以下条件的无序顶点对 ($u$, $v$) 的数量：

1. 顶点 $u$ 和 $v$ 都被染成黑色。
2. $u$ 是 $v$ 的祖先，或者 $v$ 是 $u$ 的祖先。

给你一棵含有 $n$ 个顶点的有根树，其根节点为 $1$。

对于每个从 $0$ 到 $n$（包含）的 $k$，你可以对给定的树进行染色，使得恰好有 $k$ 个黑色顶点和 $n - k$ 个白色顶点。在所有可能的染色方案中，我们将染色的最小得分记为 $c_k$。

求对于所有 $0 \leq k \leq n$ 的 $c_k$。

输入格式

第一行包含一个整数 $n$，表示给定树中的顶点数（$1 \leq n \leq 2 \cdot 10^5$）。

接下来的 $n - 1$ 行，每行包含一个整数，依次为 $p_2, p_3, \ldots, p_n$，表示顶点 $i$ 的父节点是 $p_i$（$1 \leq p_i \leq n$，$p_{i} \neq i$）。保证生成的图是一棵以顶点 $1$ 为根的树。

输出格式

在第一行也是唯一一行中，输出 $n + 1$ 个整数：$c_0, c_1, c_2, \ldots, c_n$。

样例

输入 1

3
1
1

输出 1

0 0 0 2

输入 2

3
3
1

输出 2

0 0 1 3

说明

如果 $x \neq y$ 且存在一个顶点序列 $\{x = a_1, a_2, \ldots a_k = y\}$，其中 $a_i$ 是 $a_{i + 1}$ 的父节点（$1 \leq i \leq k - 1$），则称顶点 $x$ 是顶点 $y$ 的祖先。