C. Game on tree
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Andreas has a tree with $$$n$$$ nodes (undirected connected graph without cycles).

Andreas and Eleni will play the following game:

  • The first player chooses a starting node. (The starting node is visited at this turn)

  • Then, each player, starting from the second one, chooses a node that is not already chosen and has distance$$$^{\dagger}$$$ at most $$$k$$$ from at least one of the already chosen nodes. Moreover, there should be a path that starts from the starting node (that was chosen in the first move) and passes through every node already chosen (it may also pass through non-chosen nodes).

$$${\dagger}$$$ The distance between two nodes of a tree is the length (in edges) of the shortest path between these nodes.

If there are no other nodes that can be chosen the game ends and the player who makes the last move wins.

Who will win the game if both players play optimally?

You already know that Andreas really wants to win so you need to find the answer for every starting node.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 3 \cdot 10^{5}$$$) — the number of nodes and the number $$$k$$$.

The $$$i^{th}$$$ of the following $$$n−1$$$ lines in the test case contains two positive integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i,v_i \le n$$$), meaning that there exists an edge between them in the graph.

It is guaranteed that the given edges form a tree.

Output

For each test case, print $$$n$$$ integer — the $$$i^{th}$$$ integer should be $$$1$$$ if the first player wins with starting node $$$i$$$ otherwise it should be $$$0$$$.

Scoring
SubtaskConstraintsPoints
$$$\sum {n}$$$Additional
$$$1$$$$$$\sum {n} \le 3 \cdot 10^{5}$$$Every node $$$j$$$ ($$$j \neq 1$$$) has a direct edge to $$$1$$$ (the tree is a star)$$$3$$$
$$$2$$$$$$\sum {n} \le 3 \cdot 10^{5}$$$There is an edge from every $$$i$$$ to $$$i+1$$$ ($$$1 \le i \le n-1$$$) (the tree is a line)$$$5$$$
$$$3$$$$$$\sum {n} \le 10^{3}$$$$$$k = n$$$$$$7$$$
$$$4$$$$$$\sum {n} \le 3 \cdot 10^{5}$$$$$$k = n$$$$$$8$$$
$$$5$$$$$$\sum {n} \le 50$$$—$$$12$$$
$$$6$$$$$$\sum {n} \le 3 \cdot 10^{5}$$$$$$k = 1$$$$$$10$$$
$$$7$$$$$$\sum {n} \le 700$$$—$$$15$$$
$$$8$$$$$$\sum {n} \le 5000$$$—$$$17$$$
$$$9$$$$$$\sum {n} \le 3 \cdot 10^{5}$$$—$$$23$$$
Example
Input
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
Output
0 0 
0 1 1 0 1 1 
0 0 0 0
Note

In the first test case, no matter how they will play all of the nodes will be selected so the second player always wins.

Below you can see a way that the second player will win in the second test case if the starting node was $$$1$$$.

Blue nodes are those that were selected by the first player, and red nodes are those that were selected by the second player.