Distance Sum

Time limit4sMemory limit512 MB

Summary

Given a connected undirected unweighted graph with at most n+42 edges, compute the sum of shortest-path distances over all unordered vertex pairs.

Level: Hard8 of 10
Topics: Graph, BFS, Tree, Implementation
Solved: No attempts yet

Problem

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

Input

The first line 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. 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

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

Hint

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

Examples2

Example 1
Input
```
4 4
1 2
2 3
3 1
3 4
```
Expected output
```
8
```

Example 2

Input

Expected output