頂点 \(1\) を根とした根付き木を考える.

辺 \(E_i\) を選んで除いたとき, \(E\) が結んでいる頂点を \(u_i, v_i\) (\(v_i\) の方が深い) とすると, \(v_i\) を根とする部分木とそれ以外に分割される. 全体の頂点数を \(c_1\), \(v_i\) を根とする部分木に含まれる頂点の数を \(c_{v_i}\) とすると, \(A, B\) をランダムに選んだときに連結である確率は,

\[p_i = \frac{ \combi{ c_1-c_{v_i} }{2} + \combi{ c_{v_i} }{2} }{ \combi{N}{2} }\]

となる. \(E_i\) をすべての辺について考えると, \(A\) と \(B\) が連結である確率は

\[P = \frac{1}{N-1} \sum_i p_i\]

となる. 部分木の頂点数はあらかじめ DP で計算しておく.

出力方法は色々書いてるが, \(998244353\) は素数なので, 割り算は逆元を掛けろと言ってるだけである.