/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
頂点に 1 から N の番号がついた N 頂点 0 辺のグラフ G があります。また、長さ M の数列 u=(u_1,u_2,\ldots,u_M),v=(v_1,v_2,\ldots,v_M) が与えられます。
あなたは以下の操作を N-1 回行います。
- i (1 \leq i \leq M) を一様ランダムに選ぶ。 G に頂点 u_i と頂点 v_i を結ぶ無向辺を追加する。
すでに G に u_i と v_i を結ぶ辺があった場合も、新たに辺を追加する操作を行うことに注意してください。すなわち、操作後の G には多重辺が存在する可能性があります。
K=1,2,\ldots,N-1 について、K 回の操作後に G が森になっている確率を \bmod 998244353 で求めてください。
森とは？
閉路を含まない無向グラフのことを森と呼びます。森は連結でなくても構いません。
確率 \bmod 998244353 の定義
この問題で求める確率は必ず有理数になることが証明できます。 また、この問題の制約下では、求める確率を既約分数 \frac{y}{x} で表したときに x が 998244353 で割り切れないことが保証されます。
このとき xz \equiv y \pmod{998244353} を満たすような 0 以上 998244352 以下の整数 z が一意に定まります。この z を答えてください。
制約
- 2 \leq N \leq 14
- N-1 \leq M \leq 500
- 1 \leq u_i,v_i \leq N
- u_i\neq v_i
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M u_1 v_1 \vdots u_M v_M
出力
N-1 行出力せよ。i 行目には i 回の操作後に G が森になっている確率を \bmod 998244353 で出力せよ。
入力例 1
3 2 1 2 2 3
出力例 1
1 499122177
頂点 u と頂点 v を結ぶ辺を (u,v) と書きます。
操作を 1 回行った後の G は以下のようになります。
- 1/2 の確率で、辺 (1, 2) が存在する。
- 1/2 の確率で、辺 (2, 3) が存在する。
どちらの場合も G は森なので、 K=1 の場合の答えは 1 です。
操作を 2 回行った後の G は以下のようになります。
- 1/4 の確率で、辺 (1, 2),(1,2) が存在する。
- 1/4 の確率で、辺 (2, 3),(2,3) が存在する。
- 1/2 の確率で、辺 (1, 2),(2,3) が存在する。
辺 (1,2),(2,3) が存在するときのみ G は森となっています。よって求める確率は 1/2 であり、これを \bmod 998244353 で表した 499122177 を出力してください。
入力例 2
4 5 1 2 1 2 1 4 2 3 2 4
出力例 2
1 758665709 918384805
Score : 600 points
Problem Statement
We have a graph G with N vertices numbered 1 through N and 0 edges. You are given sequences u=(u_1,u_2,\ldots,u_M),v=(v_1,v_2,\ldots,v_M) of length M.
You will perform the following operation (N-1) times.
- Choose i (1 \leq i \leq M) uniformly at random. Add to G an undirected edge connecting Vertices u_i and v_i.
Note that the operation above will add a new edge connecting Vertices u_i and v_i even if G already has one or more edges between them. In other words, the resulting G may contain multiple edges.
For each K=1,2,\ldots,N-1, find the probability, modulo 998244353, that G is a forest after the K-th operation.
What is a forest?
An undirected graph without a cycle is called a forest. A forest is not necessarily connected.
Definition of probability modulo 998244353
We can prove that the sought probability is always a rational number. Moreover, under the Constraints of this problem, it is guaranteed that, when the sought probability is represented by an irreducible fraction \frac{y}{x}, x is indivisible by 998244353.
Then, we can uniquely determine an integer z between 0 and 998244352 (inclusive) such that xz \equiv y \pmod{998244353}. Print this z.
Constraints
- 2 \leq N \leq 14
- N-1 \leq M \leq 500
- 1 \leq u_i,v_i \leq N
- u_i\neq v_i
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M u_1 v_1 \vdots u_M v_M
Output
Print N-1 lines. The i-th line should contain the probability, modulo 998244353, that G is a forest after the i-th operation.
Sample Input 1
3 2 1 2 2 3
Sample Output 1
1 499122177
Let us denote by (u, v) the edge connecting Vertices u and v.
After the 1-st operation, G will have:
- Edge (1, 2) with a probability of 1/2;
- Edge (2, 3) with a probability of 1/2.
In both cases, G is a forest, so the answer for K=1 is 1.
After the 2-nd operation, G will have:
- Edges (1, 2) and (1, 2) with a probability of 1/4;
- Edges (2, 3) and (2, 3) with a probability of 1/4;
- Edges (1, 2) and (2, 3) with a probability of 1/2.
G is a forest only when G has Edges (1, 2) and (2, 3). Therefore, the sought probability is 1/2; when represented modulo 998244353, it is 499122177, which should be printed.
Sample Input 2
4 5 1 2 1 2 1 4 2 3 2 4
Sample Output 2
1 758665709 918384805