Fewest Buses

A city has a number of bus routes. routes[i] lists the stops that bus i visits; it drives round its route forever, so once you are on bus i you can ride to any of its stops. You are at stop start, not on any bus, and want to get to stop goal.

Write fewest_buses(routes, start, goal) that returns the fewest buses you must board to get there, or -1 if it cannot be done. If start and goal are the same stop, the answer is 0.

Examples

fewest_buses([[1, 2, 7], [3, 6, 7]], 1, 6)  # returns 2
fewest_buses([[2, 5, 8], [8, 9, 11], [11, 3]], 2, 3)  # returns 3
fewest_buses([[1, 2], [3, 4]], 1, 4)  # returns -1

In the first city you take bus 0 from stop 1 to stop 7, then change to bus 1 and ride to stop 6. In the last, no bus links the two routes.

Constraints

• Up to 500 routes with up to 100,000 stops in all. A single route can have 50,000 stops.
• Stops are integers from 0 to 1,000,000, and a route may list a stop more than once.