F. Спички детям не игрушка
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Скажем, что дерево — это связный граф без циклов, вершины которого пронумерованы целыми числами $$$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$$$, в зависимости от того, какая вершина сгорит раньше.

Примеры
Входные данные
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
Выходные данные
4
1
3
2
5
2
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
Выходные данные
2
4
3
5
Примечание

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

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

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