题目描述

Andreas 有一棵包含 $n$ 个节点的树，即一个无向连通无环图。

Andreas 和 Eleni 要在这棵树上玩一个游戏：

1. 第一名玩家先选择一个起始节点。该节点在这一回合被视为已经选择。
2. 从第二名玩家开始，双方轮流选择一个尚未被选择的节点，并且这个节点必须满足：
   • 它到至少一个已选择节点的距离不超过 $k$；
   • 存在一条从起始节点出发的路径，经过所有已经被选择的节点。该路径可以经过未被选择的节点。

树上两点之间的距离定义为它们之间最短路径的边数。

如果当前玩家无法再选择任何节点，游戏结束，最后一次成功选择节点的玩家获胜。

你需要判断：在双方都采取最优策略时，对于每一个可能的起始节点，先手是否必胜。

输入格式

第一行包含一个整数 $t$，表示测试组数。

对于每组数据：

第一行包含两个整数 $n,k$。

接下来 $n-1$ 行，每行包含两个整数 $u_i,v_i$，表示树中存在一条边 $(u_i,v_i)$。

保证给出的边构成一棵树。

输出格式

对于每组数据，输出 $n$ 个整数。第 $i$ 个整数表示以节点 $i$ 作为起始节点时的结果：

• 若先手在双方最优策略下必胜，输出 1；
• 否则输出 0。

数据范围

• $1\le t\le10^4$；
• $1\le k\le n\le3\cdot10^5$；
• 所有测试组的 $\sum n\le3\cdot10^5$。

样例

输入

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

输出

0 0
0 1 1 0 1 1
0 0 0 0

样例解释

第一组数据中，无论如何游戏最终都会选择所有节点，因此后手获胜。

第二组数据中，如果起点为 $1$，后手存在获胜策略。原题给出了如下示意图，其中蓝色节点表示先手选择的节点，红色节点表示后手选择的节点。

子任务

难度评价

预估难度：CF 2700。

这题的关键不只是普通树上博弈。合法状态还要求“已选点能被一条从起点出发的路径覆盖”，这会把局面限制成某种树上连通路径/分支结构。需要把游戏过程转化成可计算的 Sprague-Grundy 或奇偶结构，并且还要对每个起点批量求解。全数据 $\sum n\le3\cdot10^5$，说明朴素枚举起点和状态完全不可行，整体是比较硬的树形结构博弈题。