Kết Nối Động

Cho một đồ thị vô hướng có $N$ đỉnh với $M$ cạnh ban đầu. Sau đó có $K$ thao tác, mỗi thao tác là một trong hai loại:

• Thêm cạnh: Thêm cạnh $(u,v)$ vào đồ thị.
• Xóa cạnh: Xóa cạnh $(u,v)$ khỏi đồ thị.

Sau mỗi trạng thái (trạng thái ban đầu và sau mỗi thao tác), hãy in số thành phần liên thông của đồ thị.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên $N$, $M$, $K$ — số đỉnh, số cạnh ban đầu, và số thao tác.

• $M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u$, $v$ — mô tả một cạnh ban đầu.

• $K$ dòng tiếp theo, mỗi dòng mô tả một thao tác:

• 1 u v — thêm cạnh $(u,v)$.
• 2 u v — xóa cạnh $(u,v)$ (đảm bảo cạnh này đang tồn tại trong đồ thị).

Dữ liệu ra

In $K+1$ số nguyên trên một dòng, cách nhau bởi dấu cách: số thành phần liên thông sau trạng thái ban đầu và sau mỗi thao tác.

Ràng buộc

• $1\le N\le {10}^5$
• $0\le M\le {10}^5$
• $1\le K\le {10}^5$
• $1\le u,v\le N$, $u\ne v$
• Có thể có nhiều cạnh song song (multi-edge) tại một thời điểm.

Ví dụ

Ghi chú

Đồ thị có thể có nhiều cạnh song song giữa cùng hai đỉnh. Khi xóa cạnh, chỉ xóa một bản sao.