Задача C. LCA ≡

Автор:	И. Туфанов		Ограничение времени:	2 сек
Входной файл:	input.txt		Ограничение памяти:	64 Мб
Выходной файл:	output.txt

Условие

Дано дерево из N вешрин, все некоторым образом пронумерованы, а корень имеет номер 1. Найдите LCA для некоторых пар вершин.

Формат входного файла

Первая строка входного файла состоит из единственного числа N. Далее в N−1 строке следует описание дерева: пары соединенных вершин. После этого до конца файла записаны пары номеров веришин, для которых следует найти LCA. Количество этих пар не превосходит 10^5.

Формат выходного файла

В выходном файле для каждого запроса выведите единственное число: номер LCA.

Ограничения

1 ≤ N ≤ 10⁵

Примеры тестов

№	Входной файл (input.txt)	Выходной файл (output.txt)
1	6 1 3 2 3 3 4 3 5 6 2 1 2 6 5 скопировать	1 3 скопировать

---