| Практика Dynamic Forest offline queries |
|---|
| Закончено |
Дан лес из $$$n$$$ синих вершин, изначально без рёбер.
Также даны $$$q$$$ запросов шести типов:
Гарантируется, что целые числа $$$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 19link 1 2 1link 1 3 1link 2 5 3link 5 4 1link 5 6 1link 7 2 1link 8 6 1link 9 2 1make_red 3get_red 8make_red 7get_red 8cut 3get_red 5make_red 4make_red 6get_blue 5make_red 5get_blue 5
7 6 -1 0 2
| Название |
|---|


