Problem Description

In Giga Country, there are $ N $ cities numbered $1, 2, 3, \dots, N$.

Some cities are connected by roads. Specifically, there are $ M $ roads, and the $ i $-th road connects cities $ a_i $ and $ b_i $ bidirectionally. Also, by using only some roads, it is possible to travel from any city to any other city.

Here, $ d(i, j) $ is defined as the "distance between cities $ i $ and $ j $," which is the "minimum number of roads used to travel from city $ i $ to city $ j $."

Your task is to find the sum of the distances $ d(x, y) $ for all distinct pairs of cities $ (x, y) $.

Input Format

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

$ N $ $ M $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ : : $ a_M $ $ b_M $

Output Format

Output the sum of the distances $ d(x, y) $ for all pairs of cities $ x, y $.

Sample Input and Output

Sample Input #1

4 3
1 2
2 3
3 4

Sample Output #1

10

Sample Input #2

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

Sample Output #2

6

Sample Input #3

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

Sample Output #3

72

Notes/Hints

Constraints

• $1 \leq N \leq 100,000$
• $1 \leq M \leq 100,000$
• $N - 1 \leq M \leq N + 777$
• $1 \leq a_i, b_i \leq N$
• $a_i \neq b_i$
• For any pair $ (u, v) $, there is at most one road directly connecting cities $ u $ and $ v $.
• It is possible to travel from any city to any other city by following the roads.
• All inputs are integers.

Partial Points

This problem is divided into several sub-tasks, and you are considered to have solved a sub-task if you correctly answer all test cases in that sub-task. The score of your submitted source code will be the sum of the points of the solved sub-tasks.

1. (9 points) $N \leq 100, M \leq 100$
2. (7 points) $N \leq 3,000, M \leq 3,000$
3. (12 points) $ M - N = -1 $
4. (13 points) $ M - N = 0 $
5. (28 points) $M - N \leq 7$. Additionally, for $1 \leq i \leq N-1$, $ a_i = i, b_i = i+1 $.
6. (22 points) $M - N \leq 77$
7. (9 points) No additional constraints.

Note

This problem has a somewhat large input/output size, so it is recommended to use fast input/output methods (e.g., scanf/printf in C++).

Sample Explanation 1

Giga Country has the following road network: In this road network, $ d(1, 2) = 1, d(1, 3) = 2, d(1, 4) = 3, d(2, 3) = 1, d(2, 4) = 2, d(3, 4) = 1 $, so the answer is $ 1 + 2 + 3 + 1 + 2 + 1 = 10 $.

Sample Explanation 2

Giga Country has the following road network: In this road network, all cities can be traveled to with a distance of $ 1 $, so the answer is $ 6 $.

见题面 Input 部分

见题面 Output 部分