409720: GYM103708 B Building 5G antennas

Treeland is a country consisting of $$$n$$$ cities and $$$n-1$$$ bidirectional roads. As you might imagine, Treeland is a tree, which means that there is exactly one simple path between each pair of cities.

The president of Treeland plans to build a 5G network in the country during $$$n$$$ days. Everyday, a 5G antenna tower will be built in a different city according to the following rules:

• Each day, an antenna must be built in a city at a distance not greater than $$$k$$$ from a city with an antenna already built. This restriction does not apply for day $$$1$$$.
• If during $$$i$$$-th day there are multiple valid cities to build an antenna, the one with the smallest number must be chosen.

More formally, let $$$P=[p_1, p_2, \dots, p_n]$$$ be a permutation where $$$p_i$$$ is the city where an antenna is built during day $$$i$$$. For all $$$i>1$$$ there must be a $$$j<i$$$ such that $$$dist(p_i, p_j) \leq k$$$, and $$$P$$$ must be the lexicographically smallest possible permutation. Here we define $$$dist(p_i, p_j)$$$ as the number of roads in the simple path from $$$p_i$$$ to $$$p_j$$$.

Find and print $$$P$$$.

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 10^5$$$ and $$$1 \leq k \leq 100$$$).

Each of the following $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$, indicating that there is a road connecting cities $$$u$$$ and $$$v$$$.

Print a single line with $$$n$$$ integers separated by a space $$$-$$$ the answer to the problem.

3 1
1 3
2 3

1 3 2

5 2
1 4
1 5
4 2
5 3

1 2 3 4 5

5 1
1 2
1 5
2 4
3 5

1 2 4 5 3