Пересування по країні

Обмеження: 3 сек., 512 МіБ

Зеник живе у країні, де є \(n\) міст. У країні є \(n - 1\) дорога, кожна з яких з’єднує два міста. Усі міста сполучені дорогами так, що між будь-якими двома містами існує лише один маршрут.

Столицею країни є місто з номером 1. Від столиці відходять дороги до інших міст, від них — ще далі, і так утворюється мережа міст, що розходяться від центру.

Зеник може подорожувати країною двома способами:

• Проїхати маршруткою між двома містами, що з’єднані дорогою.

• Телепортуватися далі від столиці — одразу потрапити до будь-якого міста, що знаходиться на один рівень далі від столиці, ніж те, у якому він зараз перебуває.

Надходять \(q\) запитів: за яку мінімальну кількість кроків Зеник може дістатися до Марічки, якщо він зараз перебуває в місті \(u\), а вона — в місті \(v\).

Вхідні дані

В першому рядку задано ціле число \(n\) — кількість міст у країні.

В наступних \(n - 1\) рядках задано по два цілі числа — пари міст, що з’єднані дорогою.

В наступному рядку задано одне ціле число \(q\) — кількість запитів.

В наступних \(q\) рядках задано по два цілі числа \(u\) та \(v\) — міста де є Зеник і Марічка відповідно.

Вихідні дані

В \(q\) рядках виведіть мінімальну кількість кроків, щоб Зеник дійшов від міста \(u\) до міста \(v\).

Обмеження

\(1 \le n, q \le 4 \cdot 10^5\),

\(1 \le u, v \le n\).

Оцінювання складається з таких блоків:

• по 1 балу за кожен приклад з умови,

• 27 балів: \(n, q \le 1000\),

• 14 балів: міста \(u\) та \(v\) на однаковій відстані від столиці,

• 21 бал: місто \(u\) не є далі від столиці ніж місто \(v\),

• 37 балів: без додаткових обмежень.

Бали за блок ви отримаєте, тільки якщо ваша програма пройде всі тести з блоку.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
7 1 2 1 4 2 3 2 5 4 6 6 7 4 5 7 4 7 7 4 4 4	1 2 2 0

Примітки

Країна в прикладі виглядає так:

В першому запиті Зеник є у місті 5, а Марічка у місті 7. Зеник може телепортуватися з міста 5 у місто 7 за один крок, оскільки місто 5 на є на відстані 2 від столиці, а місто 7 на відстані 3.

В другому запиті Зеник може поїхати маршруткою з міста 7 у місто 6, оскільки між ними є дорога, а після того з міста 6 поїхати маршруткою у місто 4. Тут йому знадобиться зробити 2 дії.