Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

Statement is not available on English language
D. Пограничные врата
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Герой Аркадий находится на узкой полоске земли, разделенной на n зон, пронумерованных от 1 до n. Из i-й зоны можно пройти лишь в (i - 1)-ю зону и в (i + 1)-ю зону, если они существуют. При этом между каждой парой соседних зон находятся пограничные врата, которые могут быть разных цветов, цвет врат между i-й и (i + 1)-й зоной равен gi.

Аркадий может пройти пограничные врата некоторого цвета, только если он перед этим побывал в одном из шатров хранителей ключей этого цвета и взял ключ. В каждой зоне находится ровно один шатер хранителя ключей некоторого цвета, цвет шатра в i-й зоне равен ki. После посещения шатра определенного цвета Аркадий может неограниченное число раз проходить через любые врата этого цвета.

На проход через одни врата Аркадий тратит один ход, на посещение шатра и другие перемещения ходы не требуются. За какое минимальное число ходов Аркадий может попасть из зоны a в зону b, если изначально у него нет никаких ключей?

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

Первая строка содержит три целых числа n, a, b (2 ≤ n ≤ 100 000, 1 ≤ a, b ≤ n, a ≠ b) — число зон, номер начальной зоны и номер конечной зоны, соответственно.

Вторая строка содержит n - 1 целое число g1, g2, ..., gn - 1 (1 ≤ gi ≤ 100 000), где gi означает цвет пограничных врат между зонами i и i + 1.

Третья строка содержит n целых чисел k1, k2, ..., kn (1 ≤ ki ≤ 100 000), где ki означает цвет шатра хранителя ключей в i-й зоне.

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

Если Аркадий не может попасть из зоны a в зону b, не имея изначально ключей, выведите -1.

Иначе выведите минимальное количество ходов, которое потребуется Аркадию.

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

В первом примере, чтобы попасть из зоны 4 в зону 1, Аркадию нужно сначала взять ключ цвета 1, пройти в зону 3, там взять ключ цвета 2 и пройти обратно в зону 4 и затем в зону 5, взять там ключ цвета 3 и дойти до зоны 1 за четыре хода.

Во втором примере Аркадий может дойти лишь до четвертой зоны, так как шатров хранителей ключей цвета 1 нет совсем.