配点: 100 点
問題文
在千兆国 有 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) 的总和。
制約
- 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 。
- 您可以沿着从任何城市到任何城市的道路。
- 所有输入均为整数
部分点
该问题分为多个子任务,如果您正确回答了该子任务的所有测试用例,则视为您已正确回答了“该子任务”。
提交的源代码的分数是您正确回答的子作业分数的总和。
- (9 点) N \leq 100, M \leq 100
- (7 点) N \leq 3 \ 000, M \leq 3 \ 000
- (12 点) M - N = -1 很满意。
- (13 点) M - N = 0 很满意。
- (28 点) M - N \leq 7 满意。另外, 关于1 \leq i \leq N-1 ,a_i = i, b_i = i+1 很满意。
- (22 点) M - N \leq 77 很满意。
- (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
千兆国拥有以下道路网络。
在这个路网中, 从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
千兆国拥有以下道路网络。
在该路网中,所有城市之间的距离为 你可以用 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