Problems
Connect and Disconnect
Connect and Disconnect
Знаете ли Вы что-нибудь про DFS, Depth First Search, поиск в глубину?
Например, используя этот метод, можно проверить связность графа за время \textbf{O}(\textbf{E}). Можно даже за тоже самое время посчитать число компонент связности графа.
Знаете ли Вы что-нибудь про DSU, Disjoint Set Union, систему непересекающихся множеств? Используя эту структуру данных, Вы можете обрабатывать запросы вида "Добавить ребро в граф" и "Посчитать число компонент связности графа" быстро. Т.е. оба запроса за \textbf{O}(\textbf{log N}).
А знаете ли Вы что-нибудь про Dynamic Connectivity Problem? В этой задаче, вам нужно уметь быстро обрабатывать \textbf{3} типа запросов:
\begin{enumerate}
\item Добавить ребро в граф.
\item Удалить ребро из графа.
\item Посчитать число компонент связности графа.
\end{enumerate}
\InputFile
Изначально граф пуст.
Первая строка входного файла содержит \textbf{2} числа --- \textbf{N} и \textbf{K} --- число вершин и число запросов (\textbf{1} ≤ \textbf{N} ≤ \textbf{300000}, \textbf{0} ≤ \textbf{K} ≤ \textbf{300000}).
Следующие \textbf{K} содержат запросы, по одному в строке. Есть \textbf{3} типа запросов:
\begin{enumerate}
\item \textbf{+ u v}: добавить ребро между вершинами \textbf{u} и \textbf{v}. Гарантируется, что в момент получения запроса такого ребра в графе нет.
\item \textbf{- u v}: удалить ребро между вершинами \textbf{u} и \textbf{v}. Гарантируется, что в момент получения запроса такое ребро в графе есть.
\item \textbf{?}: посчитать число компонент связности в графе в текущий момент.
\end{enumerate}
Вершины нумеруются от \textbf{1} до \textbf{N}. Нет запросов с \textbf{u} = \textbf{v}. Граф неориентированный.
\OutputFile
Для каждого запроса вида '\textbf{?}' выведите число компонент связности графа в момент времени запроса на отдельной строке.
Input example #1
5 11 ? + 1 2 + 2 3 + 3 4 + 4 5 + 5 1 ? - 2 3 ? - 4 5 ?
Output example #1
5 1 1 2