CF442D.Adam and Tree

When Adam gets a rooted tree (connected non-directed graph without cycles), he immediately starts coloring it. More formally, he assigns a color to each edge of the tree so that it meets the following two conditions:

• There is no vertex that has more than two incident edges painted the same color.
• For any two vertexes that have incident edges painted the same color (say, c), the path between them consists of the edges of the color c.

Not all tree paintings are equally good for Adam. Let's consider the path from some vertex to the root. Let's call the number of distinct colors on this path the cost of the vertex. The cost of the tree's coloring will be the maximum cost among all the vertexes. Help Adam determine the minimum possible cost of painting the tree.

Initially, Adam's tree consists of a single vertex that has number one and is the root. In one move Adam adds a new vertex to the already existing one, the new vertex gets the number equal to the minimum positive available integer. After each operation you need to calculate the minimum cost of coloring the resulting tree.

当亚当得到一棵有根树（即无环的连通无向图）时，他会立即开始对这棵树进行边染色。更准确地说，他为树的每条边分配一种颜色，使得满足以下两个条件：

• 不存在某个顶点，其关联的边中有多于两条被染成同一种颜色；
• 对任意两个存在同色（设为 $c$）关联边的顶点，它们之间的路径上所有边的颜色均为 $c$。

并非所有树的染色方案对亚当而言都同样好。考虑从某个顶点到根节点的路径，我们将该路径上不同颜色的数目称为该顶点的代价。整棵树染色方案的代价定义为所有顶点代价的最大值。请帮助亚当确定该树染色的最小可能代价。

初始时，亚当的树仅包含一个编号为 $1$ 的顶点，该顶点即为根节点。在每一次操作中，亚当将一个新顶点添加到当前已存在的某一个顶点上；新顶点的编号取为当前未使用的最小正整数。每次操作后，你都需要计算所得树的染色方案的最小代价。

The first line contains integer n (1 ≤ n ≤ 106) — the number of times a new vertex is added. The second line contains n numbers p__i (1 ≤ p__i ≤ i) — the numbers of the vertexes to which we add another vertex.

第一行包含一个整数 $n$（$1 \leq n \leq 10^6$）—— 表示新增顶点的次数。
第二行包含 $n$ 个数 $p_i$（$1 \leq p_i \leq i$）—— 表示每次新增顶点所连接的已有顶点的编号。

Print n integers — the minimum costs of the tree painting after each addition.

输出 n 个整数——每次添加后树染色的最小代价。

The figure below shows one of the possible variants to paint a tree from the sample at the last moment. The cost of the vertexes with numbers 11 and 12 equals 3.

下图展示了样例中树在最后一刻的一种可能的染色方案。编号为 11 和 12 的顶点的代价均为 3。