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

Обмеження: 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\).