Yatin created an interesting problem for his college juniors. Can you solve it?
Given \(N\) rooms, where each room has a one-way door to a room denoted by \(room[i]\), where \(1 \leq i \leq N\). Find a positive integer \(K\) such that, if a person starts from room \(i\), \((1 <= i <= N)\) , and continuously moves to the room it is connected to (i.e. \(room[i]\)) , the person should end up in room \(i\) after \(K\) steps;
Note: The condition should hold for each room.If there are multiple possible values of \(K\) modulo (\(10^9 + 7\)), find the smallest one.If there is no valid value of K, output \(-1\)
Constraints:
\(1 \leq T \leq 10\)
\(1 \leq N \leq 10^5\)
\(1 \leq room[i] \leq N\)
Input Format
- The first line of the input contains an integer \(T\), the number of testcases.
- For each Testcase:
- The first line contains an integer \(N\), the number of rooms.
- The second line contains N spaced integers \(room[1], room[2]......room[N]\)
Output Format
- Output the smallest positive integer \(K\) modulo \((10^9 +7)\) , satisfying the above-mentioned conditions.
- If there is no such value, output \(-1\)
1 4 2 3 4 1
4
Given array \(Room = [2,3,4,1]\)
If a person starts from
\(Room 1\)
Path would be \(1 > 2 > 3 > 4 >1\) , so person took 4 steps to reach room 1
\(Room 2\)
Path would be \(2 > 3 > 4 >1 > 2\) , so person took 4 steps to reach room 1
and so on for other rooms.
Similarly, it would give a value 4 for each case, And this is the smallest valid value, so \(K = 4\) for this case
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor