В далёком островном государстве насчитывается n островов, соединённых мостами с двухсторонним движением. Текущая система мостов образует дерево. Другими словами, всего мостов n - 1, каждый мост соединяет одну пару различных островов, и от любого острова можно дойти до любого другого, используя только эти мосты.
В центре каждого острова расположен пьедестал. На всех пьедесталах всех островов, кроме одного, находится очень хрупкая статуя, причём все статуи различны. У оставшегося острова пьедестал пуст.
Жители островов договорились переупорядочить статуи определённым образом. Единственная доступная им операция — это выбрать какой-то остров, непосредственно соединённый мостом с островом с пустым пьедесталом, и аккуратно перенести статую с одного пьедестала на свободный пьедестал.
Разумеется, очень часто статуи невозможно переупорядочить требуемым образом, используя только описанную выше операцию переноса. Островитяне хотят построить ещё один дополнительный мост, такой что после этого станет возможным перенести все статуи. При этом они, конечно, хотели бы выполнить как можно меньше переносов. Помогите им определить, какой мост необходимо построить и какое минимальное количество действий выполнить, чтобы добиться желаемого расположения статуй.
Выходные данные
Возможные варианты вывода:
Если переупорядочить статуи требуемым образом можно и без постройки дополнительно моста, то выведите 0 t, где t равняется минимальному требуемому количеству действий.
В противном случае выведите u, v и t (1 ≤ u < v ≤ n) — концы нового моста и минимальное количество действий, необходимое, чтобы добиться желаемого расположения статуй.
Если переставить статуи невозможно, даже построив новый мост, выведите - 1.
Примечание
В первом примере островитяне могут соединить мостом острова 1 и 3, после чего выполнить следующую последовательность действий: передвинуть статую 1 с острова 1 на остров 2, передвинуть статую 2 с острова 3 на остров 1, передвинуть статую 1 с острова 2 на остров 3. Желаемое расположение статуй будет достигнуто за 3 действия.
Во втором примере можно просто передвинуть статую 1 с острова 1 на остров 2. Строить новых мостов не требуется.
В третьем примере переставить статуи желаемым образом невозможно, даже построив новый мост.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 0 2
2 0 1
1 2
2 3
|
1 3 3
|
|
2
|
2
1 0
0 1
1 2
|
0 1
|
|
3
|
4
0 1 2 3
0 2 3 1
1 2
1 3
1 4
|
-1
|