F. Островной пазл
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В далёком островном государстве насчитывается n островов, соединённых мостами с двухсторонним движением. Текущая система мостов образует дерево. Другими словами, всего мостов n - 1, каждый мост соединяет одну пару различных островов, и от любого острова можно дойти до любого другого, используя только эти мосты.

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

Жители островов договорились переупорядочить статуи определённым образом. Единственная доступная им операция — это выбрать какой-то остров, непосредственно соединённый мостом с островом с пустым пьедесталом, и аккуратно перенести статую с одного пьедестала на свободный пьедестал.

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

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

В первой строке входных данных записано число n (2 ≤ n ≤ 200 000) — количество островов.

Во второй строке записаны n целых чисел ai (0 ≤ ai ≤ n - 1) — номер статуи, расположенной на i-м острове. Если ai = 0, то пьедестал острова пуст. Гарантируется, что все ai различны.

В третьей строке записаны n целых чисел bi (0 ≤ bi ≤ n - 1) — номер статуи, которую жители хотят поместить на i-й остров. Как и до этого, bi = 0 означает, что жители острова не хотят иметь у себя на пьедестале никакой статуи. Гарантируется, что все bi различны.

Далее следует n - 1 строка, описывающая дерево. В каждой из них записаны два целых числа ui и vi (1 ≤ ui, vi ≤ n) — индексы вершин, соединённых i-м ребром.

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

Возможные варианты вывода:

Если переупорядочить статуи требуемым образом можно и без постройки дополнительно моста, то выведите 0 t, где t равняется минимальному требуемому количеству действий.

В противном случае выведите u, v и t (1 ≤ u < v ≤ n) — концы нового моста и минимальное количество действий, необходимое, чтобы добиться желаемого расположения статуй.

Если переставить статуи невозможно, даже построив новый мост, выведите  - 1.

Примеры
Входные данные
3
1 0 2
2 0 1
1 2
2 3
Выходные данные
1 3 3
Входные данные
2
1 0
0 1
1 2
Выходные данные
0 1
Входные данные
4
0 1 2 3
0 2 3 1
1 2
1 3
1 4
Выходные данные
-1
Примечание

В первом примере островитяне могут соединить мостом острова 1 и 3, после чего выполнить следующую последовательность действий: передвинуть статую 1 с острова 1 на остров 2, передвинуть статую 2 с острова 3 на остров 1, передвинуть статую 1 с острова 2 на остров 3. Желаемое расположение статуй будет достигнуто за 3 действия.

Во втором примере можно просто передвинуть статую 1 с острова 1 на остров 2. Строить новых мостов не требуется.

В третьем примере переставить статуи желаемым образом невозможно, даже построив новый мост.