New update is available. Click here to update.

Bus Routes

Posted: 19 Mar, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

This time Ninja is helping a lost passenger on a bus stop to reach his destiny with the minimum number of buses he needs to change, on the bus stop a chart is present which contains 'N' arrays. An array 'A' denotes the route that a bus will take, such that A[i] denotes the bus stop 'i'th bus will travel to.

For Example
If the bus route is [3, 6, 7], then it will travel  in sequence 
3 > 6 > 7 > 3 > 6 > 7….

You can travel between the bus stations through buses only. You are given the source bus station and destination bus station. You need to determine the minimum number of buses you need to reach the destination. If it is not possible to reach destination return -1.

Note:
Values of A[i] are distinct.
Input Format
The first line contains a single integer ‘T’ denoting the number of test cases.

The first line of the test case contains ‘N’, ‘SOURCE’, ‘TARGET’ denoting the number of buses, source station, and target station.

The next ‘N’ lines contain the stations that the bus will travel to. 

The first integer of the ith line contains the total number of bus stations ith bus will travel to. 

The next A[i][j] integers denote the bus station’s number of ith bus.
Output Format
For each test case, return the single integer denoting the minimum number of buses to take to travel from source to destination. If it is not possible to reach destination return -1.

Note:

You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints
1 <= ‘T’ <= 10
1 <= ‘N’ <= 400
1 <= sum(length of A[i]) <= 10^5
0 <= A[i][j], ‘SOURCE’, ‘TARGET’ <=10^6

Time Limit: 1 sec