给你一棵无向树,由 $$$n$$$ 个顶点组成。
如果该顶点恰好有一个与其相邻的顶点,则该顶点称为叶子。
某对顶点之间的距离是它们之间的最短路径中的边数。
如果一组叶子中任意一对叶子之间的最大距离小于或等于 $$$k$$$,我们就称该组叶子为漂亮。
您想要将所有叶子分割成不相交的漂亮集合。这种分组的最少组数是多少?
输入
第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$3 \le n \le 10^6$$$, $$$1 \le k \le 10^6$$$) — 树中的顶点数以及每个美丽集合中任意一对叶子之间的最大距离。
接下来的 $$$n - 1$$$ 行包含两个整数 $$$v_i$$$ 和 $$$u_i$$$ ($$$1 \le v_i, u_i \le n$$$) — 第 $$$i$$$ 条边的描述。
保证给定的边形成一棵树。
输出
打印一个整数 - 分割可以拥有的漂亮集合的最小数量。
示例
输入 #1
9 3 1 2 1 3 2 4 2 5 3 6 6 7 6 8 3 9
输出 #1
2
输入 #2
5 3 1 2 2 3 3 4 4 5
输出 #2
2
输入 #3
6 1 1 2 1 3 1 4 1 5 1 6
输出 #3
5
注意
这是第一个示例的图表: