对于具有 $$$n \ge 2$$$ 个顶点的树 $$$T$$$,请考虑生成其 Prufer 序列的标准过程。我们重复执行以下步骤,直到只剩下两个顶点:
- 选择标签最小的叶子;
- 将其从树中删除。
已知顶点 $$$n$$$ 始终是剩余的两个顶点之一。令 $$$v$$$ 为另一个剩余顶点。我们定义 普鲁弗顶点 $$$T$$$ 的 为 $$$P(T) = v$$$。
给你一个森林,有 $$$n$$$ 个顶点和 $$$m$$$ 个边。令 $$$k$$$ 为该森林中连通分量的数量,并令它们的大小为 $$$s_1, s_2, \ldots, s_k$$$。已知总共有 $$$n^{k - 2} \prod\limits_{i=1}^k s_i$$$ 种方法向森林添加边,使其成为一棵树。
对于每个 $$$v$$$ ($$$1 \le v \lt n$$$),计算有多少种方法会产生满足 $$$P(T) = v$$$ 的树 $$$T$$$。
由于答案可能很大,请以 $$$998\,244\,353$$$ 为模打印它们。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$0 \le m \le n - 1$$$) - 分别是森林中的顶点和边的数量。
每个测试用例接下来的 $$$m$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n, u \neq v$$$),描述顶点 $$$u$$$ 和 $$$v$$$ 之间的边。保证这些边形成森林(即图是非循环的)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,在一行上打印 $$$n - 1$$$ 整数。第 $$$i$$$ 个整数应该是向森林添加边的方式数量,使其成为满足 $$$P(T) = i$$$ 的树 $$$T$$$,模 $$$998\,244\,353$$$。
示例
输入复制
33 05 44 23 41 24 56 31 66 42 1
输出复制
1 20 0 0 112 0 1 6 5
注意
在第一个示例中,森林中没有边,有 $$$3$$$ 方法将其完善为树。其中之一是添加边 $$$(1, 2)$$$ 和 $$$(1, 3)$$$。有 $$$2$$$ 叶子:顶点 $$$2$$$ 和 $$$3$$$。由于 $$$2$$$ 具有较小的标签,因此它会从树中删除,并且仅保留两个顶点:$$$1$$$ 和 $$$3$$$。因此,这棵树的普鲁弗顶点是$$$1$$$。
在第三个示例中,森林如下所示:

假设我们添加边 $$$(3, 5)$$$ 和 $$$(3, 1)$$$ 将其补全为一棵树 $$$T$$$。它看起来像这样:

可以证明$$$P(T) = 1$$$。