406565: GYM102441 G Sum of Distances in Cactus
Description
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 vertices is calculated as the number of edges in the shortest path connecting a given pair of vertices.
InputFirst 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$$$ $$$v_i$$$ — the numeric labels of vertices connected by an edge.
It is guaranteed that the graph is connected and does not have self-loops and multiple edges.
$$$$$$ 1 \le n \le 10^5$$$$$$ $$$$$$ n - 1 \le m \le 2 \times n$$$$$$ $$$$$$ 1 \le u_i, v_i \le n$$$$$$
OutputOutput a single line containing the sum of the distances between all pairs of vertices.
ExamplesInput3 3 1 2 2 3 3 1Output
3Input
7 8 2 1 3 1 5 1 3 2 4 3 5 7 6 3 4 6Output
42