CF2190D.Prufer Vertex

For a tree $T$ with $n \ge 2$ vertices, consider the standard process for generating its Prufer sequence. We repeatedly perform the following steps until only two vertices remain:

• Select the leaf with the smallest label;
• Remove it from the tree.

It is known that vertex $n$ is always one of the two remaining vertices. Let $v$ be the other remaining vertex. We define the Prufer vertex of $T$ as $P(T) = v$.

You are given a forest with $n$ vertices and $m$ edges. Let $k$ be the number of connected components in this forest, and let their sizes be $s_1, s_2, \ldots, s_k$. It is known that there are exactly $n^{k - 2} \prod\limits_{i=1}^k s_i$ ways to add edges to the forest so that it becomes a single tree.

For each $v$ ($1 \le v \lt n$), calculate how many of these ways result in a tree $T$ satisfying $P(T) = v$.

Since the answers can be large, print them modulo $998\,244\,353$.

对于一棵包含 $n \ge 2$ 个顶点的树 $T$，考虑其 Prüfer 序列 的标准生成过程：我们不断重复以下步骤，直到树中仅剩两个顶点：

• 选取标号最小的叶子顶点；
• 将其从树中删除。

已知顶点 $n$ 总是最后剩余的两个顶点之一。设另一个剩余顶点为 $v$。我们定义树 $T$ 的 Prüfer 顶点为 $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 < n$），计算有多少种这样的加边方式能产生一棵满足 $P(T) = v$ 的树 $T$。

由于答案可能很大，请对 $998\,244\,353$ 取模后输出。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($2 \le n \le 2 \cdot 10^5$, $0 \le m \le n - 1$) — the number of vertices and edges in the forest, respectively.

The next $m$ lines of each test case contain two integers $u$ and $v$ ($1 \le u, v \le n, u \neq v$), describing an edge between vertices $u$ and $v$. It is guaranteed that these edges form a forest (that is, the graph is acyclic).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, print $n - 1$ integers on a single line. The $i$-th integer should be the number of ways to add edges to the forest so that it becomes a tree $T$ satisfying $P(T) = i$, modulo $998\,244\,353$.

对于每个测试用例，在一行中输出 $n - 1$ 个整数。其中第 $i$ 个整数表示：向该森林中添加边使其成为一棵树 $T$，且满足 $P(T) = i$ 的方案数，对 $998\,244\,353$ 取模的结果。

In the first example, there are no edges in the forest, and there are $3$ ways to complete it to a tree. One of them is to add edges $(1, 2)$ and $(1, 3)$. There are $2$ leaves: vertex $2$ and $3$. Since $2$ has a smaller label, it gets deleted from the tree, and only two vertices remain: $1$ and $3$. Therefore, the Prufer vertex of this tree is $1$.

In the third example, the forest is shown below:

Suppose we add edges $(3, 5)$ and $(3, 1)$ to complete it to a tree $T$. It is going to look like this:

It can be shown that $P(T) = 1$.

在第一个例子中，森林中没有边，将其补全为一棵树共有 $3$ 种方式。其中一种是添加边 $(1, 2)$ 和 $(1, 3)$。此时树中有 $2$ 个叶子节点：顶点 $2$ 和 $3$。由于 $2$ 的标号更小，它将从树中被删除，剩余两个顶点为 $1$ 和 $3$。因此，该树的 Prüfer 编码顶点为 $1$。

在第三个例子中，森林如下图所示：

假设我们添加边 $(3, 5)$ 和 $(3, 1)$ 将其补全为一棵树 $T$，则该树形如：

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