Вентиляция
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
treefirstedge.in
вывод
treefirstedge.out

Норман заблудился в вентиляции и уже четвёртую неделю ищет свою квартиру.

Вентиляция состоит из n узлов, соединённых n - 1 переходами таким образом, что между любыми двумя узлами существует ровно один путь.

Иногда Норман задаётся вопросом: в каком направлении идти, чтобы попасть в некоторый узел. Норман — всего лишь морская свинка, поэтому он не может запомнить все узлы и переходы между ними. Помогите ему узнать, куда идти.

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

В первой строке входного файла задано число n — количество узлов в вентиляции (2 ≤ n ≤ 200 000).

В следующих n - 1 строках описаны переходы — по одному в строке. Каждый переход задаётся номерами узлов, которые он соединяет: ai и bi (1 ≤ ai, bi ≤ n; ai ≠ bi). Гарантируется, что между любыми двумя узлами существует единственный путь по переходам.

В следующей строке задано число m — количество вопросов Нормана (1 ≤ m ≤ 100 000).

В следующих m строках описаны вопросы — по одному в строке. Каждый вопрос задаётся номером узла, в котором находится Норман (si) и номером узла, куда он хочет попасть (ti) (1 ≤ si, ti ≤ N; si ≠ ti).

Узлы нумеруются с 1.

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

Для каждого вопроса выведите номер узла, в который нужно идти из si напрямую, чтобы попасть в ti. Обратите внимание, что ответ единственный, так как между любыми двумя вершинами существует ровно один путь.

Пример

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