ЗАДАЧА I

Дороги

Имя входного файла:roads.in
Имя выходного файла:roads.out
Ограничение по времени:1 секунда
Ограничение по памяти:64 Мб

В связи с тем, что в деревне Простоквашино построено две гостиницы, аэродром, три военных санатория и проведена автотрасса российского значения, переименовать деревню Простоквашино в город Простоквашинск.
Мэром города назначить Ломовую-Бамбино Тамару Семёновну.


Э.Успенский «Дядя Федор, пес и кот», почти конец



Вскоре Простоквашино (а точнее Простоквашинск) еще больше разрослось. Сегодня Простоквашинск – уже центр Простоквашинской области, а на должности мэра по-прежнему работает тетя дяди Федора, Тамара Семёновна. Одной из приоритетных задач развития области является постройка дорог.

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

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

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


Первая строка входного файла содержит единственное натуральное число N (1 <= N <= 15000) – количество населенных пунктов (т.е. деревень и самого Простоквашинска) в области. Все населенные пункты пронумерованы от 1 до N, причем Простоквашинск имеет номер 1. Следующие N-1 строк содержат по два различных натуральных числа A и B (1 <= A, B <= N) – номера населенных пунктов, соединенных дорогой.

Следующая строка содержит единственное натуральное число M (1 <= M <= 30000) – количество запросов к программе. Каждая из следующих M строк описывает запрос и содержит два натуральных числа A и B (1 <= A, B <= N).

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


Для каждого запроса во входном файле выведите в выходной файл строку, содержащую ответ на запрос – расстояние между населенными пунктами A и B.

Пример


roads.in roads.out 
8
1 2
2 3
3 4
3 5
3 6
6 7
7 8
5
2 8
4 6
1 3
5 5
7 4
 
4
2
2
0
3


Подсказка

Ваше решение должно быть действительно быстрым, чтобы пройти ограничение по времени на максимальном тесте.