시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (추가 시간 없음) | 256 MB | 45 | 6 | 5 | 11.364% |
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.
3 3 1 2 2 3 3 1
3
7 8 2 1 3 1 5 1 3 2 4 3 5 7 6 3 4 6
42