Description

当且仅当一条路径中所有边的颜色都不同时，这条路径是坏的；否则，这条路径是好的。

当且仅当树中存在一条长度为 $k$ 的坏路径时，这棵树是坏的；否则，这棵树是好的。

现在我们有一棵树，需要给它的边染色。染色方案的美观度定义为使用的不同颜色数量。我们希望在不使树变坏的前提下，最大化美观度。请问能达到的最大美观度是多少？

Input Format

输入的第一行包含两个整数 $n$ 和 $k$，分别表示树的顶点数和禁止出现的坏路径长度。

接下来的 $n-1$ 行描述树的边。第 $i$ 行包含两个整数 $u$ 和 $v$，表示顶点 $u$ 和 $v$ 之间有一条边。保证这些边构成一棵树。

Output Format

输出一个整数，表示可以使用的最大颜色数量。

4 2
1 2
1 3
1 4

1

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

3

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

7

Hint

数据范围

• $1 \leq k \leq n \leq 10^5$
• $1 \leq k \leq 30$

子任务

翻译由 DeepSeek V3 完成