Рассмотрим дерево, состоящее из n вершин. Назовём расстоянием между двумя вершинами минимальное количество рёбер в пути, соединяющем эти вершины.
По вершине vi и расстоянию di найдите такую вершину ui, что расстояние между vi и ui
равняется di.
Исходные данные
В первой строке записано количество вершин n (1 ≤ n ≤ 20000) и количество запросов q (1 ≤ q ≤ 50000). Каждая из следующих n − 1 строк описывает ребро и содержит номера вершин, соединённых этим ребром. Вершины занумерованы числами от 1 до n. В следующих q строках заданы запросы. Каждый запрос представляет собой строку, в которой записаны числа vi (1 ≤ vi ≤ n) и di (0 ≤ di ≤ n).
Результат
Выведите 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