[ABC253Ex] We Love Forest

给定 $ n $ 个点无边的图，给定 $ m $ 条待选的无向边。每次等概率地从 $ m $ 条边中抽取一条边加入图中。 $ n - 1 $ 次询问求加 $ 1, 2, \cdots, n - 1 $ 次边后原图形成一个森林（一棵树亦为森林）的概率为多少。对 $ 998244353 $ 取模。

[problemUrl]: https://atcoder.jp/contests/abc253/tasks/abc253_h 頂点に $ 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 $ を答えてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ u_1 $ $ v_1 $ $ \vdots $ $ u_M $ $ v_M $

$ N-1 $ 行出力せよ。$ i $ 行目には $ i $ 回の操作後に $ G $ が森になっている確率を $ \bmod\ 998244353 $ で出力せよ。

3 2
1 2
2 3

1
499122177

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

1
758665709
918384805

### 制約 - $ 2\ \leq\ N\ \leq\ 14 $ - $ N-1\ \leq\ M\ \leq\ 500 $ - $ 1\ \leq\ u_i,v_i\ \leq\ N $ - $ u_i\neq\ v_i $ - 入力は全て整数 ### Sample Explanation 1 頂点 $ 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 $ を出力してください。