AT_abc414_f [ABC414F] Jump Traveling

頂点に $ 1 $ から $ N $ の番号がつけられた $ N $ 頂点の木および整数 $ K $ が与えられます。 $ i $ 番目の辺は頂点 $ u_i $ と頂点 $ v_i $ を双方向に結んでいます。 あなたはいま頂点 $ 1 $ にいます。以下の操作を $ 0 $ 回以上繰り返すことができます。 - あなたが今いる頂点からの距離が $ K $ であるような頂点を一つ選び、その頂点に移動する。ただし、 $ 2 $ 頂点間の距離は $ 2 $ 頂点を結ぶ単純パスに含まれる辺の個数とする。 各 $ k=2,\ldots,N $ に対して、操作を繰り返して頂点 $ k $ に移動することができるかどうか判定し、移動できるならば操作回数の最小値を求めてください。 $ 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` とせよ。

### Sample Explanation 1 この入出力例は $ 1 $ つのテストケースからなります。 頂点 $ 1 $ との距離が $ 2 $ である頂点は $ 3,4 $ であるため、この $ 2 $ つの頂点には $ 1 $ 回の操作で移動することができます。 また、頂点 $ 1 $ から頂点 $ 4 $ に移動したのち、頂点 $ 4 $ からの距離が $ 2 $ である頂点 $ 6 $ に移動することで、頂点 $ 6 $ には $ 2 $ 回の操作で移動することができます。 頂点 $ 2,5 $ にはどのように操作しても移動することができません。 ### 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 $ - 与えられるグラフは木 - 全てのテストケースに対する $ N $ の総和は $ 2\times 10^5 $ 以下 - 入力は全て整数