题目说明

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

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

• 随机选择一个$i$ $(1\leq i\leq M)$。在$G$中添加一条连接顶点$u_i$和$v_i$的无向边。

注意，即使$G$已经存在一条或多条连接$a_i$和$b_i$的边，上述操作也会添加一条连接顶点$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$。

约束条件

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

输入

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

$N$ $M$ $u_1$ $v_1$ $\vdots$ $u_M$ $v_M$

输出

打印$N-1$行。第$i$行应包含在第$i$次操作后$G$是森林的概率，模$998244353$。

示例输入 1

3 2
1 2
2 3

示例输出 1

1
499122177

记$(u, v)$为连接顶点$u$和$v$的边。

在第$1$次操作之后，$G$有以下情况：

• 边$(1, 2)$的概率为$1/2$；
• 边$(2, 3)$的概率为$1/2$。

在这两种情况下，$G$都是一个森林，所以$K=1$时的答案是$1$。

在第$2$次操作之后，$G$有以下情况：

• 边$(1, 2)$和边$(1, 2)$的概率为$1/4$；
• 边$(2, 3)$和边$(2, 3)$的概率为$1/4$；
• 边$(1, 2)$和边$(2, 3)$的概率为$1/2$。

当且仅当$G$具有边$(1, 2)$和边$(2, 3)$时，$G$才是一个森林。因此，所求概率为$1/2$，当使用模$998244353$表示时，为$499122177$，应该输出这个值。

示例输入 2

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

示例输出 2

1
758665709
918384805