题目内容

在一片数据中心里，有 $n$ 台服务器，通过 $n-1$ 条光缆连接成一棵树。一次紧急维护中，工程师可以选择两台服务器，并断开它们直连的所有光缆。网络会因此分裂成若干个连通块，其中包含服务器数量最多的连通块的大小称为碎片度。工程师希望碎片度尽可能小。

约束：服务器数量 $n$ 满足 $2 \le n \le 2 \times 10^3$，所有编号均为从 $1$ 到 $n$ 的整数。

输入描述

第一行包含一个正整数 $n$。 第二行包含 $n-1$ 个整数 $p_1, p_2, \dots, p_{n-1}$，其中 $p_i$ 表示服务器 $i+1$ 与服务器 $p_i$ 之间有一条光缆。

输出描述

输出一个整数，表示可能的最小碎片度。

样例1

输入

2
1

输出

1

说明

当 $n=2$ 时，只有两台服务器，编号分别为 1 和 2。 工程师必须同时选择这两台服务器，并断开它们之间唯一的光缆。 操作后，两台服务器各自成为独立的连通块，大小均为 1。 因此，最小可能的碎片度为 1。

样例2

输入

5
1 2 2 2

输出

1

说明

树的结构为：服务器 1 连接 2，服务器 2 连接 3、4、5，即以服务器 2 为中心的星型拓扑。 选择服务器 2 和 1 并断开它们直连的所有光缆：

• 服务器 2 与 1、3、4、5 之间的光缆全部断开；
• 服务器 1 仅与 2 断开。 剩余的服务器 3、4、5 以及被选中的 1、2 均各自孤立，每个连通块大小均为 1，最大连通块大小为 1。 故最小碎片度为 1。

样例3

输入

6
1 2 3 4 5

输出

2

说明

服务器形成一条链 $1-2-3-4-5-6$。 考虑选择服务器 3 和 4：断开它们的光缆后，剩余连通块为 $\{1,2\}$ 和 $\{5,6\}$，大小均为 2；被选中的服务器自身形成大小为 1 的连通块。此时碎片度为 2。 若选择其他组合，碎片度均不小于 2（例如选择 2 和 5，剩余 $\{1\}$、$\{3,4\}$、$\{6\}$，最大连通块仍为 2）。 因此最小可能碎片度为 2。

样例4

输入

7
1 2 3 4 5 6

输出

2

说明

服务器形成一条链 $1-2-3-4-5-6-7$。 选择服务器 2 和 5 并断开相关光缆后，网络分裂为三个片段：$\{1\}$（大小 1）、$\{3,4\}$（大小 2）、$\{6,7\}$（大小 2），被选中的 2 和 5 各自大小为 1。最大连通块大小为 2。 可以证明，无论怎样选择两台服务器，总会留下一个大小至少为 2 的连通块，无法将碎片度降至 1，因此答案为 2。