Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

D. Большие проблемы организаторов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Финал «Russian Code Cup» 2214 года будет проводиться в n гостиницах. При этом в двух гостиницах, назовем их главными, будут проводиться всевозможные мероприятия, а в остальных поселят участников. Сеть дорог устроена таким образом, что гостиницы соединены n - 1 дорогой, при этом из любой гостиницы можно попасть в любую.

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

Сейчас организаторы еще окончательно не определились, какие гостиницы должны быть главными, поэтому они рассматривают различные варианты расположения главных гостиниц. Для каждого рассматриваемого расположения помогите организаторам посчитать минимальное время.

Входные данные

В первой строке находится целое число n (2 ≤ n ≤ 100000) — количество гостиниц. В последующих n - 1 строках содержится по два целых числа — номера гостиниц между которыми есть дорога. Считайте, что гостиницы нумеруются от 1 до n.

Следующая строка содержит целое число m (1 ≤ m ≤ 100000) — количество запросов. В следующих m строках содержится по два различных целых числа — номера предполагаемых главных гостиниц.

Выходные данные

На каждый запрос организаторов выведите одно целое число — время, которое понадобится, чтобы все участники добрались до главных гостиниц.

Примеры
Входные данные
3
2 3
3 1
3
2 1
2 3
3 1
Выходные данные
1
1
1
Входные данные
4
1 4
1 2
2 3
3
1 4
1 3
2 3
Выходные данные
2
1
2