AT_abc414_f.[ABC414F] Jump Traveling

给定一棵有 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$，以及一个整数 $K$。第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$，是双向的。

你现在位于顶点 $1$。你可以重复进行如下操作 $0$ 次或多次：

• 从你当前所在的顶点，选择一个距离为 $K$ 的顶点，移动到该顶点。这里，两个顶点之间的距离指的是连接这两个顶点的简单路径上边的数量。

对于每个 $k=2,\ldots,N$，判断是否可以通过若干次操作移动到顶点 $k$，如果可以，输出所需操作次数的最小值；否则输出 $-1$。

有 $T$ 个测试用例，请分别解答。

输入以如下格式从标准输入读入。这里，$\mathrm{case}_i$ 表示第 $i$ 个测试用例。

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

每个测试用例的格式如下：

$N$ $K$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{N-1}$ $v_{N-1}$

输出 $T$ 行。第 $i$ 行为第 $i$ 个测试用例的答案，格式如下：

$\mathrm{ans}_2$ $\mathrm{ans}_3$ $\ldots$ $\mathrm{ans}_N$

其中，$\mathrm{ans}_i$ 表示对于 $k=i$ 的答案。如果可以通过若干次操作移动到顶点 $i$，输出最小操作次数，否则输出 $-1$。

限制条件

• $1\leq T\leq 10^5$
• $2\leq N\leq 2\times 10^5$
• $1\leq K\leq 20$
• $1\leq u_i< v_i\leq N$
• 给定的图为树
• 所有测试用例中 $N$ 的总和不超过 $2\times 10^5$
• 输入均为整数

样例解释 1

本样例仅包含 $1$ 个测试用例。与顶点 $1$ 距离为 $2$ 的顶点为 $3,4$，因此可以通过 $1$ 次操作移动到这两个顶点。再从顶点 $1$ 移动到顶点 $4$ 后，从顶点 $4$ 出发，距离为 $2$ 的顶点为 $6$，因此可以通过 $2$ 次操作移动到顶点 $6$。顶点 $2,5$ 无论如何都无法通过操作到达。

由 ChatGPT 4.1 翻译