Description

Xiao Q is designing a board game.

In the game he designed, pieces can be placed on the grid points on the board. Some pairs of grid points are connected by lines, and a piece may move only between grid points that are connected by a line. There are $V$ grid points in total, labeled $0, 1, 2, \cdots, V - 1$, and they are connected; that is, starting from any grid point, the piece can reach all grid points. Xiao Q also guarantees that the path between any two grid points is unique.

Xiao Q now wants to know: starting from grid point $0$, after moving $N$ steps, what is the maximum number of grid points that can be visited? A grid point may be visited multiple times, but is counted only once.

Input Format

The first line contains $2$ positive integers $V, N$, where $V$ is the total number of grid points and $N$ is the number of moves.

Each of the next $V - 1$ lines contains two integers $a_i, b_i$, indicating that there is a line connecting grid points $a_i$ and $b_i$.

Output Format

Output a single integer, the maximum number of grid points that can be visited.

5 2
1 0
2 1
3 2
4 3

3

9 5
0 1
0 2
2 6
4 2
8 1
1 3
3 7
3 5

5

Hint

[Explanation for Sample 1]

From grid point $0$, move $2$ steps. The piece visits $0, 1, 2$, i.e., $3$ grid points.

[Explanation for Sample 2]

One feasible path is $0 \to 1 \to 3 \to 5 \to 3 \to 7$, visiting $0, 1, 3, 5, 7$, i.e., $5$ grid points.

Constraints

For $100\%$ of the testdata, $1 \le N, V \le 100$, and $0 \le a_i, b_i < V$.

Translated by ChatGPT 5