AT_otemae2019_i ピーターランドの道路整備 (Road Development in Peterland)

[problemUrl]: https://atcoder.jp/contests/otemae2019/tasks/otemae2019_i ピーターランドには $ N $ 個の都市があり，$ 1 $ から $ N $ までの番号が付いている．$ 2 $ 個の都市を双方向に結ぶ道がちょうど $ N $ 本あり，$ i $ 番目 ($ 1\ \leq\ i\ \leq\ N $) の道は都市 $ A_i $ と都市 $ B_i $ を結んでいる．どの都市からどの都市へも，いくつかの道を使って移動できる． $ 2 $ 個の都市の間の距離を，一方から他方へ移動するために通る必要がある道の本数の最小値と定める．$ N $ 個の都市から$ 2 $ 個の都市を選ぶ方法は $ \frac{N\ (N\ -\ 1)}{2} $ 通りあるが，それらについての距離の $ 2 $ 乗の総和を $ 998\,244\,353 $ で割った余りを求めよ．

入力は以下の形式で標準入力から与えられる． > $ N $ $ A_1 $ $ B_1 $ $ \vdots $ $ A_N $ $ B_N $

標準出力に，距離の $ 2 $ 乗の総和を $ 998\,244\,353 $ で割った余りを $ 1 $ 行で出力せよ．

### 制約 - $ 2\ \leq\ N\ \leq\ 500\,000 $． - $ 1\ \leq\ A_i\ \leq\ N $ ($ 1\ \leq\ i\ \leq\ N $)． - $ 1\ \leq\ B_i\ \leq\ N $ ($ 1\ \leq\ i\ \leq\ N $)． - $ A_i\ \neq\ B_i $ ($ 1\ \leq\ i\ \leq\ N $)． - どの都市からどの都市へも，いくつかの道を使って移動できる． ### 小課題 1. ($ 5 $ 点) $ N\ \leq\ 400 $． 2. ($ 5 $ 点) $ N\ \leq\ 4\,000 $． 3. ($ 30 $ 点) $ (A_1,\ B_1)\ =\ (A_2,\ B_2)\ =\ (1,\ 2) $，$ A_i\ \neq\ 1 $ ($ 3\ \leq\ i\ \leq\ N $)，$ B_i\ \neq\ 1 $ ($ 3\ \leq\ i\ \leq\ N $)． 4. ($ 60 $ 点) 追加の制約はない． ### Sample Explanation 1 \- 都市 $ 1 $ と都市 $ 2 $ の距離は $ 1 $ - 都市 $ 1 $ と都市 $ 3 $ の距離は $ 1 $ - 都市 $ 1 $ と都市 $ 4 $ の距離は $ 1 $ - 都市 $ 2 $ と都市 $ 3 $ の距離は $ 1 $ - 都市 $ 2 $ と都市 $ 4 $ の距離は $ 2 $ - 都市 $ 3 $ と都市 $ 4 $ の距離は $ 2 $ であるから，距離の $ 2 $ 乗の総和は $ 1^2\ +\ 1^2\ +\ 1^2\ +\ 1^2\ +\ 2^2\ +\ 2^2\ =\ 12 $ である．