AT_dwacon6th_final_c Tree Shrinking

[problemUrl]: https://atcoder.jp/contests/dwacon6th-final/tasks/dwacon6th_final_c $ 1,\ \ldots,\ N $ の番号がついた $ N $ 個の頂点からなる木が与えられます。 $ 1,\ \ldots,\ N-1 $ の番号がついた $ N-1 $ 本の辺があり、辺 $ i $ は頂点 $ a_i,b_i $ をつないでいます。 ニワンゴ君は操作を $ N-1 $ 回行います。$ i $ 回目の操作は以下の手順からなります。 - 木の辺を等確率で選ぶ(選ばれた辺を $ e $, $ e $ の端点を $ u,v $ とする) - $ u $ の次数を $ x $, $ v $ の次数を $ y $ として $ xy $ 点得る - $ e $ を取り除き、$ u,v $ を $ 1 $ つの頂点にまとめる(すなわち辺の縮約を行う)。 $ N-1 $ 回の操作によって、ニワンゴ君が得た得点の総和の期待値に $ (N-1)! $ をかけた値(これは整数になることが示せます)を $ 998244353 $ で割ったあまりを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ a_1 $ $ b_1 $ $ \vdots $ $ a_{N-1} $ $ b_{N-1} $

答えを出力せよ。

### 制約 - $ 2\ \leq\ N\ \leq\ 10^{5} $ - $ 1\ \leq\ a_i,\ b_i\ \leq\ N $ - 与えられるグラフは木 ### Sample Explanation 1 \- 例えば $ 1 $ 回目の操作で辺 $ 1 $ が選ばれた場合、$ 9 $ 点を得てグラフは以下の図のように変化します !\[f5f78a71a75bc641ea14315dcd873900.png\](https://img.atcoder.jp/dwacon6th-final/f5f78a71a75bc641ea14315dcd873900.png) ### Sample Explanation 3 \- 答えを $ 998244353 $ で割ったあまりを求めてください。