配点 : $600$ 点

問題文

$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$ で割ったあまりを出力してください。

制約

• $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)$ である。
• 入力は全て整数である。

入力

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

$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$ はどの点とも連結でない。
• 頂点 $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