连通性 2

题目描述

给定一个具有 $N$ 个顶点和 $M$ 条边的简单无向图 $G$。顶点编号为 $1,2,\dots,N$,边编号为 $1,2,\dots,M$,边 $i$ 连接顶点 $a_i$ 和顶点 $b_i$。

考虑从 $G$ 中删除零条或多条边得到新图 $H$。可以得到的 $H$ 共有 $2^M$ 种。其中,对于每个满足 $2 \le k \le N$ 的整数 $k$,求使顶点 $1$ 与顶点 $k$ 直接或间接连通的 $H$ 的数量。

由于数量可能十分巨大,请对 $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

可以作为 $H$ 得到的图如下。

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

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

43
31
37
41

2 0

0

数据范围

• $2 \le N \le 17$
• $0 \le M \le \frac{N(N-1)}{2}$
• $1 \le a_i \lt b_i \le N$
• 当 $i \neq j$ 时,$(a_i, b_i) \neq (a_j, b_j)$
• 输入均为整数