Задача №114117. Спички детям не игрушка

Лена играется со спичками. Естественный вопрос, посещающий любого школьника, играющего со спичками — а можно ли поджечь спичкой дерево?

Скажем, что дерево — это связный граф без циклов, вершины которого пронумерованы целыми числами $1, 2, \ldots, n$, в каждой вершине которого также записано некоторое целое число $p_v$, являющееся приоритетом вершины $v$. Все приоритеты различны.

Оказывается, что если поджечь дерево, то оно, как и можно было ожидать, сгорит целиком. Однако процесс этот не быстрый. Сначала у дерева сгорает лист ( листом называется вершина, имеющая ровно одного соседа) с минимальным приоритетом, затем сгорает лист с минимальным приоритетом из оставшихся вершин дерева, и так далее. Таким образом, вершины превращаются в листья и сгорают до тех пор, пока от дерева не останется лишь одна вершина, после чего она тоже сгорает.

Лена приготовила дерево из $n$ вершин и в каждой вершине записала приоритет $p_v = v$. Лене с одной стороны интересно посмотреть, как горит дерево, но с другой она понимает, что если дерево поджечь, оно исчезнет насовсем. Лена добрая девочка, и деревья ей жалко, так что она хочет ограничиться выяснением ответов на некоторые вопросы про процесс сгорания дерева в уме. Лена хочет ответить на $q$ вопросов, каждый из которых относится к одному из трёх следующих видов:

« up $v$», присвоить вершине $v$ приоритет $1 + \max\{p_1, p_2, \ldots, p_n\}$;
« when $v$», выяснить, какой по счёту сгорит вершина $v$, если дерево поджечь сейчас;
« compare $v$ $u$», выяснить, какая из вершин $v$ и $u$ сгорит раньше, если дерево поджечь сейчас.

Заметим, что если приоритеты всех вершин сейчас различны, то и после выполнения запроса « up » они тоже останутся различными. Исходно они различны, поэтому в любой момент времени порядок сгорания листьев определён однозначно.

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

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

В $i$-й из следующих $n - 1$ строк находятся два целых числа $v_i$, $u_i$ ($1 \le v_i, u_i \le n$), задающие концы $i$-го ребра дерева.

Каждая из оставшихся $q$ строк содержит операцию одного из трёх типов.

« up $v$» ($1 \le v \le n$) — присвоить новый приоритет вершине $v$;
« when $v$» ($1 \le v \le n$) — определить момент сгорания вершины $v$ для текущего дерева;
« compare $v$ $u$» ($1 \le v, u \le n$, $v \ne u$) — определить, какая из вершин $v$ и $u$ сгорит раньше для текущего дерева.

Гарантируется, что среди запросов хотя бы один имеет тип « when » или « compare ».

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

Для каждого запроса типа « when » нужно вывести одно целое число от $1$ до $n$ — момент времени, когда сгорит вершина $v$.

Для запроса типа « compare » выведите $v$ или $u$, в зависимости от того, какая вершина сгорит раньше.

Примечание

В первом примере процесс сгорания исходного дерева проиллюстрирован на картинке:

$\text{[math]}$

В частности, порядок сгорания вершин следующий: [2, 4, 3, 1, 5] Во втором примере после применения операции «up» порядок сгорания вершин станет следующим: [2, 4, 3, 5, 1]

Система оценки

Тесты к этой задаче состоят из пяти групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.

$\text{[math]}$

Примеры

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

5 7
1 5
1 2
1 3
4 3
when 1
when 2
when 3
when 4
when 5
compare 2 3
compare 3 4

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

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

5 5
1 5
1 2
1 3
4 3
up 1
compare 2 4
compare 4 3
compare 3 1
compare 1 5

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

Сдать: для сдачи задач необходимо войти в систему