You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

现在我们将在树上进行一个游戏，首先将给出一棵含有 $n$ 个点，$n-1$ 条边的树和一个整数 $k$ ｡ 在每回合时，当前剩余的度数为 $k$ 的点及与其连接的边会瞬间同时被删去｡

形式化的，每回合都将按顺序进行如下操作： 统计当前剩余每个点的度数（一个点的度数定义为，这个点当前连接的边的条数）｡ 将所有度数恰好为 $k$ 的点标记｡ 将上一步标记的点及其连接的边全部删去｡ 我们希望知道在无穷多回合后，这棵树将被分为多少个连通块｡若最终两个点能够直接或间接的通过若干条边相连，则认为这两个点属于同一个连通块｡

输入格式：

第一行两个整数 $n$ , $k$ $(0 \le k \lt n \le 10^6)$，用空格隔开｡ 接下来 $n-1$ 行，每行两个用空格隔开的正整数 $u_i,v_i$ $(1 \le u_i,v_i \le n )$表示 $u_i$ 和 $v_i$ 之间有一条边｡输入的数据量较大，建议使用快速的读入方式｡

输出格式：

共一行一个整数，表示无穷多回合之后剩余的连通块个数｡

样例 1：

输入

3 1
1 2
2 3

输出

1

样例2：

输入

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

输出

5

样例解释：

对于样例 $2$ : 初始状态

一回合之后：

两回合之后：

最终保持不变，连通块为 $5$

限制与约定

对于 $40\%$ 的数据 ： $2 \le n \le 100$ $1 \le k \lt n$ 对于 $100\%$ 的数据 $2 \le n \le 10^6$ $1 \le k \lt n$