「Astra」は、プレイヤーが交互に星に印をつけて星座を発見していく美しいボードゲームです。このゲームは戦術と戦略が巧みに組み合わされており、洗練された直感的なルールセットにより、覚えやすく短時間で遊べるようになっています。

Photo by @kavics004 on BoardGameGeek

Alice と Bob の 2 人で行うゲームを考えます。このゲームには木状の星座があり、これは $n$ 個の星（$1$ から $n$ までの番号が付けられている）と $(n - 1)$ 本の辺からなる連結グラフとみなすことができます。最初、1 つの星 $s$ だけに印がついています。Alice と Bob は以下のルールに従って交互に残りの星に印をつけていきます：

• 各ターンにおいて、プレイヤーは少なくとも $1$ 個、最大で $k$ 個の星に印をつけなければなりません。
• 各星には 1 度だけ印をつけることができます。
• あるターンに印をつけられた星を、印をつけられた順に $a_1, a_2, \cdots, a_p$ とします：
  • $a_1$ に印をつけるとき、それはすでに印がついている星の隣接頂点でなければなりません。
  • すべての $2 \le i \le p$ について、$a_i$ に印をつけるとき、それは $a_{i-1}$ の隣接頂点でなければなりません。

2 つの星 $u$ と $v$ が辺で直接結ばれているとき、それらは隣接しているといいます。

最後の星に印をつけたプレイヤーがその星座を獲得します。Alice が先手で、両プレイヤーが最適に行動するとき、各 $1 \le s \le n$ について、どちらが星座を獲得するかを判定してください。

入力

複数のテストケースが与えられます。入力の最初の行には、テストケースの数を表す整数 $T$（$1 \le T \le 100$）が含まれます。各テストケースについて：

最初の行には、星の数と各ターンに印をつけることができる星の最大数を表す 2 つの整数 $n$ と $k$（$2 \le n \le 2 \times 10^3$, $1 \le k < n$）が含まれます。

続く $(n - 1)$ 行のうち $i$ 行目には、星 $u_i$ と $v_i$ を結ぶ辺が存在することを表す 2 つの整数 $u_i$ と $v_i$（$1 \le u_i, v_i \le n$）が含まれます。

すべてのテストケースにわたる $n$ の総和は $2 \times 10^3$ を超えないことが保証されます。

出力

各テストケースについて、文字列 $d_1 d_2 \cdots d_n$（$d_i \in \{0, 1\}$）を含む 1 行を出力してください。ここで $d_i$ は $s = i$ のときにどちらが星座を獲得するかを表します。Alice が勝つ場合は $d_i = 1$、そうではなく Bob が勝つ場合は $d_i = 0$ です。

出力例

入力 1

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

出力 1

011000
000
101

注記

最初のサンプルテストケースは上の図に示されています。

• $s = 1$ の場合を考えます。最初のターンで、Alice には $\{2\}$、$\{2, 3\}$、または $\{2, 6\}$ に印をつける 3 つの選択肢があります。もし Alice が $\{2, 6\}$ を選んだ場合、Bob は次に $\{3\}$ に印をつけることができ、離れた $2$ 個の星が残ります。以降のターンでは、各プレイヤーは 1 つずつしか星に印をつけることができず、Bob が勝者となります。Alice の他の選択肢も同様に分析できます。
• $s = 2$ の場合を考えます。最初のターンで、Alice には $\{1\}$、$\{3\}$、$\{6\}$、$\{3, 4\}$、または $\{3, 5\}$ に印をつける 5 つの選択肢があります。Alice は $\{3\}$ に印をつけることを選ぶことができ、離れた $4$ 個の星が残ります。以降のターンでは、各プレイヤーは 1 つずつしか星に印をつけることができず、Alice が勝者となります。

2 番目のサンプルテストケースでは、$k = 1$ であるため、ちょうど $3 - 1 = 2$ ターンが行われ、常に Bob が勝者となります。

3 番目のサンプルテストケースでは、$s = 1$ または $s = 3$ の場合、Alice は残りの $2$ 個の星に直接印をつけて星座を獲得することができます。