G. Запросы на дереве
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано дерево из n вершин (пронумерованных от 1 до n). Изначально все вершины белого цвета. Необходимо обработать q запросов двух типов:

  1. 1 x — покрасить вершину x в чёрный цвет. Гарантируется, что первый запрос будет такого типа.
  2. 2 x — для вершины x найти минимальный индекс y, такой, что вершина с индексом y принадлежит простому пути от x до некоторой чёрной вершины (простой путь — такой путь, который проходит через каждую вершину не более одного раза).

Выведите ответ на каждый запрос типа 2.

Обратите внимание, что запросы задаются в модифицированном виде.

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

В первой строке записаны два числа n и q (3 ≤ n, q ≤ 106).

Затем следуют n - 1 строк, в каждой строке записаны два числа xi и yi (1 ≤ xi < yi ≤ n), обозначающие ребро между xi и yi.

Гарантируется, что эти рёбра образуют дерево.

Затем следуют q строк. Каждая строка содержит два целых числа ti и zi, где ti — тип i-го запроса, а zi используется для восстановления xi для этого запроса следующим образом: нужно хранить ответ на последний запрос типа 2 (назовём этот ответ last, изначально last = 0); тогда xi = (zi + last) mod n + 1.

Гарантируется, что первый запрос типа 1, и существует хотя бы один запрос типа 2.

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

Выведите ответ на каждый запрос типа 2.

Пример
Входные данные
4 6
1 2
2 3
3 4
1 2
1 2
2 2
1 3
2 2
2 2
Выходные данные
3
2
1