「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$ 粒星星並贏得呢個星座。