题目背景

翻译自 NERC 2018 D 题。

题目描述

给你一个 $n$ 个顶点 $m$ 条边的连通无向图，定义 $u$ 与 $v$ 的距离 $d(u, v)$ 为从 $u$ 到 $v$ 最短路径上经过的边数。

现在请你求出 $\sum_{u=1}^n \sum_{v=u+1}^n d(u,v)$。

输入格式

第一行给定两个整数 $n(1 \leq n \leq 10^5)$，$m(n - 1 \leq m \leq n + 42)$，分别表示点数和边数。

接下来 $m$ 行，每行 $2$ 个整数 $x_i$ 和 $y_i(1 \leq x_i,y_i \leq n, x_i \neq y_i)$，表示 $x_i$ 和 $y_i$ 之间有一条边。

保证没有重边和自环。

输出格式

输出 $\sum_{u=1}^n \sum_{v=u+1}^n d(u,v)$。

4 4
1 2
2 3
3 1
3 4

8

7 10
1 2
2 6
5 3
5 4
5 7
3 6
1 7
5 1
7 4
4 1

34

提示

对于所有数据保证 $1 \leq n \leq 10^5$，$n-1 \leq m \leq n + 42$，$1 \leq x_i, y_i \leq n$ 且 $x_i \neq y_i$。

样例一的图是：

其中 $d(1,2) = 1$，$d(1,3) = 1$，$d(1,4) = 2$，$d(2,3) = 1$，$d(2,3) = 2$，$d(3,4) = 1$，总和为 $1 + 1 + 2 + 1 + 2 + 1 = 8$。

样例二为：