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

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

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

  • link $$$u$$$ $$$v$$$ $$$w$$$ — добавить новое неориентированное ребро между $$$u$$$ и $$$v$$$ с весом $$$w$$$.
  • cut $$$i$$$ — удалить ребро, которое было добавлено в $$$i$$$-м запросе.
  • make_blue $$$u$$$ — покрасить $$$u$$$ в синий цвет.
  • make_red $$$u$$$ — покрасить $$$u$$$ в красный цвет.
  • get_blue $$$u$$$ — найти кратчайший путь от $$$u$$$ до синей вершины.
  • get_red $$$u$$$ — найти кратчайший путь от $$$u$$$ до красной вершины.

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

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

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

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

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

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

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

Если $$$type$$$ это make_blue, то следует одно целое число $$$u$$$ ($$$1 \le u \le n$$$) — вершина, которую нужно покрасить в синий цвет.

Если $$$type$$$ это make_red, то следует одно целое число $$$u$$$ ($$$1 \le u \le n$$$) — вершина, которую нужно покрасить в красный цвет.

Если $$$type$$$ это get_blue, то следует одно целое число $$$u$$$ ($$$1 \le u \le n$$$) — вершина, от которой нужно найти кратчайший путь к синей вершине.

Если $$$type$$$ это get_red, то следует одно целое число $$$u$$$ ($$$1 \le u \le n$$$) — вершина, от которой нужно найти кратчайший путь к красной вершине.

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

Для каждого из запросов типа get_blue или get_red выведите длину кратчайшего пути от $$$u$$$ до синей или красной вершины соответственно.

Пример
Входные данные
9 19
link 1 2 1
link 1 3 1
link 2 5 3
link 5 4 1
link 5 6 1
link 7 2 1
link 8 6 1
link 9 2 1
make_red 3
get_red 8
make_red 7
get_red 8
cut 3
get_red 5
make_red 4
make_red 6
get_blue 5
make_red 5
get_blue 5
Выходные данные
7
6
-1
0
2