G - Connectivity 2 Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 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 のときの答えを出力せよ。

入力例 1

3 2
1 2
2 3

出力例 1

2
1

H としてあり得るグラフ、および頂点 1 と連結な頂点は次の通りです。

  • 辺が無いとき、頂点 1 はどの点とも連結でない。
  • 頂点 1 と頂点 2 を結ぶ辺だけがあるとき、頂点 1 は頂点 2 と連結である。
  • 頂点 2 と頂点 3 を結ぶ辺だけがあるとき、頂点 1 はどの点とも連結でない。
  • 両方の辺があるとき、頂点 1 は頂点 2 および頂点 3 と連結である。

入力例 2

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

出力例 2

43
31
37
41

入力例 3

2 0

出力例 3

0

Score : 600 points

Problem Statement

Given is a simple undirected graph G with N vertices and M edges. The vertices are numbered 1,2,\dots,N, the edges are numbered 1,2,\dots,M, and Edge i connects Vertex a_i and Vertex b_i.
Consider removing zero or more edges from G to get a new graph H. There are 2^M graphs that we can get as H. Among them, find the number of such graphs that Vertex 1 and Vertex k are directly or indirectly connected, for each integer k such that 2 \leq k \leq N.
Since the counts may be enormous, print them modulo 998244353.

Constraints

  • 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.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
a_1 b_1
\vdots
a_M b_M

Output

Print N-1 lines. The i-th line should contain the answer for k = i + 1.

Sample Input 1

3 2
1 2
2 3

Sample Output 1

2
1

We can get the following graphs as H.

  • The graph with no edges. Vertex 1 is disconnected from any other vertex.
  • The graph with only the edge connecting Vertex 1 and 2. Vertex 2 is reachable from Vertex 1.
  • The graph with only the edge connecting Vertex 2 and 3. Vertex 1 is disconnected from any other vertex.
  • The graph with both edges. Vertex 2 and 3 are reachable from Vertex 1.

Sample Input 2

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

Sample Output 2

43
31
37
41

Sample Input 3

2 0

Sample Output 3

0