题目描述

给定一棵树，初始时这棵树只有一个节点 $1$，然后会依次加入节点 $2 \sim n$。

每加入一个节点，都会相应地建一条边，且告诉你这个新加入的节点会和树上已存在的哪个节点建边。

同时，每加入一个节点，你都需要计算并输出此时树的直径。

注：树的直径指树上包含边数最多的简单路径对应的边数。

输入格式

输入共 $n$ 行，每一行包含一个整数。

其中第 $1$ 行包含一个整数 $n(2 \le n \le 200000)$，表示最终树的大小。

第 $i(2 \le i \le n)$ 行包含一个整数 $p_i(1 \le p_i \lt i)$，表示新加入节点 $i$ 时，会将节点 $i$ 和 $p_i$ 之间连一条边。

输出格式

输出共一行，包含 $n-1$ 个整数，两两之间以一个空格分隔，其中第 $i$ 个整数表示加入节点 $i+1$ 后树的直径。

样例

6
1
2
2
1
5

1 2 2 3 4 

说明/提示

数据规模与约定

• 对于 $30\%$ 的数据，$n \le 20$
• 对于 $60\%$ 的数据，$n \le 2000$
• 对于 $100\%$ 的数据，$2 \le n \le 200000, 1 \le p_i \lt i$