Những Cây Cầu Sụp Dần · canuc80k2322

Có $N$ đỉnh và $M$ cạnh vô hướng; đồ thị ban đầu liên thông. Các cạnh sẽ bị xóa lần lượt đúng theo thứ tự chúng xuất hiện trong input.

Sau mỗi lần xóa, gọi một cặp đỉnh ${u, v}$ là bị chia cách nếu không còn đường đi giữa chúng. Mỗi cặp không thứ tự chỉ được đếm một lần.

Hãy tính số cặp bị chia cách ngay sau từng lần xóa cạnh.

Input

Dòng đầu chứa hai số nguyên $N$ và $M$ .
Mỗi trong $M$ dòng tiếp theo chứa hai số nguyên $A_{i}$ và $B_{i}$ .

Output

In $M$ dòng. Dòng thứ $i$ chứa số cặp bị chia cách ngay sau khi xóa cạnh thứ $i$ .

Constraints

$2 \leq N \leq 1 0^{5}$ .
$1 \leq M \leq 1 0^{5}$ .
$1 \leq A_{i} < B_{i} \leq N$ .
Các cặp ( $A_{i}, B_{i}$ ) đôi một khác nhau.
Đồ thị ban đầu liên thông.
Kết quả có thể vượt giới hạn số nguyên $32$ bit.

Scoring

Subtask $1$ ( $50%$ số điểm): $N, M \leq 1000$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

Output

Giải thích: Hai lần xóa đầu tiên lần lượt giữ mạng liên thông rồi cô lập đỉnh $2$ , nên kết quả là $0$ và $4$ . Sau đó các thành phần tiếp tục tách, cho $7, 7, 9, 10$ ; khi mọi cầu đã mất, cả $10$ cặp đỉnh đều rời nhau.

Phân tích: Xóa cạnh có thể tách thành phần nên không thể xử lý trực tiếp bằng DSU. Đảo thứ tự, ta bắt đầu từ đồ thị rỗng và thêm cạnh từ cuối về đầu. Khi nối hai thành phần có kích thước a và b, đúng a·b cặp đỉnh từ trạng thái chia cách trở thành liên thông.
Thuật toán: Khởi tạo số cặp chia cách bằng N(N-1)/2. Duyệt cạnh từ M về 1: trước khi thêm cạnh i, lưu giá trị hiện tại làm đáp án sau khi cạnh đó đã bị xóa; nếu hai đầu thuộc hai thành phần khác nhau, trừ tích kích thước rồi hợp chúng.
Chứng minh: Ở bước ngược ứng với cạnh i, DSU chứa đúng các cạnh có chỉ số lớn hơn i, tức đúng trạng thái sau khi các cạnh 1..i đã bị xóa. Thêm một cạnh giữa hai thành phần chỉ thay đổi các cặp có một đầu ở mỗi thành phần, tổng cộng a·b; nếu hai đầu đã liên thông thì không cặp nào đổi. Do đó mọi giá trị lưu là chính xác.
Độ phức tạp: Thời gian O((N+M) α(N)), bộ nhớ O(N+M).