The Cyclic Maze
All submissions for this problem are available.
Aladdin has designed a small maze for his son. He has designed a path divided into small partitions. Each partition has a door to the next partition that opens only one way. Each partition also has a number printed on the walls. Each partition has a single exit door but may have multiple entrance doors. The doors open only when someone passes through it and closes immediately after that. So, only one number is visible at a time. Now, the path may curve such that it joins itself at any partition, thus forming a cycle. Aladdin has asked his son to start from the beginning of the path and move ahead in the direction that the doors open. Each partition is exactly identical except for the number painted on its wall. Aladdin has asked his son to find out if there is a cycle in the path and the number of partitions in the cycle.
Finding the task impossible, Aladdin's son asks his friend Rahim to help him. They have a very good coordination among them and they want to find a solution to Aladdin's puzzle together.
In case there is no cycle, the path ends in a chocolate store where free chocolate is available. The chocolate store is denoted by number 0. Otherwise, if they are able to count the number of partitions in the cycle, they are teleported out of the maze.
Help them to solve the maze.
Note: The two friends may or may not move separately. To keep matters simple, Aladdin has made a maximum of one cycle in each path.
The first line of input contains a single integer T denoting the number of test cases.
For each test case, the first line of input contains a single integer N denoting the number of partitions. The next line contains N space separated integers denoting the number painted in each partition. The next line contains a single integer K which denotes that the last partition exits into the kth partition. If K=0, it means there is no cycle.
Output a single integer denoting the number of partitions in the cycle or 0 if there is no cycle.
Example: Input 2 10 1 2 3 4 5 6 7 8 9 10 4 8 1 2 3 4 5 6 7 8 0 Output: 6 0
Explanation: In the first test case, the last partition opens into the 4th partition. Thus, there are 6 elements in the cycle. In the second test case, there is no cycle.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
Fetching successful submissions
If you are still having problems, see a sample solution here.