P6890 [CEOI 2006] Link

网站管理员 Kirk 正在重新组织他学校的网站。网站上有许多页面，内容很好，但他注意到页面之间的链接不够合理。事实上，每个页面都只包含一个链接，指向网站中的其他页面。这是一个糟糕的设计——从主页开始，访问者通常需要点击许多链接才能到达他感兴趣的页面，而且有些页面可能根本无法从主页访问。作为第一步，他想添加一些链接，以便每个页面都可以从主页快速访问。新链接可以添加在网站的任何地方。 网站包含 $N$ 个页面，用整数 1 到 $N$ 标记，主页标记为数字 1。 每个页面也有 $N$ 个链接；**每个页面都包含一个指向其他页面的链接**。对于整数 $K$，如果网站上的每个页面（除了主页）都可以通过**最多 $K$ 个链接**从主页访问，则称该网站是 **K-可达的**。 编写一个程序，给定网站的描述和整数 $K$，找出为了使网站 K-可达所需添加的**最少链接数**。

第一行是两个整数用空格隔开 $N$ 和 $K$。 接下来 $N$ 行： 其中第 $i+1$ 行 $(1\leqslant i\leqslant N)$ 输入两个整数 $x$ 和 $y$，表示存在一条从 $x$ 到 $y$ 的单向边。

输出仅一个整数：表示最少需要添加的边数。

在第二组样例中，一个合法的路径集合 $\{1\to 7,1\to 14,14\to 10\}$。 $2 \leq N \leq 500 000$, $1 \leq K \leq 20 000$。 题面翻译由 ChatGPT-4o 提供。