Family Tree

Time limit2sMemory limit64 MB

Summary

Given a tree where each node lists its single child (parent-of relation), compute the minimum number of extra ancestor nodes to insert so no node has more than d parents.

Level: Medium5 of 10
Topics: Tree, Greedy, Implementation
Solved: No attempts yet

Problem

The alien Peter wants to organize his family tree. After weeks of hard work he finished a draft (beta version) of it.

Looking the draft over, he noticed that some ancestors had far too many parents. (An alien may have at most d parents.) Peter therefore suspected that some parent-child links are really more distant ancestor-descendant relationships.

Write a program that computes the minimum number of ancestors Peter must insert to turn the family tree into a satisfactory form.

A family tree is in satisfactory form when every alien has at most d parents and each alien appears in the tree exactly once.

For example, if d = 2 and Peter's draft looks like this,

then adding the two ancestors shown below makes it satisfactory.

Input

The first line contains two integers n and d (2 ≤ n ≤ 100,000, 2 ≤ d ≤ n).

The second line contains n integers separated by spaces. The i-th integer is the number of the alien that alien i designates as its child; that is, alien i is a parent of that alien.

The ancestors appearing in Peter's family tree are numbered from 1 to n, and Peter himself is numbered 0.

Output

Print the minimum number of ancestors that must be added to make the family tree satisfactory.

Examples6

Example 1
Input
```
6 2
5 5 0 5 0 5
```
Expected output
```
2
```
Example 2
Input
```
2 2
2 0
```
Expected output
```
0
```
Example 3
Input
```
5 2
0 0 0 0 0
```
Expected output
```
3
```
Example 4
Input
```
7 3
0 0 0 0 0 0 0
```
Expected output
```
2
```
Example 5
Input
```
8 2
5 5 5 5 8 8 8 0
```
Expected output
```
3
```
Example 6
Input
```
10 4
0 0 0 0 0 0 0 0 0 0
```
Expected output
```
2
```