K-Reachable Website

Webmaster Kirk is reorganizing his school's website. The website consists of N pages numbered from 1 to N, where page 1 is the homepage. Each page has exactly one outgoing link to some other page (the link always points to a different page). Due to this design, starting from the homepage a visitor may have to follow many links before reaching his desired page – and some pages might not even be reachable from the homepage.

To improve navigation, Kirk wants to add a minimum number of additional links anywhere on the website so that every page (other than the homepage) becomes K-reachable – meaning that it can be reached from the homepage by following at most K links. When a new link is added, it is assumed to work immediately as a shortcut and resets the link‐count from that point.

For example, suppose a page would originally be reached in 5 steps. If K = 3, we might add a new link in the chain so that from the homepage the page is reached in (say) 1 (for the new link) + 2 (following original links) = 3 steps.

More formally, given the original website structure and an integer K, you are to compute the minimum number of additional links that must be added so that every page (except page 1) is reachable from page 1 by following at most K links.

Note: The website has exactly N links originally – one per page – and each link goes from a page to a different page. New links can be inserted arbitrarily.

The relationship between a page’s original distance and the effect of a new link is as follows: When a new link is added from some already reached page to another page, the target page is considered to be reached in 1 link from that source – effectively “resetting” the counter of original links that need to be followed. Use this idea to plan the minimum additions needed along the longest chains (or cycles) of pages.

Your task is to write a program that finds this minimum number.

inputFormat

The first line contains two integers, N and K, where 2 ≤ N ≤ 10⁵ and 1 ≤ K ≤ N.

The second line contains N integers. The i-th integer (for 1 ≤ i ≤ N) indicates the page that the link on page i points to. It is guaranteed that for each i the link goes to a page different from i.

outputFormat

Output a single integer – the minimum number of additional links that need to be added so that every page except the homepage (page 1) is K-reachable.

sample

5 2
2 3 4 5 3

2