给定一个连通的无向无权图。两个顶点 $u$ 和 $v$ 之间的距离 $d(u, v)$ 定义为它们之间最短路径上的边数。求所有无序顶点对 $(u, v)$ 的距离之和。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 10^5$; $n-1 \le m \le n+42$)，分别表示图的顶点数和边数。顶点编号从 $1$ 到 $n$。

接下来的 $m$ 行，每行包含两个整数 $x_i$ 和 $y_i$ ($1 \le x_i, y_i \le n; x_i \neq y_i$)，表示第 $i$ 条边的两个端点。

任意两个顶点之间最多只有一条边。

输出格式

输出一个整数，表示图中所有无序顶点对之间的距离之和。

样例

输入 1

4 4
1 2
2 3
3 1
3 4

输出 1

8

说明

在第一个样例中，四个由边直接相连的顶点对之间的距离为 $1$，且 $d(1, 4) = d(2, 4) = 2$。

输入 2

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

输出 2

34

说明