该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

KOI 国家由 $N$ 个村庄组成。每个村庄从 1 到 $N$ 编号。国家中共有 $N - 1$ 条道路，每条道路连接两个不同的村庄，编号从 1 到 $N - 1$。第 $i$ 条道路连接的是第 $x_i$ 个村庄与第 $y_i$ 个村庄。

KOI 国家中的任意两个村庄之间，恰好存在一条路径将它们连接起来。

从第 $x$ 个村庄到第 $y$ 个村庄的路径可以表示为一个村庄序列：$x$ - $z_1$ - $z_2$ - ⋯ - $z_t$ - $y$，该路径满足以下两个条件：

• 路径上相邻两个村庄之间，即 $x$ 与 $z_1$，$z_1$ 与 $z_2$，⋯，$z_t$ 与 $y$ 之间都存在道路直接连接。
• 路径中不得有重复村庄。也就是说，$x$，$z_1$，⋯，$z_t$，$y$ 均为互不相同的村庄。

路径的“长度”定义为该路径上所经过的道路数，即 $t + 1$。

现在，计划在若干个村庄中设置加油站。根据 KOI 国家法律，加油站必须满足以下条件：

• 对于任意长度为 $k$ 的路径，路径中必须至少有一个村庄设有加油站。

在满足上述条件的前提下，找出设置加油站所需的最小数量。

输入格式

第一行包含两个整数 $N$ 和 $k$，以空格分隔，表示村庄的数量与路径长度限制。

接下来 $N - 1$ 行，每行包含两个整数 $x_i$ 和 $y_i$，表示道路直接连接的两个村庄编号。

输出格式

输出一行，表示满足条件所需的最少加油站数量。

6 2
1 2
1 3
2 4
2 5
4 6

1

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

2

说明/提示

样例 1 说明

只需在第 $2$ 个村庄设置加油站即可满足所有长度为 $2$ 的路径。

样例 2 说明

仅在第 $2$ 个村庄设置加油站不能满足所有长度为 $2$ 的路径（例如路径 $4-6-7$ 不包含加油站）。若再在第 $6$ 个村庄也设置加油站，则所有长度为 $2$ 的路径都包含至少一个加油站。因此最小加油站数量为 $2$。

限制条件

• 所有输入均为整数。
• $2 \leq N \leq 200\,000$
• $1 \leq k \leq N - 1$
• $1 \leq x_i, y_i \leq N$
• $x_i \ne y_i$
• 任意两个村庄之间，存在唯一一条路径相连。
• 至少存在一条长度为 $k$ 的路径。