60010 통행료 Gold III

문제

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)$의 값을 계산한 후 이를 모두 합친 값이 도로망의 총 비용이다. 이를 수학 기호로 표기하면, 도로망의 총 비용은 $\sum_{a=1}^{N}\sum_{b=1}^{N}f(a, b)$가 된다.

정올이는 통행료 변화가 시민들에게 어떤 영향을 줄지 분석하려고 한다. 당신은 정올이를 도와, $i$번째 날이 끝난 이후 도로망의 총 비용을 계산해야 한다.

입력

첫 번째 줄에 $N$과 $M$이 공백으로 구분되어 주어진다.

다음 $M$개의 줄에는 도로의 정보가 주어진다. 이 중 $i$ ($1 ≤ i ≤ M$)번째 줄에는 두 정수 $u_i$, $v_i$가 공백으로 구분되어 주어진다.

출력

총 $M$개의 줄을 출력한다. 이 중 $i$ ($1 ≤ i ≤ M$) 번째 줄에는, $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$을 만족한다.
• 임의의 서로 다른 두 건물을 잇는 도로는 최대 하나이다.
• 임의의 두 건물 사이를 도로들을 이용해 오갈 수 있다.

서브태스크

번호	배점	제한
1	10	$N ≤ 5$.
2	15	$N ≤ 50$.
3	30	$M ≤ 500$.
4	45	추가 제약 조건 없음.

힌트

예제 1 설명

$4$일이 지난 뒤 각 건물 간의 최소 이동 비용은 다음과 같은 표로 나타낼 수 있다.

	$1$번 건물	$2$번 건물	$3$번 건물	$4$번 건물
$1$번 건물	$0$	$1$	$1$	$2$
$2$번 건물	$1$	$0$	$1$	$2$
$3번$ 건물	$1$	$1$	$0$	$1$
$4$번 건물	$2$	$2$	$1$	$0$

따라서, $4$번째 날이 끝난 이후 도로망의 총 비용은 $0 + 1 + 1 + 2 + 1 + 0 + 1 + 2 + 1 + 1 + 0 + 1 + 2 + 2 + 1 + 0 = 16$이 된다.

4 4
1 2
2 3
3 1
3 4

0
6
10
16

4 4
2 3
3 1
3 4
1 2

0
8
14
16