Лена играется со спичками. Естественный вопрос, посещающий любого школьника, играющего со спичками — а можно ли поджечь спичкой дерево?
Скажем, что дерево — это связный граф без циклов, вершины которого пронумерованы целыми числами \(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» они тоже останутся различными. Исходно они различны, поэтому в любой момент времени порядок сгорания листьев определён однозначно.
Выходные данные
Для каждого запроса типа «when» нужно вывести одно целое число от \(1\) до \(n\) — момент времени, когда сгорит вершина \(v\).
Для запроса типа «compare» выведите \(v\) или \(u\), в зависимости от того, какая вершина сгорит раньше.
Примечание
В первом примере процесс сгорания исходного дерева проиллюстрирован на картинке:
В частности, порядок сгорания вершин следующий: \([2, 4, 3, 1, 5]\).
Во втором примере после применения операции «up» порядок сгорания вершин станет следующим: \([2, 4, 3, 5, 1]\)