Как вы заметили, в стране 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).
Выходные данные
Если не существует t удовлетворяющего условию, выведите -1. Иначе выведите минимальное из таких t.
Примечание
Предположим, в первом тесте из условия t = 3.
Если первый человек начинает раунд, то:
Первый человек звонит второму и говорит «Owwwf», затем второй человек звонит третьему и говорит «Owwf», затем третий человек звонит первому и говорит «Owf», поэтому первый человек становится проигравшим в этом раунде. Поэтому условие удовлетворено, если x равно 1.
Процесс аналогичен, если начинает второй или третий человек.
Если четвертый человек начинает раунд, то:
Четвертый человек звонит самому себе и говорит «Owwwf», затем он звонит себе еще раз и говорит «Owwf», затем он звонит себе опять и говорит «Owf», поэтому он сам и становится проигравшим в этом раунде. Поэтому условие удовлетворено, если x равно 4.
В последнем тесте из условия если начинает первый человек, то проигравшим становится второй, и наоборот.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2 3 1 4
|
3
|
|
2
|
4
4 4 4 4
|
-1
|
|
3
|
4
2 1 4 3
|
1
|