28614번 - Распределенная Матрица 다국어

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

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

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

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

• <<! $x_i$ $y_i$>> --- узел $y_i$ подключается к узлу $x_i$ и начинает получать энергию от него;
• <<- $x_i$>> --- узел $x_i$ отказывает и перестает проводить энергию;
• <<+ $x_i$>> --- ранее отказавший узел $x_i$ восстанавливается и продолжает проводить энергию;
• <<? $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$.

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

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