28935번 - Вентиляция 다국어

문제

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

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

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

입력

В первой строке входного файла задано число $n$ --- количество узлов в вентиляции (2ドル\le n\le 200,000円$).

В следующих $n-1$ строках описаны переходы --- по одному в строке. Каждый переход задаётся номерами узлов, которые он соединяет: $a_i$ и $b_i$ (1ドル\le a_i,b_i\le n$; $a_i\neq b_i$). Гарантируется, что между любыми двумя узлами существует единственный путь по переходам.

В следующей строке задано число $m$ --- количество вопросов Нормана (1ドル\le m\le 100,000円$).

В следующих $m$ строках описаны вопросы --- по одному в строке. Каждый вопрос задаётся номером узла, в котором находится Норман ($s_i$) и номером узла, куда он хочет попасть ($t_i$) (1ドル\le s_i,t_i\le N$; $s_i\neq t_i$).

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

출력

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

제한

힌트