分数: 600 点
问题陈述
我们有一个图表 G 与 N 顶点编号 1 通过 N 和 0 边缘。 给你序列 u=(u_1,u_2,\ldots,u_M),v=(v_1,v_2,\ldots,v_M) 长度 M.
您将执行以下操作 (N-1) 次。
- 选择 i (1 \leq i \leq M) 均匀随机。 添加到 G 连接顶点的无向边 u_i 和 v_i.
请注意,上面的操作将添加一条连接顶点的新边 u_i 和 v_i 即使 G 之间已存在一条或多条边。 换句话说,由此产生的 G 可能包含多个边。
对于每个 K=1,2,\ldots,N-1,求概率,模 998244353,即 G 是一片森林 K第一次操作。
什么是森林?
没有环的无向图称为森林。 森林不一定是相连的。
概率模数的定义 998244353
我们可以证明所求的概率始终是有理数。 此外,在该问题的约束下,可以保证,当所求概率由不可约分数表示时 \frac{y}{x}, x 不可整除 998244353.
那么,我们可以唯一确定一个整数 z 之间 0 和 998244352 (含)使得 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- 第行应包含概率,模 998244353,即 G 是一片森林 i第一次操作。
示例输入 1
3 2 1 2 2 3
示例输出 1
1 499122177
让我们表示为 (u, v) 连接顶点的边 u 和 v.
之后 1-st 操作, G 将具有:
- 边缘 (1, 2) 的概率为 1/2;
- 边缘 (2, 3) 的概率为 1/2.
在这两种情况下, G 是一片森林,所以答案为 K=1 is 1.
之后 2-nd操作, G 将具有:
- 边缘 (1, 2) 和 (1, 2) 的概率为 1/4;
- 边缘 (2, 3) 和 (2, 3) 的概率为 1/4;
- 边缘 (1, 2) 和 (2, 3) 的概率为 1/2.
G 仅当 G 有边缘 (1, 2) 和 (2, 3)。 因此,寻求的概率是 1/2;当以模表示时 998244353,它是 499122177,应该打印出来。
示例输入 2
4 5 1 2 1 2 1 4 2 3 2 4
示例输出 2
1 758665709 918384805