P12452 [INOI Team Selection 2021] Color Colony

A path is bad if and only if the colors of all edges in it are different, otherwise, the path is good. A tree is bad if and only if there exists a path of length $k$ in it which is bad, otherwise, the tree is good. Now we have a tree, we want to color its edges, the beauty of coloring of edges is the number of different colors we use, we want to make the beauty of coloring maximum possible, and we don't want our tree to become bad, what is maximum beauty we can reach?

The first line of the input contains $n$ and $k$, the number of vertices of the tree, and the value $k$ which declares we shouldn't have a bad path of length $k$ in tree. The following $n-1$ lines describe the edges of the tree. The $i$-th line contains two integers $u$ and $v$, denotes an edge between $u$ and $v$. It is guaranteed that these edges form a tree.

Print one integer, the maximum number of colors we can use.

### Constraints - $2 \leq k \leq n \leq 10^5$ - $2 \leq k \leq 30$ ### Subtask | subtask | score | limits | | :---: | :---: | :---: | | 1 | 19 | degree of each vertex in the tree is at most 3. | | 2 | 7 | $n \leq 10$ | | 3 | 18 | $n \leq 30$, $k \leq 10$ | | 4 | 22 | $n \leq 100$ | | 5 | 25 | $n \leq 50000$ | | 6 | 9 | No extra limits |