В условиях нехватки энергии Матрица была модифицирована, чтобы расходовать как можно меньше энергетических ресурсов. Всего есть $$$n$$$ узлов Матрицы с уникальными номерами от $$$1$$$ до $$$n$$$. Изначально энергия есть только в генераторе, который является узлом с номером $$$1$$$.
Требующие энергии узлы постепенно подключаются к уже запитанным узлам, и начинают получать энергию от них, образуя сеть питания в виде дерева. Некоторые узлы могут отказывать и восстанавливаться спустя время после отказа. Уже подключенный к сети узел никогда не переподключается к другим узлам, даже если какой-то из косвенно питающих его узлов отказал.
Ненадежностью узла называется время, прошедшее с момента его последнего восстановления (либо с момента подключения этого узла к сети, если он еще не отказывал). Временем подключения генератора считается момент времени $$$0$$$.
Требуется обработать $$$m$$$ событий. Событие номер $$$i$$$ происходит ровно спустя $$$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|} Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
1 | 12 | полная | ||
2 | 14 | 1 | полная | |
3 | 18 | 1 | полная | |
4 | 24 | 3 | полная | |
5 | 32 | 1 – 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$$$.