After a long day of being a goat farmer, Tudor finally returns to an old hobby of his - baking cheese.
Tudor's recipe requires ~N~ operations to be performed. The operations happen to form a directed tree, where operation ~a_i~ may depend on some other operations to be performed first. Operation 1 is guaranteed to be the last operation to perform and there will be no cyclic dependencies.
Each operation will generate some intermediate result in the process of baking cheese that needs to be stored in a bowl. When an operation that depends on others to be done first is to be performed, Tudor will take all of the bowls with those intermediate results, grab a new bowl, and mix the intermediate results in the new bowl. After that, the other bowls may be cleaned and reused in later operations.
Compute the minimum number of bowls Tudor needs to bake cheese.
~2 \le N \le 10^6~
~a_i < i~
The first line contains a single positive integer, ~N~.
Each of the next ~N-1~ lines contain the integers ~a_2~ through ~a_N~ in order, one per line. Operation ~a_i~ depends directly on operation ~i~ to be completed first.
Output the minimum number of bowls that Tudor needs.
5 1 1 2 2
Below, we provide a diagram showing the dependencies on operations explicitly.
We can show that 2 bowls are not sufficient to perform all the operations. If we have bowls A, B, and C, then the following steps show that 3 bowls are sufficient to perform all the operations.
- Perform operation 5 and store the result in bowl A.
- Perform operation 4 and store the result in bowl B.
- Perform operation 2, using bowls A and B, and store the result in bowl C.
- Clean bowls A and B.
- Perform operation 3 and store the result in bowl B.
- Perform operation 1, using bowls B and C, and store the result in bowl A.