Протокол «Судного дня»
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Согласно протоколу «Судного дня», выжившим агентам Кингсман нужно добраться до некого винного магазина. Для этого они могут воспользоваться лондонским метро и секретными тоннелями Кингсман. Сеть лондонского метро представляет собой дерево, где вершины — станции, а ребра — перегоны между ними. Станции пронумерованы числами от 1 до n, и винный магазин находится на станции с номером 1. Все перегоны имеют одинаковую длину. Так как за выжившими агентами может вестись наблюдение, и перемещение по метро может раскрыть их местонахождение, они должны перемещаться по метро только в направлении от магазина, чтобы запутать противника. Другими словами, они могут проехать на метро от станции до соседней, только если расстояние по ребрам от магазина до первой станции меньше, чем до второй. Все тоннели кингсман соединяют две станции метро, такие, что от одной можно доехать до другой перемещаясь по метро только в направлении от магазина.

Мерлин прорабатывает различные сценарии, которые могут возникнуть при активации протокола «Судного дня». Каждый сценарий характеризуется тем, на какой станции метро находятся выжившие агенты, и каким наибольшим количеством тоннелей они могут воспользоваться. По метро агенты могут перемещаться сколько угодно, но только в направлении, удаляющем их от магазина. Мерлину необходимо для каждого сценария узнать, на каком минимальном расстоянии от магазина могут оказаться выжившие агенты, если будут следовать всем указаниям, ведь оставшийся путь им придется проделать пешком.

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

В первой строке дано одно целое число n — количество станций метро (2 ≤ n ≤ 200 000). В следующих n - 1 строках дано по два целых числа, ai и bi — номера станций, соединенных перегоном метро (1 ≤ ai, bi ≤ n). В следующей строке дано одно целое число m — суммарное количество тоннелей кингсман (0 ≤ m ≤ 200 000). В следующих m строках дано по два целых числа, ui и vi — номера станций, соединенных тоннелем кингсман (1 ≤ ui, vi ≤ n, ui ≠ vi). Гарантируется, что от vi можно добраться до ui, перемещаясь только в направлении удаления от магазина. В следующей строке дано одно целое число q — количество сценариев (0 ≤ q ≤ 200 000). В следующих q строках дано по два целых числа, si и ki — номер станции метро, на которой изначально находятся выжившие агенты, и количество тоннелей кингсман, которыми они могут воспользоваться (1 ≤ si ≤ n, 0 ≤ ki ≤ m).

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

Для каждого сценария выведите одно число — номер станции, находящейся на минимальном расстоянии до магазина, среди тех, до которых могут добраться выжившие агенты.

Пример

Входные данные
5
1 2
2 3
2 4
1 5
2
3 1
4 2
4
2 0
4 1
4 2
5 2
Выходные данные
2
2
1
5