Background

With the decisive battle between the phantom and the shadow, the completion of the Moon Island altar, the appearance of the celestial storm, and the arrival of the heavenly guardians, all secrets of the Moon and ancient times seem to have reached the final chapter.

The old gods are about to return.

Problem Description

An ordinary tree on Moon Island keeps growing under the erosion of moonlight, and becomes even more uncontrolled as the lunar storm arrives.

Specifically, the growth rules are as follows:

• Initially, there is a rooted tree $T_0$ with $n$ nodes, rooted at $1$.

• On day $i$, the tree grows from $T_{i - 1}$ into $T_i$. The rule is: let $v$ be a leaf node in $T_{i - 1}$ with the minimum depth (if there are multiple, choose any one). Replace the node $v$ with $T_{i - 1}$ itself.

In this problem, the depth of a node is defined as the number of edges on the simple path from it to the root node. Note that this may differ from the usual definition.

The figure below shows an example of growing from $T_{i-1}$ to $T_i$:

Besides dealing with the heavenly guardians, it is also important to estimate environmental effects, so you need to compute:

• For each integer $d \in [1, m]$, find $S_d$, the minimum number of days such that, in $T_{S_d}$, the minimum depth among all leaf nodes is greater than $d$.

Output the answers modulo $998244353$.

Input Format

The first line contains two integers $n, m$, representing the number of nodes in $T_0$ and the depth range for which answers are required.

In the next $n - 1$ lines, each line contains two integers $x, y$, indicating that there is an edge between nodes $x$ and $y$ in $T_0$.

Output Format

Output $m$ lines. On the $i$-th line, output one integer representing $S_i$.

4 10
1 2
2 3
1 4

1
3
4
7
9
12
16
24
32
45

Hint

[Sample 1 Explanation]

The figure shows the shapes of $T_0$ to $T_3$. The shallowest leaf is marked in red, and the part grown in the most recent operation is marked in blue.

You can see that, in $T_1$, the minimum leaf depth is greater than $1$; in $T_3$, the minimum leaf depth is greater than $2$; and after one more operation, in $T_4$, the minimum leaf depth will be greater than $3$ (it should be $4$). This explains the first three lines of the sample output:

[Constraints]

This problem uses bundled testdata.

For $100\%$ of the testdata: $2 \le n, m \le {10}^5$.

Translated by ChatGPT 5