All problems

Bus Routes

Hard · graph traversal

A city has several bus lines. You are given routes, where routes[i] is the list of stops that bus line i serves. The bus drives through those stops in the order given, then returns from the last stop to the first and starts again, forever. Every stop in one line is different, but a stop can be served by several lines.

You are standing at the stop source, not on any bus yet. You want to get to the stop target. You may get on a bus at any stop it serves, and get off at any stop it serves. You cannot walk between stops: the only way to move is by bus.

Each time you get on a bus counts as one bus. Return the fewest buses you need to get from source to target.

If source and target are the same stop, you are already there and the answer is 0. If there is no way to get there, return -1.

Examples

Example 1

Input: routes = [[2, 4, 9], [9, 5, 8], [8, 1]], source = 2, target = 1

Output: 3

Take the first bus from stop 2 to stop 9, the second bus from stop 9 to stop 8, then the third bus from stop 8 to stop 1.

Example 2

Input: routes = [[1, 2], [3, 4]], source = 1, target = 4

Output: -1

The two lines have no stop in common, so you can never change from the first to the second.

Example 3

Input: routes = [[1, 5], [5, 6], [1, 6]], source = 1, target = 6

Output: 1

Going via stop 5 takes two buses, but the third line serves both stop 1 and stop 6, so one bus is enough.

Constraints