ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

2109. Туризм на Марсе

Ограничение времени: 4.0 секунды
Ограничение памяти: 300 МБ
Мало кто знает, но давным-давно на Марсе существовало развитое государство. В его состав входили n городов, пронумерованных целыми числами от 1 до n, столица имела номер 1. Некоторые пары городов были соединены дорогой. Жители государства были очень расчётливыми, поэтому между любыми двумя городами существовал ровно один путь (возможно, состоящий из нескольких дорог).
Так как государство было развитым, его жители любили путешествовать. Туристический маршрут на Марсе задавался двумя числами L и R. Это означало, что турист начинает путь в городе с номером L, затем едет в город с номером L + 1 (не заезжая в города, не лежащие на пути между L и L + 1), затем едет в город с номером L + 2, и так далее. Последним городом в маршруте был город с номером R. Главной достопримечательностью маршрута туристы считали ближайший к столице город среди всех посещённых на этом маршруте (если расстояние между городами считать по дорогам).
Зная карту марсианского государства и все туристические маршруты, укажите для каждого маршрута номер города, который являлся его главной достопримечательностью.

Исходные данные

В первой строке дано целое число n — количество городов (1 ≤ n ≤ 2 · 105).
Затем в n − 1 строке перечислены дороги. Каждая дорога задаётся двумя номерами городов, которые эта дорога соединяет (1 ≤ vi, uin; viui).
В (n + 1)-й строке дано целое число q — количество туристических маршрутов (0 ≤ q ≤ 106).
Затем в q строках перечислены сами маршруты. Каждый маршрут — пара целых чисел Li, Ri (1 ≤ LiRin).

Результат

Выведите q целых чисел по одному в строке — номер главной достопримечательности для каждого маршрута. Числа следует выводить в том же порядке, в котором были описаны соответствующие маршруты.

Примеры

исходные данныерезультат
7
1 2
1 3
2 4
2 5
2 6
3 7
3
4 6
3 4
5 7
2
1
1
7
1 3
3 5
5 6
7 5
1 4
2 4
3
4 5
5 6
6 7
1
5
5

Замечания

В этой задаче большие объёмы ввода и вывода, а Time Limit выставлен достаточно жёстко. Для решений на языке C++ рекомендуем использовать компилятор Visual C++ 2013.
Автор задачи: Владимир Лесков
Источник задачи: Чемпионат УрФУ среди юниоров 2016