← 返回题目列表

AtCoder · abc253_h

Ex. 我们爱森林

中文机器翻译题面 查看原题

分数: 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