ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1752. Дерево 2

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Рассмотрим дерево, состоящее из n вершин. Назовём расстоянием между двумя вершинами минимальное количество рёбер в пути, соединяющем эти вершины. По вершине vi и расстоянию di найдите такую вершину ui, что расстояние между vi и ui равняется di.

Исходные данные

В первой строке записано количество вершин n (1 ≤ n ≤ 20000) и количество запросов q (1 ≤ q ≤ 50000). Каждая из следующих n − 1 строк описывает ребро и содержит номера вершин, соединённых этим ребром. Вершины занумерованы числами от 1 до n. В следующих q строках заданы запросы. Каждый запрос представляет собой строку, в которой записаны числа vi (1 ≤ vin) и di (0 ≤ din).

Результат

Выведите q строк. В i-й строке выведите номер вершины ui — ответ на i-й запрос. Если существует несколько возможных ответов, выведите любой из них. Если искомой вершины не существует, выведите 0.

Пример

исходные данныерезультат
9 10
1 8
1 5
1 4
2 7
2 5
3 6
5 9
6 9
5 4
8 1
4 3
2 4
9 3
1 1
5 2
3 5
6 4
7 3
0
1
2
3
4
5
6
7
8
9
Автор задачи: Пётр Лежанкин
Источник задачи: Ufa SATU Contest. Petrozavodsk Summer Session, August 2009