0

Bus Routes

Difficulty: MEDIUM
Avg. time to solve
30 min
Success Rate
70%

Problem Statement
Suggest Edit

You are given an array of routes, such that routes[i] denote the bus station’s ith 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 routes[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 
routes[i][0] integers denote the bus station’s number of 
ith bus.
Output Format
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.
Constraints
1<=’T’<=10
1<=’n’<=400
1<=sum(length of routes[i])<=10^5
0<=routes[i][j],’source’,’target’<=10^6
Sample Input 1
1
2 6 7
3 1 5 6
3 5 7 8
Sample Output 1
2

For the first test case.
The best possible ans is to take 1st bus from 6th 
station.
Then from 6th station travel to 5th station using the 
first bus.
Then change the bus at 5th station and take the 2nd 
bus.
From 2nd bus travel to 7th station.
Thus the answer is 2.
Sample Input 2
1
2 7 8
3 1 2 6
3 5 6 7
Sample Output 2
-1
Reset Code
Full screen
copy-code
Console