문제

You are given a connected undirected unweighted graph. The distance $d(u, v)$ between two vertices $u$ and $v$ is defined as the number of edges in the shortest path between them. Find the sum of $d(u, v)$ over all unordered pairs $(u, v)$.

입력

The first line of the input contains two integers $n$ and $m$ ($2 \le n \le 10^5$; $n - 1 \le m \le n + 42$) — the number of vertices and the number of edges in the graph respectively. The vertices are numbered from 1 to $n$.

Each of the following $m$ lines contains two integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le n$; $x_i \ne y_i$) — the endpoints of the $i$-th edge.

There is at most one edge between every pair of vertices.

출력

Output a single integer — the sum of the distances between all unordered pairs of vertices in the graph.

예제 입력 1

4 4
1 2
2 3
3 1
3 4

예제 출력 1

8

예제 입력 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

노트

In the first example the distance between four pairs of vertices connected by an edge is equal to 1 and $d(1, 4) = d(2, 4) = 2$.