AT_arc217_e [ARC217E] Tree Growing

頂点に $ 1 $ から $ N $ までの番号がついた $ N $ 頂点の木が与えられます。ここで $ N $ は $ 2 $ 以上です。 $ i $ 番目 $ (1\le i\le N-1) $ の辺は頂点 $ u_i $ と頂点 $ v_i $ を相互に結んでいます。 この木に対して操作をちょうど $ K $ 回行います。 $ k $ 回目 $ (1\le k\le K) $ の操作は以下の通りです。 - その時点での木の辺 $ N-2+k $ 本の中から、一本の辺を一様ランダムに選ぶ。選んだ辺が結ぶ頂点を $ u,v $ として、新たに頂点 $ N+k $ を用意し、頂点 $ u,N+k $ を結ぶ辺、頂点 $ v,N+k $ を結ぶ辺を追加する。その後、選んだ辺を削除する。 $ k=1,2,\ldots,K $ に対し、 $ k $ 回目の操作後に、与えられた木は $ N+k $ 頂点の木になっていることに注意してください。 $ K $ 回の操作後の $ \displaystyle \sum_{1\le i < j\le N+K} \text{dist}(i,j) $ の期待値を $ \text{mod}\ 998244353 $ で求めてください。ただし、 $ \text{dist}(i,j) $ で木の頂点 $ i $ と頂点 $ j $ の距離を表します。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。 期待値 $ \ \text{mod}\ 998244353 $ の定義求める期待値は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、求める有理数を既約分数 $ \displaystyle \frac{P}{Q} $ で表した時、 $ Q \neq 0 \bmod 998244353 $ となることが証明できます。 よって、 $ R \times Q \equiv P \bmod 998244353, 0 \leq R \lt 998244353 $ を満たす整数 $ R $ が一意に定まります。 この $ R $ を答えてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ K $ $ u_1 $ $ v_1 $ $ u_2 $ $ v_2 $ $ \vdots $ $ u_{N-1} $ $ v_{N-1} $

各テストケースに対する答えを順に改行区切りで出力せよ。

### Sample Explanation 1 $ 1 $ 番目のテストケースについて考えます。 例えば $ 2 $ 回の操作は以下のように進行します。 - $ 1 $ 回目：頂点 $ 1 $ と頂点 $ 2 $ を結ぶ辺が選ばれる。頂点 $ 1 $ と頂点 $ 5 $ を結ぶ辺、頂点 $ 2 $ と頂点 $ 5 $ を結ぶ辺が追加された後、頂点 $ 1 $ と頂点 $ 2 $ を結ぶ辺が削除される。 - $ 2 $ 回目：頂点 $ 2 $ と頂点 $ 5 $ を結ぶ辺が選ばれる。頂点 $ 2 $ と頂点 $ 6 $ を結ぶ辺、頂点 $ 5 $ と頂点 $ 6 $ を結ぶ辺が追加された後、頂点 $ 2 $ と頂点 $ 5 $ を結ぶ辺が削除される。 この場合の $ \displaystyle \sum_{1\le i < j\le N+K} \text{dist}(i,j) $ の値は $ 32 $ です。 $ \displaystyle \sum_{1\le i < j\le N+K} \text{dist}(i,j) $ の値は $ \displaystyle \frac12 $ の確率で $ 31 $ に、 $ \displaystyle \frac12 $ の確率で $ 32 $ になります。 ### Constraints - $ 1\le T $ - $ 2\le N $ - 全てのテストケースにおける $ N $ の総和は $ 3\times 10^5 $ 以下 - $ 1\le K $ - 全てのテストケースにおける $ K $ の総和は $ 10^6 $ 以下 - $ 1\le u_i < v_i \le N $ - 与えられるグラフは木 - 入力される値は全て整数