캑터스 그래프에서의 거리 합

캑터스 그래프에서 모든 정점 쌍 사이 거리의 합을 구하시오. 캑터스 그래프는 모든 간선이 최대 한 개의 단순 사이클에 속하는 그래프이다. 두 정점 사이의 거리는 두 정점을 잇는 최단 경로의 간선 수이다.

첫 줄에 정점의 수 $n$과 간선의 수 $m$이 주어진다.

이어서 $m$개의 줄에 각각 간선으로 연결된 두 정점의 번호 $u_i$와 $v_i$가 주어진다.

모든 정점 쌍 사이 거리의 합을 한 줄에 출력한다.

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

그래프는 연결되어 있으며, 자기 루프와 다중 간선이 없다.