Распределенная Матрица

В условиях нехватки энергии Матрица была модифицирована, чтобы расходовать как можно меньше энергетических ресурсов. Всего есть $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$.