\textit{А у Вашей дипломной есть практическое применение?} _____________________________________________________ Популярный вопрос \textbf{Легенда} Мальчик Серёжа уже почти закончил работу над дипломной работой. Тема диплома с декабря не изменилась, это всё ещё "Dynamic 2-Edge-Connectivity Problem". Алгоритм уже придуман, протестирован, доказана оценка \textbf{O(K log K)}... Осталось только написать главу про "практическое применение". Ну какое может быть практическое применение у задачи "Dynamic 2-Edge-Connectivity Problem"? Вопрос непростой. Он оказался чуть ли не сложнее исходной задачи. Но диплом нужно защитить, так что нужно срочно что-то делать. Итак, первое практическое применение: можно предложить на соренование задачу на эту тему! \textbf{Задача} Дан неориентированный граф из не более чем \textbf{10^5} вершин. Изначально граф не содержит рёбер. Вам нужно обрабатывать запросы вида \textbf{ADD x y} и \textbf{DEL x y} - добавить или удалить ребро из \textbf{x} в \textbf{y}. В каждый момент времени нужно знать, \textit{\textbf{сколько в графе мостов}}. Кратных рёбер и петель ни в какой момент времени нет. Если поступает команда "удалить ребро", оно в графе точно присутствует. \textbf{Решение задачи} Диплом на то и диплом, что за \textbf{5} часов его так просто не напишешь. Поэтому Вам даны целых \textbf{5} подсказок: \begin{enumerate} \item Добавить ребро и удалить ребро - сделать ребро "живым" на некотором отрезке времени. \item Используйте метод "Разделяй и Властвуй". \item Сжимайте компоненты двусвязности. \item Даже когда компоненты двусвязности уже сжаты, если запросов мало, граф всё ещё можно сильно уменьшить. \item Существует решение за \textbf{O(K log K)}. \end{enumerate} \InputFile В первой строке записаны целые числа \textbf{N} и \textbf{K}: количество вершин и количество запросов, соответственно. \textbf{1} ≤ \textbf{N}≤ \textbf{10^5}, \textbf{1} ≤ \textbf{K} ≤ \textbf{10^5}. В следующих \textbf{K} строках по одному в строке записаны запросы. Каждый запрос начинается словом "\textbf{ADD}" или "\textbf{DEL}" для запроса на добавление или удаление ребра, соответственно. После этого слова два целых числа \textbf{a} и \textbf{b}, задающих ребро. \textbf{1} ≤ \textbf{a}, \textbf{b} ≤ \textbf{N}, \textbf{a} ≠ \textbf{b}. \OutputFile После каждого запроса нужно вывести одно число - сколько в текущем графе мостов.