Соединение и разъединение
Вы когда-нибудь слышали про обход в глубину? Например, используя этот алгоритм, вы можете проверить, является ли граф связным, за время O(E). Вы можете даже посчитать количество компонент связности за то же время.
А вы когда-нибудь слышали о системе непересекающихся множеств? Используя эту структуру, вы можете быстро обрабатывать запросы "Добавить ребро в граф" и "Посчитать количество компонент связности в графе".
А вы когда-нибудь слышали о динамической задаче связности? В этой задаче вам надо обрабатывать три типа запросов:
Добавить ребро в граф.
Удалить ребро из графа.
Посчитать количество компонент связности в графе.
Входные данные
Изначально граф пустой.
В первой строке находятся два целых числа N и K - количество вершин и количество запросов соответственно (1 ≤ N ≤ 300000, 0 ≤ K ≤ 300000). Следующие K строк содержат запросы, по одному в строке. Есть три типа запросов:
+ u v: Добавить ребро между вершинами u и v. Гарантируется, что такого ребра нет.
- u v: Удалить ребро между u и v. Гарантируется, что такое ребро есть.
?: Посчитать количество компонент связности в графе.
Вершины пронумерованы целыми числами от 1 до N. Во всех запросах u ≠ v. граф считается неориентированным.
Выходные данные
Для каждого запроса типа "?", выведите количество компонент связности в момент запроса.