阿斯特拉 - Problem

“Astra”是一款精美的桌面游戏，玩家们轮流通过标记星星来探索星座。这款游戏巧妙地融合了战术与策略，规则精简直观，易于上手且节奏轻快。

Photo by @kavics004 on BoardGameGeek

考虑一个由 Alice 和 Bob 进行的双人游戏。在这个游戏中，有一个树形星座，可以看作是一个由 $n$ 颗星星（编号为 $1$ 到 $n$）和 $n - 1$ 条边组成的连通图。最开始，只有一颗星星 $s$ 被标记。Alice 和 Bob 轮流根据以下规则标记剩余的星星：

每回合，玩家必须标记至少 $1$ 颗且最多 $k$ 颗星星。
每颗星星只能被标记一次。
设 $a_1, a_2, \dots, 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$。

对于每个测试用例，输出一行，包含一个长度为 $n$ 的字符串 $d_1 d_2 \dots d_n$ ($d_i \in \{0, 1\}$)，其中 $d_i$ 表示当 $s = i$ 时谁将获胜。如果 Alice 获胜，则 $d_i = 1$；否则，如果 Bob 获胜，则 $d_i = 0$。

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$ 颗星星并赢得该星座。

QOJ.ac