На Древесном острове наступает Новый год! На этом острове, как понятно из названия, есть 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 не смогли это определить, так что они просят вас помочь им.
Выходные данные
Для каждого тестового примера выведите целое число, описывающее количество времени, необходимое для пробега в минутах. Если ребятам придётся бежать бесконечно долго (иными словами, если бегуны никогда не встретятся в одном городе), выведите -1. Если ребята встретятся в момент начала забега, выведите 0.
Примечание
Пример выглядит так:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|