Sum of Distances in Cactus

Time limit1sMemory limit256 MB

Summary

Given a connected cactus graph with n vertices and m edges, compute the sum of shortest-path distances over all unordered vertex pairs.

Level: Medium7 of 10
Topics: Dynamic programming, Graph, DFS
Solved: No attempts yet

Problem

Find the sum of the distances between all pairs of vertices in a cactus graph. A cactus graph is a graph in which every edge belongs to at most one simple cycle. The distance between two vertices is the number of edges on the shortest path connecting them.

Input

The first line contains two integers $n$ and $m$ , the number of vertices and the number of edges in the cactus.

Each of the following $m$ lines contains two integers $u_i$ and $v_i$ , the labels of the vertices joined by an edge.

Output

Print a single line containing the sum of the distances between all pairs of vertices.

Constraints

$1 \le n \le 10^5$
$n - 1 \le m \le 2 \times n$
$1 \le u_i, v_i \le n$

The graph is connected and has no self-loops or multiple edges.

Examples2

Example 1
Input
```
3 3
1 2
2 3
3 1
```
Expected output
```
3
```
Example 2
Input
```
7 8
2 1
3 1
5 1
3 2
4 3
5 7
6 3
4 6
```
Expected output
```
42
```