Мосты через Нарын


Отправить решение Решать в редакторе

Сложность: 90%
Очки: 100 (частичный балл)
Ограничение по времени: 2.5s
Ограничение по памяти: 512M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Нарын — самая длинная река Кыргызстана. Весной, когда тают ледники, вода поднимается и смывает временные мосты, а летом жители сёл строят их заново.

Вдоль реки расположены n сёл, пронумерованных от 1 до n. Мост соединяет два села, по нему можно ходить в обе стороны; между двумя сёлами может быть несколько мостов. Сначала мостов нет. Районный акимиат ведёт журнал из q событий:

  • + u v — построен новый мост между сёлами u и v;
  • - u v — один из мостов между сёлами u и v смыло (гарантируется, что такой мост есть);
  • ? u v — нужно сообщить, можно ли сейчас дойти из села u в село v по мостам (YES или NO);
  • C — нужно сообщить, на сколько изолированных друг от друга групп разбиты сёла (село, к которому не ведёт ни один мост, — отдельная группа).

Ответьте на все вопросы журнала.

Рисунок

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

В первой строке — два целых числа n и q (1 ≤ n, q ≤ 300 000).

В каждой из следующих q строк — одно событие в описанном формате (1 ≤ u, v ≤ n; в событиях + и - u ≠ v). Мост u v и мост v u — это одно и то же.

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

Для каждого события ? и C выведите ответ в отдельной строке.

Пример 1

Вход:

5 10
+ 1 2
+ 2 3
C
? 1 3
- 2 1
? 1 3
+ 4 5
+ 1 3
C
? 2 1

Выход:

3
YES
NO
2
YES

Пояснение

После первых двух мостов сёла образуют группы {1, 2, 3}, {4}, {5}. Когда мост 1–2 смыло, из села 1 в село 3 пройти нельзя. После постройки мостов 4–5 и 1–3 остаются две группы: {1, 2, 3} и {4, 5}.

Система оценивания

Подзадача Баллы Дополнительные ограничения
1 20 n, q ≤ 1000
2 15 нет событий -
3 65 без дополнительных ограничений

Баллы за подзадачу начисляются, только если пройдены все её тесты.


Комментарии

Еще нет ни одного комментария.