LCC '22 Contest 5 S3 - Jimmy's Jovial Jackboxes

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Java 8 1.5s
PyPy 3 2.0s
Python 3 2.0s
Memory limit: 128M
Java 8 256M
PyPy 3 256M

Author:
Problem type

Jimmy has recently bought another large haul of jackboxes! To celebrate, he decides to give each of his N jackboxes an integer a from 1 to N and puts them all into a one-indexed array as a permutation of the integers 1, 2, ..., N. He decides that life is too boring just permuting the jackboxes, so he decides to play a game with his newly made array.

In this game, Jimmy can perform only perform one operation. When performing this operation, Jimmy will create a new array by doing the following:

  • Given a value a_i in his original array, the value at index i in the new array is the value at the original array at index a_i.
  • He then replaces his original array with his new array.

The purpose of this game is to figure out, if possible, the number of operations it takes to return the array to its original state. Jimmy is a bit of a penguin brain, so could you, the newly recruited assistant of LCC Problems, help him solve this problem?

Constraints

1 \le N \le 10^6

1 \le a_i \le N

Subtask 1 [5%]

1 \le N \le 50

Subtask 2 [95%]

No additional constraints.

Input Specification

The first line of input will contain an integer N.

The second line contains N space separated integers a_i, where every number from 1 to N occurs once.

Output Specification

Output the number of operations it takes to return the array to its original value, or -1 if it will never return.

Note that this number may not fit in a 32-bit integer.

Sample Input 1

3
2 3 1

Sample Output 1

2

Explanation for Sample 1

For the first operation, a_1=2, so the new value of a_1 will be the value at index 2, which is 3. Likewise, a_2=1 and a_3=2. After the operation, [2, 3, 1] turns into [3, 1, 2]. Performing the operation again, the value of the new array at index a_1 = 3 is 2, so a_1 = 2, and likewise, a_2=3 and a_3=1. AFter the second operation, [3, 1, 2] turns into [2, 3, 1], returning us to the original array. Therefore, it takes 2 operations.

Sample Input 2

4
1 2 4 3

Sample Output 2

-1

Explanation for Sample 2

After the first operation, the new array will be [1, 2, 3, 4]. Performing any operations on this array will loop back to [1, 2, 3, 4], meaning that it is impossible to go back to the original array.


Comments

There are no comments at the moment.