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 翻译