Fewest Buses to Ride Between Two Stops on Looping Bus Lines

A city runs several bus lines. Each line drives a fixed loop of stops and repeats it forever, so a rider who boards a line can stay on from any of its stops to any other of its stops. You start at stop source, not on any bus, and want to reach stop target. You can board or leave a bus only at a stop on its line, and you change lines by leaving one bus at a stop that both lines serve.

Return the fewest buses you must board to travel from source to target, or -1 if target cannot be reached.

Function Signature

def min_buses(routes: list[list[int]], source: int, target: int) -> int:

routes[i] lists the stops served by line i in the order its bus visits them; after the last stop the bus returns to the first. source and target are stop IDs.

Rules

• Every boarding counts as one bus, including the first. Riding one line between any two of its stops counts as one bus, however many stops lie between them.
• If source == target, the answer is 0, even when that stop is on no line.
• Otherwise, if no sequence of boardings reaches target, return -1. This includes a source or a target that no line serves.
• Riders change lines only at a shared stop; walking between different stops is not allowed.
• The answer is a single integer, so it is unique.

Constraints

• 1 <= len(routes) <= 500
• 1 <= len(routes[i]) <= 10^5
• The total number of stops over all lines, sum(len(r) for r in routes), is at most 10^5.
• The stops within one line are distinct; the same stop may appear on many lines.
• 0 <= routes[i][j] < 10^6
• 0 <= source, target < 10^6
• All values fit in a signed 32-bit integer.

Examples

Example 1

Input: routes = [[2, 4, 9], [9, 11, 5], [5, 13], [4, 5]], source = 4, target = 13
Output: 2

Board line 3 at stop 4 and ride to stop 5, then board line 2 at stop 5 and ride to stop 13: two buses. One bus is not enough, because no single line serves both 4 and 13. Lines 0, 1 and 2 also connect the two stops (4 to 9, 9 to 5, 5 to 13), but that takes three buses.

Example 2

Input: routes = [[1, 3, 5], [2, 4], [4, 8]], source = 3, target = 8
Output: -1

Stop 3 is served only by line 0, whose stops are 1, 3 and 5. None of those stops is on another line, so stop 8 cannot be reached.

Example 3

Input: routes = [[7, 12]], source = 3, target = 3
Output: 0

The rider is already at the target, so no bus is needed, even though stop 3 is on no line.