Найнижчий спільний предок

Обмеження: 2 сек., 256 МіБ

Задано кореневе дерево з $n$ вершин, пронумерованих від $1$ до $n$. Коренем дерева є вершина $1$.

Потрібно відповісти на $q$ запитів — для пари вершин $x$, $y$ потрібно знайти їхнього найнижчого спільного предка.

Вхідні дані

У першому рядку задано ціле число $n$ — кількість вершин дерева.

У наступних $n - 1$ рядках записано по два цілих числа $u$, $v$ — номери вершин, з’єднані ребром.

Далі задано ціле число $q$ — кількість запитів.

У наступних $q$ рядках записано по два цілі числа $x$, $y$ — номери вершин у запиті.

Вихідні дані

У $q$ рядках виведіть по одному цілому числу на кожен запит — номер найнижчого спільного предка вершин $x$ та $y$.

Обмеження

$1 \le n \le 2 \cdot 10^5$,

$1 \le q \le 2 \cdot 10^5$.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
7 4 7 1 2 1 3 2 4 2 5 3 6 7 4 7 7 6 7 7 5 7 2 3 7 3 4 5	4 1 7 2 1 1 2

Примітки

• Найнижчим спільним предком вершин $4$ і $7$ є вершина $4$.

• Найнижчим спільним предком вершин $7$ і $6$ є вершина $1$.

• Найнижчим спільним предком вершин $7$ і $7$ є вершина $7$.

• Найнижчим спільним предком вершин $5$ і $7$ є вершина $2$.

• Найнижчим спільним предком вершин $2$ і $3$ є вершина $1$.

• Найнижчим спільним предком вершин $7$ і $3$ є вершина $1$.

• Найнижчим спільним предком вершин $4$ і $5$ є вершина $2$.