D. Мосты: последняя битва
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
bridges3.in
вывод
bridges3.out
А у вашей дипломной работы есть практическое применение?
Популярный вопрос

Мальчик Серёжа уже почти закончил работу над дипломной работой. Тема диплома с декабря не изменилась, это всё ещё «Dynamic 2-Edge-Connectivity Problem». Алгоритм уже придуман, протестирован, доказана оценка ... Осталось только написать главу про «практическое применение».

Ну какое может быть практическое применение у задачи «Dynamic 2-Edge-Connectivity Problem»? Вопрос непростой. Он оказался чуть ли не сложнее исходной задачи. Но диплом нужно скоро защитить, так что срочно нужно что-то делать.

Итак, первое практическое применение: можно предложить на соревнование задачу на эту тему!

Дан неориентированный граф из не более чем 105 вершин. Изначально граф не содержит рёбер. Вам нужно обрабатывать запросы вида ADD x y и DEL x y — добавить или удалить ребро из x в y.

В каждый момент времени нужно знать, сколько в графе мостов.

Кратных рёбер и петель ни в какой момент времени нет.

Если поступает команда «удалить ребро», оно в графе точно присутствует.

Диплом на то и диплом, что за 5 часов его так просто не напишешь. Поэтому вам даны целых 5 подсказок.

  1. Добавить ребро и удалить ребро — сделать ребро «живым» на некотором отрезке времени.
  2. Используйте метод «Разделяй и Властвуй».
  3. Сжимайте компоненты двусвязности.
  4. Даже когда компоненты двусвязности уже сжаты, если запросов мало, граф всё ещё можно сильно уменьшить.
  5. Cуществует решение за .
Входные данные

В первой строке записаны целые числа N и K: количество вершин и количество запросов, соответственно. 1 ≤ N ≤ 105, 1 ≤ K ≤ 105.

В следующих K строках по одному в строке записаны запросы. Каждый запрос начинается словом «ADD» или «DEL» для запроса на добавление или удаление ребра, соответственно. После этого слова записаны два целых числа a и b, задающих ребро. 1 ≤ a, b ≤ N, a ≠ b.

Выходные данные

После каждого запроса нужно вывести одно число — сколько в текущем графе мостов.

Примеры
Входные данные
4 8
ADD 1 2
ADD 2 3
ADD 1 3
DEL 2 3
DEL 1 2
ADD 2 4
ADD 1 4
ADD 2 3
Выходные данные
1
2
0
2
1
2
3
0