#W0007. 徐老师的转换二叉树

徐老师的转换二叉树

Description

徐老师最近学习了二叉树的遍历序列知识,但是毕竟不是所有的树都叫二叉树

这让徐老师非常头疼,于是他自己自创了一种 二叉树转换法

可以把一棵非二叉树用这种方法转换成一棵二叉树!

  1. 徐老师会从根节点 rootroot 出发,用递归的形式遍历每个节点
  2. 当遍历到节点 AA 时,徐老师会列出 AA 的所有兄弟节点 xx,以及 AA 的所有孩子节点 yy
  3. 接着随机选择一个孩子节点 y1y1 成为 AA 的左儿子,再随机选择一个兄弟节点 x1x1 成为 AA 的右孩子
  4. 递归遍历刚才选出的两个节点

但是显然,这种转换方式会构造出非常多不同形态的二叉树

为了不浪费空间,徐老师希望转换出来的二叉树深度尽可能小

他想知道在给定一棵树的情况下,构造出的树深度最小是多少?

Format

Input

输入第一行一个整数 nn 表示这棵树的节点数量

接下来一行包含 n1n - 1 个数字,分别表示 2n2 \sim n 每个节点的父亲节点编号

题目保证第 ii 个节点的父亲编号均小于 ii.

Output

输出一个整数,表示这棵树用 二叉树转换法 转换成二叉树后最小的深度

Samples

10
1 1 1 2 3 4 4 5 7
5

样例解释

1122 作为左儿子,11 没有兄弟,所以没有右儿子 2255 作为左儿子,选 44 作为右儿子 5599 作为左儿子,55 没有兄弟,所以没有右儿子 4477 作为左儿子,选 33 作为右儿子 771010 作为左儿子,选 88 作为右儿子 3366 作为左儿子,此时 33 已经没有兄弟节点了,所以没有右儿子

Limitation

对于 20%20\% 的测试数据满足:n10n \leq 10

对于 50%50\% 的测试数据满足:n500n \leq 500

对于 100%100\% 的测试数据满足:n100000n \leq 100000