Мосты через Нарын
Нарын — самая длинная река Кыргызстана. Весной, когда тают ледники, вода поднимается и смывает временные мосты, а летом жители сёл строят их заново.
Вдоль реки расположены 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 | без дополнительных ограничений |
Баллы за подзадачу начисляются, только если пройдены все её тесты.
Комментарии