Олимпиадный тренинг

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


Задача

Темы: Деревья поиск в глубину и подобное графы *2500

Дано дерево из 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.


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

time 3000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
Python1
С++4
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет