問題

ピーターランドには 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 で割った余りを求めよ．

制約

• 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 点) 追加の制約はない．

入力例 1

4
1 2
2 3
3 1
1 4

出力例 1

12

• 都市 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 である．

入力例 2

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

出力例 2

65

入力例 3

10
7 4
9 7
5 8
8 4
3 7
1 9
10 9
4 1
2 5
6 4

出力例 3

384