「Astra」是一款精美的桌上遊戲，玩家們輪流透過標記星星來探索星座。這款遊戲巧妙地融合了戰術與策略，規則精簡直觀，易於上手且節奏輕快。
Photo by @kavics004 on BoardGameGeek
考慮一個由 Alice 和 Bob 進行的雙人遊戲。在這個遊戲中，有一個樹形星座，可以看作是一個由 $n$ 顆星星（編號為 $1$ 到 $n$）和 $(n - 1)$ 條邊組成的連通圖。最開始，只有一顆星星 $s$ 被標記。Alice 和 Bob 輪流根據以下規則標記剩餘的星星：
- 每回合，玩家必須標記至少 $1$ 顆且最多 $k$ 顆星星。
- 每顆星星只能被標記一次。
- 設 $a_1, a_2, \cdots, a_p$ 為某一回合中被標記的星星，按照它們被標記的順序排列：
- 標記 $a_1$ 時，它必須是某顆已標記星星的鄰居。
- 對於所有 $2 \le i \le p$，標記 $a_i$ 時，它必須是 $a_{i-1}$ 的鄰居。
如果兩顆星星 $u$ 和 $v$ 直接由一條邊相連，則稱它們是鄰居。
標記最後一顆星星的玩家贏得該星座。假設 Alice 先手，且兩位玩家都採取最佳策略，對於每個 $1 \le s \le n$，確定誰將贏得該星座。
輸入格式
輸入包含多組測試資料。輸入的第一行包含一個整數 $T$ ($1 \le T \le 100$)，表示測試資料的組數。對於每組測試資料：
第一行包含兩個整數 $n$ 和 $k$ ($2 \le n \le 2 \times 10^3$，$1 \le k < n$)，分別表示星星的數量和每回合最多可以標記的星星數量。
接下來的 $(n - 1)$ 行中，第 $i$ 行包含兩個整數 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n$)，表示有一條邊連接星星 $u_i$ 和 $v_i$。
保證所有測試資料中 $n$ 的總和至多為 $2 \times 10^3$。
輸出格式
對於每組測試資料，輸出一行，包含一個字串 $d_1 d_2 \cdots d_n$ ($d_i \in \{0, 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\}$。如果 Alice 選擇 $\{2, 6\}$，Bob 隨後可以標記 $\{3\}$，此時將剩下 $2$ 顆不相鄰的星星。在接下來的回合中，每位玩家只能標記一顆星星，Bob 將成為獲勝者。Alice 的其他選擇也可以類似地進行分析。
- 考慮 $s = 2$。在第一回合，Alice 有五種選擇：標記 $\{1\}$、$\{3\}$、$\{6\}$、$\{3, 4\}$ 或 $\{3, 5\}$。Alice 可以選擇標記 $\{3\}$，此時將剩下 $4$ 顆不相鄰的星星。在接下來的回合中，每位玩家只能標記一顆星星，Alice 將成為獲勝者。
對於第二組範例測試資料，由於 $k = 1$，遊戲將進行恰好 $3 - 1 = 2$ 回合，因此 Bob 總是獲勝者。
對於第三組範例測試資料，如果 $s = 1$ 或 $s = 3$，Alice 可以直接標記剩餘的 $2$ 顆星星並贏得該星座。