AT_gigacode_2019_g.ギガ国の道路事情

在“ギガ国”中有 $N$ 个城市，编号分别为 $1, 2, 3, \dots, N$。

有若干城市通过道路相连。具体来说，有 $M$ 条道路，第 $i$ 条道路连接城市 $a_i$ 和 $b_i$，且为双向道路。此外，通过某些道路，可以从任意一个城市到达任意另一个城市。

这里，$d(i, j)$ 表示“城市 $i$ 和城市 $j$ 之间的距离”，即“仅通过道路从城市 $i$ 到城市 $j$ 时所经过的最少道路数”。

请计算所有不同的 $2$ 个城市对 $(x, y)$ 的距离 $d(x, y)$ 的总和。

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

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

输出所有城市 $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. (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 分) 无额外限制。

注意

本题输入输出数据量较大，建议使用高效的输入输出方式（如 C++ 的 scanf/printf 等）。

样例解释 1

ギガ国的道路网络如下所示。

在该道路网络中，$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

ギガ国的道路网络如下所示。

在该道路网络中，任意两城市间距离均为 $1$，因此答案为 $6$。

由 ChatGPT 4.1 翻译