통행료 timer 1s memory 1024MB

KOI 도시는 1번 건물부터 N번 건물까지 N개의 건물로 이루어져 있으며,
1번 도로부터 M번 도로까지 M개의 양방향 도로가 각 건물을 연결하고 있다.

각 도로는 서로 다른 두 건물을 연결하며, 이 중 i번 도로는 u_i​번 건물과 v_i​번 건물을 양방향으로 연결한다.

이때, 임의의 두 건물 사이를 도로들을 이용해 오갈 수 있다.

원래 KOI 도시의 각 도로는 무료로 이용할 수 있었다.

즉, 모든 도로의 통행료는 0원이었다.

그러나, KOI 도시의 시장인 정올이는 KOI 도시의 재정난을 극복하기 위해, M일에 걸쳐 각 도로에 통행료를 부과하려고 한다.

구체적으로, 정올이는 i번째 날에 i번 도로의 통행료를 1원으로 변경한다. 이에 따라, M일이 모두 지나면 모든 도로의 통행료는 1원이 될 것이다.

a번 건물과 b번 건물 사이의 최소 이동 비용을 a번 건물에서 b번 건물로 이동하기 위해 필요한 총 통행료의 최솟값으로 정의하고, f(a,b)로 표기하자.

a=b라면 f(a,b)=0이다.

도로망의 총 비용은, 가능한 모든 두 건물의 쌍 사이의 최소 이동 비용의 합으로 정의한다.

즉, 모든 1≤a,b≤N인 자연수 a와 b에 대해 f(a,b)의 값을 계산한 후 이를 모두 합친 값이 도로망의 총 비용이다.

이를 수학 기호로 표기하면, 도로망의 총 비용은 ∑_{a=1}^N∑_{b=1}^Nf(a,b) 가 된다.

정올이는 통행료 변화가 시민들에게 어떤 영향을 줄지 분석하려고 한다.

당신은 정올이를 도와, i번째 날이 끝난 이후 도로망의 총 비용을 계산해야 한다.

제약 조건

• 주어지는 모든 수는 정수이다.

• 2≤N≤500

• N−1≤M≤\frac{N(N−1)}{2}

• 1≤i≤M에 대해서, u_i≠v_i​를 만족한다.

• 1≤i≤M에 대해서, 1≤u_i,v_i≤N을 만족한다.

• 임의의 서로 다른 두 건물을 잇는 도로는 최대 하나이다.

• 임의의 두 건물 사이를 도로들을 이용해 오갈 수 있다.