我们爱森林

题目描述

我们有一个 $N$ 个顶点（编号为 1 到 N）、0 条边的图 $G$。给定长度为 $M$ 的序列 $u=(u_1,u_2,\ldots,u_M)$ 和 $v=(v_1,v_2,\ldots,v_M)$。

你将执行以下操作 $(N-1)$ 次：

均匀随机地选择 $i$（$1 \le i \le M$）。在 $G$ 中添加一条连接顶点 $u_i$ 和 $v_i$ 的无向边。

注意，即使 $G$ 中已经有一条或多条连接 $u_i$ 和 $v_i$ 的边，上述操作也会添加一条新的边。也就是说，最终得到的 $G$ 可能包含重边。

对于每个 $K=1,2,\ldots,N-1$，求第 $K$ 次操作后 $G$ 是森林的概率，并对 $998244353$ 取模后输出。

什么是森林？

没有环的无向图称为森林。森林不一定是连通的。

模 $998244353$ 下的概率定义

可以证明所求概率总是有理数。此外，在本问题的约束下，可以保证当所求概率用最简分数 $\frac{y}{x}$ 表示时，$x$ 不被 $998244353$ 整除。

此时，我们可以唯一确定一个介于 0 和 998244352（含端点）之间的整数 $z$，使得 $xz \equiv y \pmod{998244353}$。请打印这个 $z$。

输入格式

输入按以下格式从标准输入给出：

N M
u_1 v_1
⋮
u_M v_M

输出格式

打印 $N-1$ 行。第 $i$ 行应输出第 $i$ 次操作后 $G$ 是森林的概率对 $998244353$ 取模的结果。

样例

3 2
1 2
2 3

1
499122177

用 $(u, v)$ 表示连接顶点 $u$ 和 $v$ 的边。

第 1 次操作后，$G$ 将以 $1/2$ 的概率含有边 $(1, 2)$，以 $1/2$ 的概率含有边 $(2, 3)$。

两种情况 $G$ 都是森林，因此 $K=1$ 的答案是 1。

第 2 次操作后，$G$ 将以 $1/4$ 的概率含有边 $(1, 2)$ 和 $(1, 2)$，以 $1/4$ 的概率含有边 $(2, 3)$ 和 $(2, 3)$，以 $1/2$ 的概率含有边 $(1, 2)$ 和 $(2, 3)$。

只有当 $G$ 含有边 $(1, 2)$ 和 $(2, 3)$ 时，$G$ 才是森林。因此所求概率为 $1/2$；对 $998244353$ 取模后为 $499122177$，应输出该值。

4 5
1 2
1 2
1 4
2 3
2 4

1
758665709
918384805

数据范围

• $2 \le N \le 14$
• $N-1 \le M \le 500$
• $1 \le u_i, v_i \le N$
• $u_i \neq v_i$
• 输入中的所有值均为整数。