[R22G]双路径极值差 - 代码源竞赛平台

时空限制

5S/1024M

题目描述

给定一张包含 $n$ 个顶点和 $m$ 条边的无向连通图。

函数 $f(i, j)$ 按照如下方式定义：考虑从顶点 $i$ 到顶点 $j$ 的任意两条（可重合的）简单路径 $path_1$ 和 $path_2$。令：

$Max$ 表示 $path_1$ 上经过顶点编号的最大值，

$Min$ 表示 $path_2$ 上经过顶点编号的最小值。

$f(i, j)$ 定义为所有可能的路径对 $(path_1, path_2)$ 中，差值 $Max - Min$ 的最小值。

请你输出：$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n} f(i,j) \times \lfloor \frac{i}{j} \rfloor$。

格式

输入格式

第一行包含两个整数 $n$ 和 $m$，表示图中点的数量和边的数量。

接下来 $m$ 行，每行包含两个整数 $u,v$，表示图中有 $u,v$ 这条边。

输出格式

输出一个整数，表示答案。

样例

样例输入 #1

2 1
1 2

样例输出 #1

2

样例输入 #2

5 5 
1 2 
2 3
1 4
2 5
3 5 

样例输出 #2

62

数据规模

对于 $32\%$ 的数据，$1 \leq n \leq 5000$。

对于 $100\%$ 的数据，$1 \leq n \leq 4 \times 10^4$，$1 \leq m \leq 2 \times 10^5$，$1 \leq u , v \leq n$。