A. Динамический get_path
ограничение по времени на тест
7 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан лес на $$$n$$$ вершинах, изначально без рёбер.

Также даны $$$q$$$ запросов трёх типов:

  • link $$$u$$$ $$$v$$$ — добавить новое неориентированное ребро между $$$u$$$ и $$$v$$$.
  • cut $$$i$$$ — удалить ребро, которое было добавлено в $$$i$$$-м запросе.
  • get_path $$$u$$$ $$$v$$$ — найти длину пути $$$u \leftrightarrow v$$$.

Гарантируется, что числа $$$i$$$ различны, и граф остаётся лесом.

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

Первая строка содержит два целых числа $$$n$$$ и $$$q$$$ ($$$2 \le n,q \le 2\cdot 10^5$$$) — количество вершин и количество запросов соответственно.

$$$j$$$-я из следующих $$$q$$$ строк описывает запрос в соответствии со следующим принципом:

Сначала даётся одна строка $$$type$$$ ($$$type \in$$$ {link, cut, get_path}) — тип запроса.

Если $$$type$$$ равен link, то следуют два целых числа $$$u,v$$$ ($$$1 \le u,v \le n$$$), что означает, что добавляется новое неориентированное ребро между $$$u$$$ и $$$v$$$.

Если $$$type$$$ равен cut, то следует одно целое число $$$i$$$ ($$$1 \le i \lt j \le q$$$) — индекс запроса, который добавил ребро, которое требуется удалить.

Если $$$type$$$ равен get_path, то следуют два целых числа $$$u,v$$$ ($$$1 \le u,v \le n$$$) — концы запрашиваемого пути.

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

Для каждого из запросов типа get_path выведите длину пути, если он существует; иначе выведите $$$-1$$$.

Пример
Входные данные
9 12
link 1 2
link 2 3
get_path 1 3
cut 2
get_path 1 3
link 8 7
link 8 9
link 2 8
get_path 9 3
get_path 9 2
link 3 1
get_path 9 3
Выходные данные
2
-1
-1
2
4