Connectivity 2

题目描述

给定一个有 $N$ 个顶点和 $M$ 条边的简单无向图 $G$。顶点编号为 $1,2,\dots,N$，边编号为 $1,2,\dots,M$，第 $i$ 条边连接顶点 $a_i$ 和顶点 $b_i$。
考虑从 $G$ 中删除零条或多条边以得到一个新图 $H$。我们可以得到 $2^M$ 个图作为 $H$。在这些图中，求满足顶点 $1$ 与顶点 $k$ 直接或间接连通的图的数量，对于每个整数 $k$，使得 $2 \leq k \leq N$。
由于计数可能非常大，请将它们对 $998244353$ 取模后输出。

输入格式

输入由标准输入按如下格式提供： $N$ $M$ $a_1$ $b_1$ $\vdots$ $a_M$ $b_M$

输出格式

输出 $N-1$ 行。第 $i$ 行应包含对于 $k = i + 1$ 的答案。

3 2
1 2
2 3

2
1

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

43
31
37
41

2 0

0

提示

$2 \leq N \leq 17$ $0 \leq M \leq \frac{N(N-1)}{2}$ $1 \leq a_i \lt b_i \leq N$ $(a_i, b_i) \neq (a_j, b_j)$ if $i \neq j$. 输入中的所有数值均为整数。我们可以得到如下的图作为 $H$。

没有边的图。顶点 $1$ 与任何其他顶点都不连通。 只有连接顶点 $1$ 和 $2$ 的那条边的图。顶点 $2$ 可从顶点 $1$ 到达。 只有连接顶点 $2$ 和 $3$ 的那条边的图。顶点 $1$ 与任何其他顶点都不连通。 两条边都有的图。顶点 $2$ 和 $3$ 可从顶点 $1$ 到达。

标签: AtCoder|abc213G

来源

AtCoder|abc213G