Задача B. LCA

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

Условие

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

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

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

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

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

Ограничения

1 ≤ N ≤ 105

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

Входной файл (input.txt) Выходной файл (output.txt)
1
6
1 3
2 3
3 4
3 5
6 2
1 2
6 5
1
3

0.071s 0.012s 13