E. Ezra and Experiments
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Recently, Ezra has been interested in Conway's Game of Life (you don't need to know it to solve this problem though!)  — specifically, trying to generalize it to trees.

His favorite tree is undirected, with vertices numbered from $$$1$$$ through $$$n$$$. It is rooted at vertex $$$1$$$.

In the Game of Life, it is optimal for cells to have three living neighbors. Ezra has decided that for his experiment, the optimal number of neighbors is described by a constant $$$l$$$.

More specifically, he defines the aliveness of a vertex $$$v$$$ recursively:

  • Let $$$S$$$ be the sum of aliveness across the direct children of $$$v$$$, plus one (in particular, if $$$v$$$ is a leaf, then $$$S=1$$$).
  • Then, the aliveness of $$$v$$$ will be $$$\max(0,l-|l-S|)$$$.

Ezra can easily calculate the aliveness of vertices in a given tree using his programming skills, but the issue comes when he tries to modify the tree. Help him answer the following question, for all $$$1 \le i \le n$$$ independently:

  • Suppose you create a new vertex and attach it with an undirected edge to vertex $$$i$$$. What will the aliveness of vertex $$$1$$$ in this new tree be?
Input

Input consists of multiple tests. The first line contains $$$t$$$, the number of tests ($$$1 \le t \le 10^5$$$).

The first line of each test contains $$$n$$$ and $$$l$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le l \le 10^9$$$).

The next $$$n-1$$$ lines contain two integers $$$u_i$$$ and $$$v_i$$$, the edges of the graph ($$$1 \le u_i, v_i \le n$$$).

It is guaranteed that in each test, the given graph is a tree, the sum of $$$n$$$ over all tests does not exceed $$$2 \cdot 10^5$$$.

Output

For each test, output $$$n$$$ integers, the answers for each $$$1 \le i \le n$$$.

Example
Input
3
4 3
1 2
1 3
1 4
1 1000000000
8 2
2 1
3 1
4 2
5 2
6 2
7 3
8 4
Output
1 1 1 1
2
0 1 2 1 1 1 2 1
Note

In the first test, if we attach a new vertex to the root of the tree, the aliveness of each leaf will be $$$\max(0,l-|l-1|)=\max(0,3-2)=1$$$. There will be $$$4$$$ leaves, so the aliveness of the root is $$$\max(0,l-|l-(4+1)|)=\max(0,3-2)=1$$$.

Now, suppose we attach a new vertex to vertex $$$2$$$. The aliveness of that leaf will be $$$1$$$, so the aliveness of vertex $$$2$$$ is $$$\max(0,l-|l-2|)=2$$$. Then, the sum of aliveness for the direct children of the root, will be $$$2+1+1=4$$$. This is the same as in the case where we attach a vertex directly to the root, so the answer is again $$$1$$$.

In the second test, the aliveness of the root would become $$$\max(0,l-|l-2|)$$$. Substituting in values, we get $$$\max(0,1\,000\,000\,000-999\,999\,998)=2$$$.