F - Jump Traveling Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 525 点

問題文

頂点に 1 から N の番号がつけられた N 頂点の木および整数 K が与えられます。i 番目の辺は頂点 u_i と頂点 v_i を双方向に結んでいます。

あなたはいま頂点 1 にいます。以下の操作を 0 回以上繰り返すことができます。

  • あなたが今いる頂点からの距離が K であるような頂点を一つ選び、その頂点に移動する。ただし、2 頂点間の距離は 2 頂点を結ぶ単純パスに含まれる辺の個数とする。

各 k=2,\ldots,N に対して、操作を繰り返して頂点 k に移動することができるかどうか判定し、移動できるならば操作回数の最小値を求めてください。

T 個のテストケースが与えられるので、それぞれについて解いてください。

制約

  • 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
  • 与えられるグラフは木
  • 全てのテストケースに対する N の総和は 2\times 10^5 以下
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。ここで、\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

1
6 2
1 2
2 3
2 4
4 5
5 6

出力例 1

-1 1 1 -1 2

この入出力例は 1 つのテストケースからなります。

頂点 1 との距離が 2 である頂点は 3,4 であるため、この 2 つの頂点には 1 回の操作で移動することができます。

また、頂点 1 から頂点 4 に移動したのち、頂点 4 からの距離が 2 である頂点 6 に移動することで、頂点 6 には 2 回の操作で移動することができます。

頂点 2,5 にはどのように操作しても移動することができません。

入力例 2

3
2 20
1 2
10 2
1 9
1 8
1 5
6 8
4 5
2 8
5 10
7 9
3 5
10 1
2 6
2 9
8 9
9 10
3 9
4 9
7 9
1 6
3 5

出力例 2

-1
1 1 1 -1 1 1 -1 -1 1
2 4 4 5 1 4 4 3 4

Score : 525 points

Problem Statement

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.

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.

Input

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

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 Input 1

1
6 2
1 2
2 3
2 4
4 5
5 6

Sample Output 1

-1 1 1 -1 2

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.

Sample Input 2

3
2 20
1 2
10 2
1 9
1 8
1 5
6 8
4 5
2 8
5 10
7 9
3 5
10 1
2 6
2 9
8 9
9 10
3 9
4 9
7 9
1 6
3 5

Sample Output 2

-1
1 1 1 -1 1 1 -1 -1 1
2 4 4 5 1 4 4 3 4