시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 256 MB111100.000%

문제

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.

입력

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. 

출력

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

제한

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

예제 입력 1

3 3
1 2
2 3
3 1

예제 출력 1

3

예제 입력 2

7 8
2 1
3 1
5 1
3 2
4 3
5 7
6 3
4 6

예제 출력 2

42