685. Bus Routes

You are given bus routes where routes[i] is the list of stops that bus i cycles through. Starting at the stop source, return the fewest number of buses you must take to reach the stop target, or -1 if impossible. The input is JSON {routes, source, target}.

Input: JSON {routes, source, target}.

Output: Integer — the fewest buses, or -1.

Examples

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

Input: {"routes":[[7,12],[4,5,15],[6],[15,19],[9,12,13]],"source":15,"target":12}
Output: -1
Explanation: Target unreachable.

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

Constraints

• 1<=routes<=500

Asked by