P6890 [CEOI 2006] Link

Webmaster Kirk is reorganizing his school's website. There are a number of pages on the website and the content is fine, but he noticed that the pages are not properly linked. In fact, every page contains exactly one link, pointing to some other page in the website. This is a poor design – starting from the homepage, a visitor will usually have to follow many links before reaching the page of his interest, and some pages might not be reachable from the homepage at all. As a first step, he wants to add a few links so that every page can be quickly accessed from the homepage. New links can be added anywhere in the website. The website contains N pages marked with integers 1 to N and the homepage is marked with the number 1. There are also N links; **each page contains exactly one link** pointing to some **different** page. For an integer K, a website is said to be **K-reachable** if every page on the website other than the homepage can be reached from the homepage by following **at most K** links. Write a program that, given the description of the website and an integer K, finds the **minimum number of links that need to be added** in order to make the website K-reachable.

无

无

在第二组样例中，一个合法的路径集合 $\{1\to 7,1\to 14,14\to 10\}$。 $2 ≤ N ≤ 500 000$, $1 ≤ K ≤ 20 000$。