Repetitive Jugglers

View as PDF

Submit solution

Points: 100 (partial)
Time limit: 8.0s
Memory limit: 200M

Authors:
Problem types
Allowed languages
C#, C++, Go, Haskell, Java, JS, Python, Rust

Alice is the leader of a juggling crew, and they are set to perform a crazy juggling trick.

In this trick, every member of the crew starts off with a different coloured ball. Every member then picks another member of the crew (possibly themselves), let us call that member their receiver.

Then, the trick begins. Every second, every crew member will throw all of the balls they are holding to their designated receiver.

The trick only stops once everyone has the same ball they started with (Note that not always does this trick stop!)

Alice wants to know, given who has chosen who as receiver, whether the game will end, and if so, how many seconds this will take.

Input

Input will consist of two lines.

The first line will contain an integer n, the number of members in the juggling crew.

The second line will then contain n space-separated integers. The ith integer represents the ith crew member's pick for receiver.

(So we enumerate crew members 1, 2, 3\ldots, and if the second integer is 1, that means that crew member 2 has chosen 1 as their receiver.)

It is guaranteed that if the trick does stop, it will stop before 10^{15} seconds have passed

Output

If the trick will never finish, print -1. Otherwise, print the total length of the trick, in seconds.

Example Test

Input

3
2 1 3

Output

2

After 1 second, person 1 and person 2 throw the balls at each other, and person 3 throws the ball to themselves. As such person 1 is holding person 2's ball, and person 2 is holding person 1's ball. Person 3 is holding their own ball.

After 2 seconds, the same action occurs, and so everyone is holding their own ball.


Comments

There are no comments at the moment.