Có \(N\) hòn đảo và \(M\) cây cầu.

Cây cầu thứ \(i\) kết nối hai hòn đảo \(A_i\) và \(B_i\) theo hai chiều.

Ban đầu, chúng ta có thể di chuyển giữa bất kỳ hai hòn đảo nào sử dụng một số cây cầu này.

Tuy nhiên, kết quả của một cuộc khảo sát cho thấy những cây cầu này sẽ sụp đổ theo thứ tự từ cây cầu đầu tiên đến cây cầu thứ \(M\).

Hãy xác định sự bất tiện là số lượng các cặp hòn đảo \((a, b)\) (với \(a < b\)) mà chúng ta không thể di chuyển giữa hòn đảo \(a\) và \(b\) sử dụng các cây cầu còn lại.

Đối với mỗi \(i (1 \leq i \leq M)\), tìm sự bất tiện ngay sau khi cây cầu thứ \(i\) sụp đổ.

Ràng buộc

• Tất cả giá trị đầu vào là số nguyên.
• \(2 \leq N \leq 10^5\)
• \(1 \leq M \leq 10^5\)
• \(1 \leq A_i < B_i \leq N\)
• Mọi cặp \((A_i, B_i)\) đều là duy nhất.
• Sự bất tiện ban đầu là \(0\).

INPUT FORMAT

• Đầu vào được cung cấp từ Standard Input theo định dạng sau:

  N M
  A_1 B_1
  A_2 B_2
  ...
  A_M B_M

OUTPUT FORMAT

• Theo thứ tự \(i=1,2,...,M\), in ra sự bất tiện ngay sau khi cây cầu thứ \(i\) sụp đổ. Lưu ý rằng kết quả có thể không vừa với kiểu số nguyên 32 bit.

Ví dụ:

Input

4 5
1 2
3 4
1 3
2 3
1 4

Output

0
0
4
5
6

Ví dụ, khi ba cây cầu đầu tiên đã sụp đổ, sự bất tiện là \(4\) vì chúng ta không thể di chuyển giữa các cặp (1,2), (1,3), (2,4) và (3,4).

Input

6 5
2 3
1 2
5 6
3 4
4 5

Output

8
9
12
14
15

Giải thích ví dụ mẫu

Ví dụ 1:

• Input: 4 5, 1 2, 3 4, 1 3, 2 3, 1 4
• Giải thích: Khi cầu đầu tiên sụp đổ, không có bất tiện nào; nhưng khi cầu thứ ba sụp đổ, có 4 cặp đảo không thể di chuyển.

Ví dụ 2:

• Input: 6 5, 2 3, 1 2, 5 6, 3 4, 4 5
• Giải thích: Khi cầu đầu tiên sụp đổ, bất tiện tăng lên dần, cuối cùng là 15 cặp không thể di chuyển sau khi tất cả các cầu đã sụp đổ.
  

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House