Bus Routes: Minimum Transfers

routes[i] is the list of stops bus i visits in a loop, forever. You start at stop source (not on a bus) and want to reach stop target. Return the minimum number of buses you must take, or -1 if impossible.

routes = [[1,2,7], [3,6,7]], source = 1, target = 6
=> 2   (bus 0 to stop 7, then bus 1 to stop 6)

routes = [[7,12], [4,5,15], [6], [15,19], [9,12,13]], source = 15, target = 12
=> -1

Up to 500 routes and 100,000 total stops; stop ids can reach 1,000,000.

Follow-ups

• Output the actual sequence of buses (or stops) taken.
• Transfers cost different amounts of waiting time — what changes? (Dijkstra over the route graph.)
• Building a route-to-route adjacency matrix by intersecting stop sets is O(R² · S). What is the cheaper structure? (A stop → routes map, BFS straight over it.)