Description

网站管理员 Kirk 正在重新组织他学校的网站。网站上有许多页面，内容很好，但他注意到页面之间的链接不够合理。事实上，每个页面都只包含一个链接，指向网站中的其他页面。这是一个糟糕的设计——从主页开始，访问者通常需要点击许多链接才能到达他感兴趣的页面，而且有些页面可能根本无法从主页访问。作为第一步，他想添加一些链接，以便每个页面都可以从主页快速访问。新链接可以添加在网站的任何地方。

网站包含 $N$ 个页面，用整数 1 到 $N$ 标记，主页标记为数字 1。

每个页面也有 $N$ 个链接；每个页面都包含一个指向其他页面的链接。对于整数 $K$，如果网站上的每个页面（除了主页）都可以通过最多 $K$ 个链接从主页访问，则称该网站是 K-可达的。

编写一个程序，给定网站的描述和整数 $K$，找出为了使网站 K-可达所需添加的最少链接数。

Input Format

第一行是两个整数用空格隔开 $N$ 和 $K$。

接下来 $N$ 行：

其中第 $i+1$ 行 $(1\leqslant i\leqslant N)$ 输入两个整数 $x$ 和 $y$，表示存在一条从 $x$ 到 $y$ 的单向边。

Output Format

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

8 3
1 2
2 3
3 5
4 5
5 6
6 7
7 8
8 5

2

14 4
1 2
2 3
3 4
4 5
7 5
5 6
6 3
8 10
10 9
9 8
14 13
13 12
12 11
11 14

3

Hint

在第二组样例中，一个合法的路径集合 $\{1\to 7,1\to 14,14\to 10\}$。

$2 \leq N \leq 500 000$, $1 \leq K \leq 20 000$。

题面翻译由 ChatGPT-4o 提供。