All problems

Ferry Hops

Medium · shortest path

A harbour region has n ferry stops, numbered 0 to n - 1. Ferries run on numbered lines, and the list legs describes them: each entry [a, b, line] is a ferry leg between stops a and b that belongs to line line and sails in both directions.

You start at stop src and want to reach stop dst. You may board any leg that leaves the stop you are standing at. Staying on the same line from one leg to the next is free. Stepping off one line and boarding a leg of a different line costs one line change, even if you board it at the stop where you arrived. Boarding your very first leg is free, whichever line it belongs to.

Return the smallest number of line changes needed to get from src to dst. Return -1 if dst cannot be reached, and 0 if src and dst are the same stop.

The same line may serve many separate stretches of the map, and several legs may join the same two stops, on the same line or on different ones. The number of legs you ride does not matter, only the number of line changes.

Examples

Example 1

Input: n = 4, legs = [[0, 1, 0], [1, 2, 0], [2, 3, 1]], src = 0, dst = 3

Output: 1

Ride line 0 from stop 0 to stop 2 for free, then change once to line 1 for the last leg.

Example 2

Input: n = 4, legs = [[0, 1, 2], [1, 2, 3], [2, 3, 2], [0, 2, 4], [2, 3, 4]], src = 0, dst = 3

Output: 0

The route 0-1-2-3 would need two changes, but line 4 has legs 0-2 and 2-3, so staying on it needs none.

Example 3

Input: n = 3, legs = [[0, 1, 0]], src = 0, dst = 2

Output: -1

No leg touches stop 2.

Constraints