406565: GYM102441 G Sum of Distances in Cactus

Memory Limit:0 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

G. Sum of Distances in Cactustime limit per test1.0 smemory limit per test512 MBinputstandard inputoutputstandard output

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.

Input

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$$$ $$$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$$$$$$

Output

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

ExamplesInput
3 3
1 2
2 3
3 1
Output
3
Input
7 8
2 1
3 1
5 1
3 2
4 3
5 7
6 3
4 6
Output
42

加入题单

上一题 下一题 算法标签: