Score : $600$ points

问题描述

我们有一个图 $G$，包含 $N$ 个顶点，编号为 $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$ 已经存在一条或多条连接顶点 $u_i$ 和 $v_i$ 的边，上述操作也会添加一条新的边。换句话说，最终得到的 $G$ 可能包含多条边。

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

什么是森林？

没有环的无向图被称为森林。森林不一定连通。

概率对 $998244353$ 取模的定义

我们可以证明所求概率始终是一个有理数。此外，在本题的约束条件下，可以保证当所求概率表示为不可约分数 $\frac{y}{x}$ 时，$x$ 不会被 $998244353$ 整除。

因此，我们可以唯一确定一个整数 $z$，满足 $0 \leq z \leq 998244352$（包含边界），使得 $xz \equiv y \pmod{998244353}$。请输出这个 $z$ 值。

以上为通义千问 qwen-max 翻译，仅供参考。

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.

What is a forest?

An undirected graph without a cycle is called a forest. A forest is not necessarily connected.

Definition of probability modulo $998244353$

We can prove that the sought probability is always a rational number. Moreover, under the Constraints of this problem, it is guaranteed that, when the sought probability is represented by an irreducible fraction $\frac{y}{x}$, $x$ is indivisible by $998244353$.

Then, we can uniquely determine an integer $z$ between $0$ and $998244352$ (inclusive) such that $xz \equiv y \pmod{998244353}$. Print this $z$.

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

update @ 2024/3/10 10:48:57