网站管理员 Kirk 正在重构他学校的网站。网站上有许多页面，内容都很不错，但他发现页面之间的链接并不合理。事实上，每个页面都恰好包含一条链接，指向网站中的另一个页面。这是一个糟糕的设计——从主页开始，访问者通常需要经过许多条链接才能到达他们感兴趣的页面，而且有些页面甚至根本无法从主页到达。作为第一步，他希望添加一些链接，以便可以从主页快速访问每个页面。新的链接可以添加到网站的任何地方。

该网站包含 $N$ 个页面，用整数 $1$ 到 $N$ 标记，其中主页标记为 $1$。网站中共有 $N$ 条链接；每个页面都恰好包含一条指向另一个不同页面的链接。对于一个整数 $K$，如果除了主页之外的每个页面都可以通过从主页出发、沿着最多 $K$ 条链接到达，则称该网站是 $K$-可达 的。

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

输入格式

第一行包含两个整数 $N$ 和 $K$（$2 \le N \le 500\,000$，$1 \le K \le 20\,000$），分别表示页面的数量和目标最大链接数。

接下来的 $N$ 行，每行包含两个不同的整数 $A$ 和 $B$（$1 \le A, B \le N$），表示页面 $A$ 上的链接指向页面 $B$。

输出格式

输出第一行且仅包含一个整数，表示使网站达到 $K$-可达所需添加的最少额外链接数。

样例

输入样例 1

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

输出样例 1

2

输入样例 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

输出样例 2

3

说明

在第二个样例中，一种可能的方案是添加链接 $1 \to 7$、$1 \to 14$ 和 $14 \to 10$。