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 翻译