1058. Bus Routes — Minimum Buses to Destination

Given routes where routes[i] is the list of stops served by bus i (looping forever), plus a source and target stop, return the fewest number of buses you must take to travel from source to target, or -1 if impossible. If source equals target, the answer is 0. The input is JSON {routes, source, target}.

Input: JSON {routes, source, target}.

Output: Integer — fewest buses, or -1.

Examples

Input: {"routes":[[1,2,7],[3,6,7]],"source":1,"target":6}
Output: 2
Explanation: Bus 0 then bus 1.

Input: {"routes":[[1,2,3]],"source":1,"target":1}
Output: 0
Explanation: Already there.

Input: {"routes":[[1,2]],"source":1,"target":9}
Output: -1
Explanation: Target unreachable.

Constraints

• 1<=buses<=500

Asked by