Задача . G. Запросы на дереве

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

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

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

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

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