Mạng Lưới Theo Thời Gian · canuc80k7410

Có $n$ trạm được đánh số từ $1$ đến $n$ . Ban đầu chưa có đường nối nào. Bạn phải xử lý lần lượt $m$ thao tác trên một đồ thị vô hướng đơn:

$+ uv$ : thêm đường nối giữa $u$ và $v$ .
$- uv$ : xóa đường nối giữa $u$ và $v$ .
?: in số thành phần liên thông hiện tại.

Trước mỗi thao tác thêm, cạnh tương ứng chưa tồn tại; trước mỗi thao tác xóa, cạnh đó đang tồn tại. Hai đầu mút của một cạnh luôn khác nhau.

Input

Dòng đầu chứa hai số nguyên $n$ và $m$ .
Mỗi trong $m$ dòng tiếp theo mô tả đúng một thao tác theo một trong ba dạng trên.

Output

Với mỗi thao tác ?, in số thành phần liên thông của đồ thị tại thời điểm đó trên một dòng riêng.

Constraints

$1 \leq n \leq 3 \cdot 1 0^{5}$ .
$0 \leq m \leq 3 \cdot 1 0^{5}$ .
$1 \leq u, v \leq n, u \neq = v$ .

Scoring

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

Example

Test 1

Input

6 9
?
+ 1 2
+ 2 3
?
+ 1 3
- 2 3
?
- 1 3
?

Output

Giải thích: Hai cạnh đầu nối $1, 2, 3$ thành một nhóm nên còn $4$ thành phần. Cạnh $1 - 3$ tạo thêm một chu trình; xóa $2 - 3$ vẫn giữ ba đỉnh liên thông, còn xóa tiếp $1 - 3$ tách đỉnh $3$ , làm số thành phần tăng lên $5$ .

Phân tích: Mỗi cạnh tồn tại trên một khoảng thời gian nửa mở [l,r): l là vị trí thao tác thêm, còn r là vị trí xóa hoặc m nếu cạnh không bị xóa. Ta cần đưa cạnh tới đúng mọi thời điểm thuộc khoảng ấy.
Thuật toán: Xây cây đoạn trên các thời điểm 0..m-1. Phân rã mỗi khoảng sống của cạnh thành O(log m) nút cây đoạn. Khi DFS một nút, chụp snapshot của DSU rollback rồi hợp tất cả cạnh lưu tại nút. Ở lá có truy vấn ?, biến components của DSU là đáp án. Sau khi xử lý các con, rollback về snapshot.
Thuật toán: DSU chỉ dùng union-by-size, không path compression. Mỗi lần hợp thành công lưu gốc bị gắn, gốc nhận và kích thước cũ; phép hợp dư thừa lưu sentinel.
Chứng minh: Một cạnh được lưu ở các nút có các đoạn rời nhau hợp đúng bằng khoảng sống của nó. Vì vậy, trên đường từ gốc cây đoạn tới lá thời điểm t, cạnh được áp đúng khi và chỉ khi nó đang tồn tại tại t. DSU ở lá do đó biểu diễn chính xác đồ thị tại thời điểm truy vấn, nên components là đáp án. Rollback khôi phục toàn bộ thay đổi của một nhánh trước khi sang nhánh khác, nên trạng thái không bị rò rỉ.
Độ phức tạp: Mỗi cạnh đi vào O(log m) nút; mỗi union/find mất O(log n) trong trường hợp xấu nhất. Thời gian O(m log m log n), bộ nhớ O(n + m log m).