eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Динамический Лес

Динамический Лес

Лимит времени 1 секунда
Лимит использования памяти 256 MiB

Вам нужно научиться обрабатывать 3 типа запросов:

  1. Добавить ребро в граф (link).

  2. Удалить ребро из графа (cut).

  3. По двум вершинам a и b вернуть длину пути между ними (или -1, если они лежат в разных компонентах связности) (get).

Изначально граф пустой (содержит N вершин, не содержит ребер). Гарантируется, что в любой момент времени граф является лесом. При добавлении ребра гарантируется, что его сейчас в графе нет. При удалении ребра гарантируется, что оно уже добавлено.

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

Числа N и M (1N10^5+1, 1M10^5) — количество вершин в дереве и, соответственно, запросов. Далее Mстрок, в каждой строке команда (link или cut, или get) и 2 числа от 1 до N — номера вершин в запросе.

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

В выходной файл для каждого запроса get выведите одно число — расстояние между вершинами, или -1, если они лежат в разных компонентах связности.

Пример

Входные данные #1
3 7
get 1 2
link 1 2
get 1 2
cut 1 2
get 1 2
link 1 2
get 1 2
Выходные данные #1
-1
1
-1
1