Вентиляция

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

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