Problem Description

Peterland has $ N $ cities numbered from $ 1 $ to $ N $. There are exactly $ N $ bidirectional roads connecting pairs of cities. The $ i $th ($1 \leq i \leq N$) road connects city $ A_i $ and city $ B_i $. Any city can be reached from any other city using some roads.

The distance between two cities is defined as the minimum number of roads needed to travel from one to the other. There are $\frac{N (N - 1)}{2}$ ways to choose two cities from $ N $ cities. Calculate the sum of the squares of these distances modulo $ 998,244,353 $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ A_1 $ $ B_1 $ $\vdots$ $ A_N $ $ B_N $

Output Format

Output the sum of the squares of the distances modulo $ 998,244,353 $ to the standard output in one line.

Sample Input and Output

Sample Input #1

4
1 2
2 3
3 1
1 4

Sample Output #1

12

Sample Input #2

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

Sample Output #2

65

Sample Input #3

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

Sample Output #3

384

Notes/Hints

Constraints

• $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$).
• Any city can be reached from any other city using some roads.

Subtasks

1. ($ 5 points $) $N \leq 400$.
2. ($ 5 points $) $N \leq 4,000$.
3. ($ 30 points $) $ (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 points $) No additional constraints.

Sample Explanation 1

• The distance between city $ 1 $ and city $ 2 $ is $ 1 $.
• The distance between city $ 1 $ and city $ 3 $ is $ 1 $.
• The distance between city $ 1 $ and city $ 4 $ is $ 1 $.
• The distance between city $ 2 $ and city $ 3 $ is $ 1 $.
• The distance between city $ 2 $ and city $ 4 $ is $ 2 $.
• The distance between city $ 3 $ and city $ 4 $ is $ 2 $.

Therefore, the sum of the squares of the distances is $ 1^2 + 1^2 + 1^2 + 1^2 + 2^2 + 2^2 = 12 $.

见题面 Input 部分

见题面 Output 部分