| Good Bye 2014 |
|---|
| Закончено |
На Древесном острове наступает Новый год! На этом острове, как понятно из названия, есть n городов, соединенных n - 1 дорогами, причём между каждыми двумя различными городами всегда существует путь. Каждому человеку на Древесном острове требуется ровно минута на прохождение одной дороги.
Есть на Древесном острове причудливая новогодняя традиция под названием «экстремальный забег». Традицию эту можно описать следующим образом.
Некоторый бегун выбирает два различных города, a и b. Для простоты, обозначим кратчайший путь из города a в город b как p1, p2, ..., pl (в частности, p1 = a и pl = b). Затем происходит следующее:
- бегун стартует из города a;
- он следует из города a в город b по кратчайшему пути;
- когда бегун прибывает в город b, он немедленно разворачивается (на это времени не требуется) и бежит в город a по кратчайшему пути;
- когда бегун прибывает в город a, он немедленно разворачивается (на это времени не требуется) и бежит в город b по кратчайшему пути;
- шаги 3 и 4 повторяются до бесконечности.
Иными словами, маршрут бегуна выглядит так: 
Два бегуна, JH и JY, решили совершить «экстремальный забег» в честь Нового года. JH выбрал два города u и v, а JY выбрал два города x и y. Ребята решили начать бежать в одно и то же время и бежать до тех пор, пока они впервые не встретятся в одном городе. Встреча посреди дороги не считается. Они хотят знать, сколько времени им предстоит бегать.
JH и JY не смогли это определить, так что они просят вас помочь им.
В первой строке записано единственное положительное целое число, n (5 ≤ n ≤ 2 × 105) — количество городов на Древесном острове.
Следующие n - 1 строк описывают дороги Древесного острова. В i-й (1 ≤ i ≤ n - 1) из этих строк записано два целых числа через пробел, ai и bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — вершины, соединенные одной дорогой дерева.
В следующей строке записано одно целое число t (1 ≤ t ≤ 2 × 105) — количество тестовых примеров.
Следующие t строк описывают тестовые примеры. В j-й строке (1 ≤ j ≤ t) записано четыре целых числа через пробел uj, vj, xj, yj (1 ≤ uj, vj, xj, yj ≤ n, uj ≠ vj, xj ≠ yj). Это значит, что в этом тестовом примере JH выбрал два города, uj и vj, JY выбрал два города, xj и yj. JH начинает бежать из города uj, а JY начинает бежать из города xj.
Для каждого тестового примера выведите целое число, описывающее количество времени, необходимое для пробега в минутах. Если ребятам придётся бежать бесконечно долго (иными словами, если бегуны никогда не встретятся в одном городе), выведите -1. Если ребята встретятся в момент начала забега, выведите 0.
7
1 3
3 6
7 4
3 7
5 4
7 2
4
6 5 5 3
3 5 4 6
1 5 1 3
1 5 3 1
2
1
0
-1
Пример выглядит так:
