如果一条路径中所有边的颜色都互不相同，则称该路径为“坏”路径，否则称其为“好”路径。
如果一棵树中存在长度为 $k$ 的坏路径，则称该树为“坏”树，否则称其为“好”树。
现在给定一棵树，我们想要对其边进行染色。染色的美观度定义为所使用的不同颜色的数量。我们希望在保证树不成为坏树的前提下，使染色的美观度尽可能大。请问我们能达到的最大美观度是多少？
输入格式
第一行包含 $n$ 和 $k$，分别表示树的顶点数以及题目要求的不能存在长度为 $k$ 的坏路径的限制。
接下来的 $n - 1$ 行描述了树的边。第 $i$ 行包含两个整数 $u$ 和 $v$，表示 $u$ 和 $v$ 之间的一条边。保证这些边构成一棵树。
输出格式
输出一个整数，表示我们可以使用的最大颜色数量。
数据范围
- $1 \le k \le n \le 10^5$
- $1 \le k \le 30$
子任务
| 子任务 | 分值 | 限制 |
|---|---|---|
| 1 | 19 | 树中每个顶点的度数最多为 3。 |
| 2 | 7 | $n \le 10$ |
| 3 | 18 | $n \le 30, k \le 10$ |
| 4 | 22 | $n \le 100$ |
| 5 | 25 | $n \le 50000$ |
| 6 | 9 | 无额外限制 |
样例
样例输入 1
4 2 1 2 1 3 1 4
样例输出 1
1
样例输入 2
6 3 1 2 2 3 3 4 4 5 5 6
样例输出 2
3
样例输入 3
11 3 1 8 1 7 1 3 1 2 2 11 2 10 2 9 3 5 3 4 3 6
样例输出 3
7