60010 통행료 Gold III

문제

KOI 도시는 N개 건물과 M개의 양방향 도로로 이루어져 있다. 처음에는 모든 도로가 무료이지만, M일에 걸쳐 각 도로에 1원의 통행료가 부과된다.

i번째 날에 i번 도로의 통행료가 1원으로 변경된다. 두 건물 a, b 사이의 최소 이동 비용 f(a,b)는 해당 경로의 최소 총 통행료이다 (a=b일 때 0).

도로망의 총 비용은 모든 건물 쌍의 최소 이동 비용의 합이다.

각 날 이후의 도로망 총 비용을 구하시오.

입력

첫째 줄에 N, M이 주어진다. (2 ≤ N ≤ 500, N-1 ≤ M ≤ N(N-1)/2)

다음 M개의 줄에 i번 도로가 연결하는 두 건물 u_i, v_i가 주어진다. 임의의 두 건물 사이를 오갈 수 있다.

출력

M개의 줄을 출력한다. i번째 줄에는 i번째 날 이후의 도로망 총 비용을 출력한다.

4 4
1 2
2 3
3 1
3 4

0
6
10
16