З'єднання та роз'єднання#4140
Ви коли-небудь чули про обхід в глибину? Наприклад, використовуючи цей алгоритм, ви можете перевірити, чи є граф зв'язним, за час . Ви можете навіть порахувати кількість компонент зв'язності за цей же час.
А ви коли-небудь чули про систему множин, які не перетинаються? Використовуючи цю структуру, ви можете швидко опрацьовувати запити "Додати ребро в граф" та "Порахувати кількість компонент зв'язності у графі".
А ви коли-небудь чули про динамічну задачу зв'язності? У цій задачі вам потрібно опрацьовувати три типи запитів:
Додати ребро в граф.
Видалити ребро з графа.
Порахувати кількість компонент зв'язності у графі.
Спочатку граф порожній.
У першому рядку знаходяться два цілих числа та — кількість вершин та кількість запитів відповідно (1 \leq N \leq 300000, 0 \leq K \leq 300000). Наступні рядків містять запити, по одному у рядку. Є три типи запитів:
+ : Додати ребро між вершинами та . Гарантується, що такого ребра немає.
- : Видалити ребро між та . Гарантується, що таке ребро є.
?: Порахувати кількість компонент зв'язності у графі.
Вершини пронумеровано цілими числами від до . У всіх запитах u \neq v. Граф вважається неорієнтованим.
Для кожного запиту типу "?", виведіть кількість компонент зв'язності у момент запиту.
Приклад 1