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