eolymp
Problems

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

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

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

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

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

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

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

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

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

Time limit 1 second
Memory limit 256 MiB
Input example #1
3 7
get 1 2
link 1 2
get 1 2
cut 1 2
get 1 2
link 1 2
get 1 2
Output example #1
-1
1
-1
1