题目描述

$N$ 頂点 $M$ 辺の単純無向グラフ $G$ が与えられます。頂点には $1,2,\dots,N$、辺には $1,2,\dots,M$ の番号がついていて、辺 $i$ は頂点 $a_i$ と頂点 $b_i$ を結んでいます。
$G$ から $0$ 本以上の辺を取り除き、新しいグラフ $H$ を作ることを考えます。$H$ としてありうるグラフは全部で $2^M$ 個ありますが、そのうち頂点 $1$ と頂点 $k$ が連結であるものの個数を $2\ \leq\ k\ \leq\ N$ を満たす全ての整数 $k$ に対して求めてください。
答えは非常に大きくなる可能性があるので、 $998244353$ で割ったあまりを出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $a_1$ $b_1$ $\vdots$ $a_M$ $b_M$

输出格式

$N-1$ 行出力せよ。$i$ 行目には $k\ =\ i\ +\ 1$ のときの答えを出力せよ。

题目大意

题目大意

给一张 $N$ 个点 $M$ 条边的简单无向图 $G$。考虑删去 $0$ 条以上的边构成一张新图。对于每个点 $k(2\leq k\leq N)$，求有多少张新图满足点 $k$ 与点 $1$ 连通（模 $998244353$）。

输入格式

第 $1$ 行两个整数 $N$，$M$，表示点数和边数。

第 $2$ ~ $M+1$ 行每行两个整数 $a$， $b$ 表示 $a$ 与 $b$ 间有一条无向边。

输出格式

共 $N-1$ 行。第 $i$ 行输出一个整数表示满足点 $1$ 与点 $(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$
• $i\ \neq\ j$ ならば $(a_i,\ b_i)\ \neq\ (a_j,\ b_j)$ である。
• 入力は全て整数である。

Sample Explanation 1

$H$ としてあり得るグラフ、および頂点 $1$ と連結な頂点は次の通りです。 - 辺が無いとき、頂点 $1$ はどの点とも連結でない。 - 頂点 $1$ と頂点 $2$ を結ぶ辺だけがあるとき、頂点 $1$ は頂点 $2$ と連結である。 - 頂点 $2$ と頂点 $3$ を結ぶ辺だけがあるとき、頂点 $1$ はどの点とも連結でない。 - 両方の辺があるとき、頂点 $1$ は頂点 $2$ および頂点 $3$ と連結である。