

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