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\)번째 날이 끝난 이후 도로망의 총 비용을 계산해야 한다.

• 주어지는 모든 수는 정수이다.
• \(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\)을 만족한다.
• 임의의 서로 다른 두 건물을 잇는 도로는 최대 하나이다.
• 임의의 두 건물 사이를 도로들을 이용해 오갈 수 있다.

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

총 \(M\)개의 줄을 출력한다. 이 중 \(i\) (\(1 ≤ i ≤ M\)) 번째 줄에는, \(i\)번째 날이 끝난 이후 도로망의 총 비용을 출력한다.

riseoj 작성

출처 올림피아드 > 한국정보올림피아드 > KOI 2025 > 2차 대회 > 초등부 3번