 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] 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
``````   Console