В далёком островном государстве насчитывается n островов, пронумерованных целыми числами от 1 до n. Острова соединены двунаправленными мостами, так чтобы образовывать один цикл: остров номер 1 соединён с островом номер 2, остров номер 2 соединён с островом номер 3 и так далее, а остров номер 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 различны.
Выведите «YES» (без кавычек), если желаемое расположение статуй может быть достигнуто. В противном случае выведите «NO» (без кавычек).
3
1 0 2
2 0 1
YES
2
1 0
0 1
YES
4
1 2 3 0
0 3 2 1
NO
В первом примере островитяне могут сначала подвинуть статую 1 с острова 1 на остров 2, затем подвинуть статую 2 с острова 3 на остров 1 и, наконец, подвинуть статую 1 с острова 2 на остров 3.
Во втором примере островитяне могут просто подвинуть статую 1 с острова 1 на остров 2.
В третьем примере никакая последовательность перемещений не позволит островитянам добиться желаемого расположения статуй.
Название |
---|