Норман заблудился в вентиляции и уже четвёртую неделю ищет свою квартиру.
Вентиляция состоит из 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