Распределенная Матрица
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В условиях нехватки энергии Матрица была модифицирована, чтобы расходовать как можно меньше энергетических ресурсов. Всего есть $$$n$$$ узлов Матрицы с уникальными номерами от $$$1$$$ до $$$n$$$. Изначально энергия есть только в генераторе, который является узлом с номером $$$1$$$.

Требующие энергии узлы постепенно подключаются к уже запитанным узлам, и начинают получать энергию от них, образуя сеть питания в виде дерева. Некоторые узлы могут отказывать и восстанавливаться спустя время после отказа. Уже подключенный к сети узел никогда не переподключается к другим узлам, даже если какой-то из косвенно питающих его узлов отказал.

Ненадежностью узла называется время, прошедшее с момента его последнего восстановления (либо с момента подключения этого узла к сети, если он еще не отказывал). Временем подключения генератора считается момент времени $$$0$$$.

Требуется обработать $$$m$$$ событий. Событие номер $$$i$$$ происходит ровно спустя $$$i$$$ секунд от начала и может быть одного из следующих видов:

  1. «! $$$x_i$$$ $$$y_i$$$» — узел $$$y_i$$$ подключается к узлу $$$x_i$$$ и начинает получать энергию от него;
  2. «- $$$x_i$$$» — узел $$$x_i$$$ отказывает и перестает проводить энергию;
  3. «+ $$$x_i$$$» — ранее отказавший узел $$$x_i$$$ восстанавливается и продолжает проводить энергию;
  4. «? $$$x_i$$$ $$$y_i$$$» — требуется выяснить, насколько надежна пара узлов $$$x_i$$$ и $$$y_i$$$.

Для ответа на запрос последнего типа требуется проверить, получают ли энергию оба узла $$$x_i$$$ и $$$y_i$$$. Узел получает энергию, если сам подключен к сети, и все узлы на пути от генератора до него включительно находятся в исправном состоянии (не отказали). Если оба узла $$$x_i$$$ и $$$y_i$$$ получают энергию, требуется вывести суммарную ненадежность всех узлов, от которых зависит работа хотя бы одного из узлов $$$x_i$$$ или $$$y_i$$$ (то есть узлов, расположенных на путях от них до генератора).

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

В первой строке ввода через пробел даны два целых числа $$$n$$$ и $$$m$$$ — общее количество узлов, которым требуется питание, и количество событий, которые надо обработать ($$$2 \leqslant n, m \leqslant 2 \cdot 10^5$$$).

В $$$i$$$-й из следующих $$$m$$$ строк дано описание $$$i$$$-го запроса (который происходит в момент времени $$$i$$$). Описание формата запросов дано в условии. За символом, обозначающим тип запроса, в зависимости от этого типа, следует либо одно целое число $$$x_i$$$, либо два целых числа $$$x_i$$$ и $$$y_i$$$, разделенные пробелом — номера задействованных в запросе узлов ($$$1 \leqslant x_i, y_i \leqslant n$$$; $$$x_i \neq y_i$$$).

Гарантируется, что в запросе первого типа узел $$$x_i$$$ уже подключен к сети, а $$$y_i$$$ — нет. Также для запросов второго и третьего типа гарантируется, что узел $$$x_i$$$ отказывает только если был до этого исправен, и наоборот, восстанавливается только после соответствующего отказа.

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

После каждого запроса четвертого типа следует в отдельной строке вывести ответ на этот запрос. Если хотя бы один из узлов $$$x_i$$$ и $$$y_i$$$ не получает энергию, следует вывести «-1» (без кавычек). Если же оба узла получают энергию, следует вывести целое число, равное сумме ненадежностей всех узлов, лежащих на путях от генератора до $$$x_i$$$ и $$$y_i$$$.

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты из условия, а также тесты для этой подзадачи и необходимых подзадач успешно пройдены.

|c|c|}

Подзадача

Баллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
112полная
2141полная
3181полная
4243полная
5321 – 4первая ошибка

Примеры

Входные данные
3 7
! 1 2
! 1 3
? 2 3
- 3
? 2 3
+ 3
? 2 3
Выходные данные
6
-1
14
Входные данные
3 7
! 1 2
! 2 3
? 1 3
- 2
? 1 3
+ 2
? 1 3
Выходные данные
6
-1
13

Примечание

В первом примере отказ третьего узла, очевидно, влечет ответ «-1» на второй запрос «? 2 3». Ответ на первый запрос равен $$$6$$$, так как с момента подключения к сети генератора, второго узла и третьего, прошли $$$3$$$, $$$2$$$ и $$$1$$$ секунда, соответственно. В момент третьего запроса с момента подключения генератора и второго узла прошло $$$7$$$ и $$$6$$$ секунд, соответственно, тогда как третий узел вернулся в строй ровно $$$1$$$ секунду назад, что дает ответ $$$14$$$.

Во втором примере отказ второго узла аналогично влечет ответ «-1» на второй запрос. Ответ на первый запрос вычисляется так же, как и в первом примере, а на третий — как $$$7 + 1 + 5 = 13$$$.