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