102537: [AtCoder]ABC253 Ex - We Love Forest

Problem Statement

We have a graph $G$ with $N$ vertices numbered $1$ through $N$ and $0$ edges. You are given sequences $u=(u_1,u_2,\ldots,u_M),v=(v_1,v_2,\ldots,v_M)$ of length $M$.

You will perform the following operation $(N-1)$ times.

• Choose $i$ $(1 \leq i \leq M)$ uniformly at random. Add to $G$ an undirected edge connecting Vertices $u_i$ and $v_i$.

Note that the operation above will add a new edge connecting Vertices $u_i$ and $v_i$ even if $G$ already has one or more edges between them. In other words, the resulting $G$ may contain multiple edges.

For each $K=1,2,\ldots,N-1$, find the probability, modulo $998244353$, that $G$ is a forest after the $K$-th operation.

Constraints

• $2 \leq N \leq 14$
• $N-1 \leq M \leq 500$
• $1 \leq u_i,v_i \leq N$
• $u_i\neq v_i$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print $N-1$ lines. The $i$-th line should contain the probability, modulo $998244353$, that $G$ is a forest after the $i$-th operation.

Sample Input 1

3 2
1 2
2 3

Sample Output 1

1
499122177

Let us denote by $(u, v)$ the edge connecting Vertices $u$ and $v$.

After the $1$-st operation, $G$ will have:

• Edge $(1, 2)$ with a probability of $1/2$;
• Edge $(2, 3)$ with a probability of $1/2$.

In both cases, $G$ is a forest, so the answer for $K=1$ is $1$.

After the $2$-nd operation, $G$ will have:

• Edges $(1, 2)$ and $(1, 2)$ with a probability of $1/4$;
• Edges $(2, 3)$ and $(2, 3)$ with a probability of $1/4$;
• Edges $(1, 2)$ and $(2, 3)$ with a probability of $1/2$.

$G$ is a forest only when $G$ has Edges $(1, 2)$ and $(2, 3)$. Therefore, the sought probability is $1/2$; when represented modulo $998244353$, it is $499122177$, which should be printed.

Sample Input 2

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

Sample Output 2

1
758665709
918384805

问题描述

我们有一个顶点编号为1到N的图G，共有0条边。你将得到长度为M的序列u=(u₁,u₂,…,u_M)和v=(v₁,v₂,…,v_M)。

你需要执行(N-1)次以下操作：

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

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

对于每个K=1,2,…,N-1，找出图G在第K次操作后是森林的概率，结果对998244353取模。

约束条件

• 2≤N≤14
• N-1≤M≤500
• 1≤u_i,v_i≤N
• u_i≠v_i
• 输入中的所有值都是整数。

输入

输入通过标准输入给出以下格式：

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

输出

打印N-1行。第i行应该包含图G在第i次操作后是森林的概率，结果对998244353取模。

样例输入1

3 2
1 2
2 3

样例输出1

1
499122177

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

在第1次操作后，图G将有：

• 连接顶点1和2的边$(1, 2)$，概率为1/2；
• 连接顶点2和3的边$(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)$时才是森林。因此，所求概率为1/2；当结果对998244353取模时，它为499122177，应该打印出来。

样例输入2

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

样例输出2

1
758665709
918384805