Minimum Reachability in Augmented Tree

You are given a directed tree with n vertices numbered from 1 to n and exactly n – 1 edges. The tree is rooted at vertex 1 and every edge is directed from its parent to its child. In other words, for each edge u → v, vertex u is the parent of v in the tree.

You are allowed to use at most k extra directed edges on a per‐query basis. That is, for each starting vertex s (which you treat as the source), you may imagine adding up to k extra edges in addition to the tree edges in order to “improve” the reachability from s. However, there is an important restriction on extra edges:

• An extra edge u → v is allowed only if there is no tree edge between u and v in either direction (i.e. if u is the parent of v or v is the parent of u, you cannot add an extra edge between them).

Using the tree edges (which incur no “cost”) plus up to k extra edges (each extra edge may be used anywhere along the path) you want to travel along a directed path starting at s. Let f(s) be the minimum vertex number (that is, the smallest label) among all vertices reachable from s by a path that uses at most k extra edges. Note that s is always considered reachable from itself.

Important: In some subtasks only the answer for vertex 1 is required. In the full problem, however, you must compute and output the answer for every vertex s (1 ≤ s ≤ n).

Input Format:

• The first line contains two integers n and k (with 1 ≤ n ≤ 10⁵ and 0 ≤ k ≤ 10).
• Then follow n – 1 lines. Each of these lines contains two integers u and v (1 ≤ u,v ≤ n) representing a directed tree edge from u to v (so u is the parent of v).

Output Format:

• Output a single line containing n integers separated by spaces, where the s-th integer is f(s), the minimum reachable vertex from vertex s using at most k extra edges according to the rule above.
• For those subtasks where only vertex 1’s answer is required, simply output f(1).

Explanation:

Consider the following example. Suppose the tree is as follows:

5  k

Edges:
1 2
1 3
3 4
3 5

For k = 0 (i.e. no extra edge allowed), the only paths available are the tree paths. In a directed tree the reachable set from a vertex s is exactly the subtree of s (including s itself). Hence, for each vertex s, f(s) is simply the minimum label in the subtree of s computed in the usual way (note that labels are arbitrary and not necessarily increasing along any tree path).

For k ≥ 1, you are allowed one extra edge. However, note that an extra edge from a vertex to its parent is not allowed (since the tree already has that edge in the opposite direction, or it is adjacent in the tree). Thus, for a vertex s that is a direct child of 1 with no descendants, you cannot add an extra edge from s directly to 1. But if s has any descendant u for which u is not a direct child of 1, then an extra edge from u to 1 is allowed. In that case, a path from s can go down to u using tree edges and then jump via the extra edge to 1, making f(s) = 1 (since 1 is the smallest possible label).

Thus, for k ≥ 1 the answer is computed as follows:

• f(1) = 1 always.
• For any other vertex s:
  • If s is not a direct child of 1, then you can use an extra edge (if needed) and obtain 1, so f(s) = 1.
  • If s is a direct child of 1 and s has no descendants (i.e. its subtree is just itself), then no extra edge can help; thus f(s) = s.
  • If s is a direct child of 1 but it has at least one descendant, then an extra edge from that descendant to 1 is allowed so f(s) = 1.

Your task is to compute f(s) for every vertex s given the tree and the integer k.

inputFormat

The first line contains two integers n and k (1 ≤ n ≤ 10⁵; 0 ≤ k ≤ 10). The next n – 1 lines each contain two integers u and v (1 ≤ u,v ≤ n) indicating there is a directed edge from node u to node v. It is guaranteed that these edges form a tree rooted at node 1.

outputFormat

Output a single line with n space‐separated integers. The s-th integer should be the minimum reachable vertex f(s) from node s using at most k extra edges according to the rules described. For subtasks where only vertex 1’s answer is required, output only f(1).

sample

5 0
1 2
1 3
3 4
3 5

1 2 1 4 5