K-step Tree

Task

The final round of IIOT is approaching and after solving so many tree problems during the previous edition of the contest, you start to wonder what the next tree problem is going to be. Your instincts were spot-on, finally here is a tree problem for you to solve!

You are given a tree graph with $N$ nodes, rooted at vertex $0$.
We define the $K$-th ancestor of a vertex as the node we reach if we move $K$ steps up the tree, in the direction of the root.
If we reach the root before doing $K$ steps, then we say that the $K$-th ancestor does not exist.

For a fixed integer $K$, your task is to find the $K$-th ancestor of each node in the tree, or report that it doesn't exist.

Input data

The input file consists of:

• a line containing integers $N$, $K$.
• $N - 1$ lines, the $i$-th of which consisting of integers $X_{i}$, $Y_{i}$, representing an edge between nodes $X_{i}$ and $Y_{i}$.

Output data

The output file must contain a single line consisting of the $N$ integers, representing the $K$-th ancestors of each node, or $-1$ if it does not exist.

Constraints and clarifications

• $1 \le K < N \le 10^6$.
• $0 \le X_i, Y_i < N$ and $X_i \neq Y_i$ for each $i=0\ldots N-2$.

Example

stdin

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

stdout

-1 -1 0 -1 -1 0 1 4 1 2 2

Explanation

The tree in the sample test case is displayed in the following figure.