CF2190D Prufer Vertex

给定一棵含有 $n \geq 2$ 个顶点的树 $T$，考虑其 [Prufer 序列](https://en.wikipedia.org/wiki/Prufer_sequence) 的生成标准过程：不断重复如下步骤，直到仅剩下两个顶点为止： - 选择最小编号的叶子结点； - 将其从树中删除。 已知编号为 $n$ 的顶点始终是最后剩下的两个顶点之一。令 $v$ 表示另一个剩下的顶点。我们定义 $T$ 的 Prufer 顶点为 $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 \leq v < n$），请计算有多少种补边方法能够得到一棵 $T$，使得 $P(T) = v$。 由于答案可能很大，请对 $998\,244\,353$ 取模后输出。

输入包含多组测试数据。第一行为测试用例数量 $t$（$1 \leq t \leq 10^4$）。 每组测试数据的第一行为两个整数 $n$ 和 $m$（$2 \leq n \leq 2 \cdot 10^5$，$0 \leq m \leq n-1$），表示森林的顶点数和边数。 接下来的 $m$ 行，每行包含两个整数 $u$ 和 $v$（$1 \leq u, v \leq n, u \neq v$），表示一条无向边。保证这些边构成一棵无环森林。 保证所有测试用例中 $n$ 之和不超过 $2 \cdot 10^5$。

对于每组测试用例，输出 $n-1$ 个整数，依次表示对于 $P(T)=1,2,\ldots,n-1$ 的情况，将森林补成树 $T$ 的方案数，对 $998\,244\,353$ 取模。

在第一个样例中，森林中没有边，可以补全为树的方案有 $3$ 种。例如加入 $(1,2)$ 和 $(1,3)$。此时叶子结点为 $2$ 和 $3$，由于 $2$ 编号较小，先移除 $2$，最后剩下 $1$ 和 $3$。因此此树的 Prufer 顶点为 $1$。 在第三个样例中，森林如下所示：  假设我们补上 $(3,5)$ 和 $(3,1)$，得到的树如下：  可以证明此树的 Prufer 顶点为 $1$。 由 ChatGPT 5 翻译