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$. Обратите внимание, что ответ единственный, так как между любыми двумя вершинами существует ровно один путь.