Ex - We Love Forest
当前没有测试数据。
Ex - 我们爱森林
得分：$600$ 分
问题描述
我们有一个标号为 $1$ 到 $N$ 的 $N$ 个顶点和 $0$ 条边的图 $G$。给出了长度为 $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$ 已经有一条或多条连接这两个顶点的边的情况下，上述操作仍会添加一条连接 $u_i$ 和 $v_i$ 的新边。换句话说，得到的图 $G$ 可能包含多条边。
对于每个 $K=1,2,\ldots,N-1$，求 $G$ 在第 $K$ 次操作之后是森林的概率，对 $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-1$ 行。第 $i$ 行应该输出 $G$ 在第 $i$ 次操作之后是森林的概率，对 $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)$。因此，所求概率是 $1/2$；对 $998244353$ 取模后，结果为 $499122177$，需要输出。
4 5
1 2
1 2
1 4
2 3
2 4
1
758665709
918384805