问题描述

Giga国有 $N$ 个城市，分别以编号 $1, 2, 3, \dots, N$ 进行标记。

一些城市之间通过道路相连。具体来说，有 $M$ 条道路，第 $i$ 条道路连接城市 $a_i$ 和 $b_i$（双向）。通过一些道路，任意两个城市之间都可以到达。

定义 $d(i, j)$ 为城市 $i$ 和 $j$ 之间的距离，即只使用道路从城市 $i$ 到城市 $j$ 所需的最小道路数量。

求所有不同的城市对 $(x, y)$ 的距离 $d(x, y)$ 的总和。

约束条件

• $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$
• 任何 $(u, v)$ 的组合中，直接连接城市 $u$ 和城市 $v$ 的道路最多只有 1 条。
• 任意两个城市之间都可以通过道路到达。
• 输入都是整数

部分得分

此问题分为若干子任务，只有在所有子任务的测试用例中都正确才会被视为“通过该子任务”。
提交的源代码的得分是通过所有通过的子任务得分之和。

1. (9 分) $N \leq 100, M \leq 100$
2. (7 分) $N \leq 3,000, M \leq 3,000$
3. (12 分) 满足 $M - N = -1$。
4. (13 分) 满足 $M - N = 0$。
5. (28 分) 满足 $M - N \leq 7$，并且对于 $1 \leq i \leq N-1$，满足 $a_i = i, b_i = i+1$。
6. (22 分) 满足 $M - N \leq 77$。
7. (9 分) 没有额外的约束。

输入

从标准输入中以以下格式给出输入：

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

输出

请输出所有城市 $x, y$ 之间的距离 $d(x, y)$ 的总和。

注意

由于输入输出规模较大，建议使用快速输入输出（比如 C++ 中的 scanf/printf）来优化程序性能。

输入示例 1

4 3
1 2
2 3
3 4

输出示例 1

10

Giga国的道路网络如下所示：

在这个道路网络中，$d(1, 2) = 1, d(1, 3) = 2, d(1, 4) = 3, d(2, 3) = 1, d(2, 4) = 2, d(3, 4) = 1$，因此答案为 $1+2+3+1+2+1=10$。

输入示例 2

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

输出示例 2

6

Giga国的道路网络如下所示：

在这个道路网络中，任意两个城市之间的距离都是 1，因此答案为 6。

输入示例 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

输出示例 3

72