| Codeforces Round 383 (Div. 1) |
|---|
| Закончено |
Как вы заметили, в стране Arpa живут милые девушки.
Все люди в стране Arpa пронумерованы от 1 до n. Каждый из них любит ровно одного человека, i-й человек любит человека с номером crushi.
Однажды Arpa громко крикнул Owf с верхушки дворца и в стране Arpa началась веселая игра по следующим правилам.
Игра состоит из раундов. Пусть человек с номером x начинает раунд: он звонит человеку crushx, говорит: «Oww...wwf» (буква w повторяется t раз) и немедленно бросает трубку. Если t > 1, то человек с номером crushx звонит человеку с номером crushcrushx и говорит: «Oww...wwf» (буква w повторяется t - 1 раз) и немедленно бросает трубку. Раунд продолжается до тех пор, пока кто-то не получает «Owf» (t = 1). Этот человек объявляется проигравшим в этом раунде и раунд заканчивается. Два раунда не могут происходить одновременно.
У Mehrdad есть ужасный план чтобы сделать игру еще смешнее. Он хочет найти такое минимальное t (t ≥ 1), что для каждого человека x, если x начинает раунд и y — проигравший в этом раунде, то если раунд начнет y, то x будет проигравшим. Найдите такое t, если это возможно.
Заметим, что в стране Arpa возможно такое, что человек любит самого себя (т. е. crushi = i).
Первая строка входных данных содержит целое число n (1 ≤ n ≤ 100) — количество людей в стране Arpa.
Вторая строка содержит n целых чисел, i-е из которых равняется crushi (1 ≤ crushi ≤ n) — номеру человека, которого любит i-й человек.
Если не существует t удовлетворяющего условию, выведите -1. Иначе выведите минимальное из таких t.
4
2 3 1 4
3
4
4 4 4 4
-1
4
2 1 4 3
1
Предположим, в первом тесте из условия t = 3.
Если первый человек начинает раунд, то:
Первый человек звонит второму и говорит «Owwwf», затем второй человек звонит третьему и говорит «Owwf», затем третий человек звонит первому и говорит «Owf», поэтому первый человек становится проигравшим в этом раунде. Поэтому условие удовлетворено, если x равно 1.
Процесс аналогичен, если начинает второй или третий человек.
Если четвертый человек начинает раунд, то:
Четвертый человек звонит самому себе и говорит «Owwwf», затем он звонит себе еще раз и говорит «Owwf», затем он звонит себе опять и говорит «Owf», поэтому он сам и становится проигравшим в этом раунде. Поэтому условие удовлетворено, если x равно 4.
В последнем тесте из условия если начинает первый человек, то проигравшим становится второй, и наоборот.
