AT_abc414_f [ABC414F] Jump Traveling

You are given a tree with $ N $ vertices numbered from $ 1 $ to $ N $ and an integer $ K $ . The $ i $ -th edge bidirectionally connects vertices $ u_i $ and $ v_i $ . You are currently at vertex $ 1 $ . You can repeat the following operation zero or more times: - Choose a vertex whose distance from the vertex you are currently at is $ K $ , and move to that vertex. Here, the distance between two vertices is the number of edges in the simple path connecting the two vertices. For each $ k=2,\ldots,N $ , determine whether you can move to vertex $ k $ by repeating the operation, and if you can move, find the minimum number of operations. You have $ T $ test cases, so solve each of them.

The input is given from Standard Input in the following format, where $ \mathrm{case}_i $ means the $ i $ -th test case. > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ Each test case is given in the following format: > $ N $ $ K $ $ u_1 $ $ v_1 $ $ u_2 $ $ v_2 $ $ \vdots $ $ u_{N-1} $ $ v_{N-1} $

Output $ T $ lines. The $ i $ -th line should contain the answer for the $ i $ -th test case in the following format: > $ \mathrm{ans}_2 $ $ \mathrm{ans}_3 $ $ \ldots $ $ \mathrm{ans}_N $ $ \mathrm{ans}_i $ is the answer for $ k=i $ . If you can move to vertex $ i $ by repeating the operation, $ \mathrm{ans}_i $ is the minimum number of operations; otherwise, $ \mathrm{ans}_i $ is `-1`.

### Sample Explanation 1 This sample input/output consists of one test case. The vertices whose distance from vertex $ 1 $ is $ 2 $ are vertices $ 3 $ and $ 4 $ , so you can move to these two vertices with one operation. Also, by moving from vertex $ 1 $ to vertex $ 4 $ , then moving to vertex $ 6 $ whose distance from vertex $ 4 $ is $ 2 $ , you can move to vertex $ 6 $ with two operations. You cannot move to vertices $ 2 $ and $ 5 $ no matter how you perform the operations. ### Constraints - $ 1\leq T\leq 10^5 $ - $ 2\leq N\leq 2\times 10^5 $ - $ 1\leq K\leq 20 $ - $ 1\leq u_i\lt v_i\leq N $ - The given graph is a tree. - The sum of $ N $ over all test cases is at most $ 2\times 10^5 $ . - All input values are integers.