A park has waypoints 0 .. n-1 at altitudes height[v], joined by two-way trails (a, b). A tired hiker only counts climbs: a trail to a strictly higher waypoint costs 1, anything else is free.
Implement fewest_climbs(height, trails, start) -> list[int]: for each v, the fewest climbs from start, or -1 if unreachable. Trail count doesn't matter.
height = [5, 3, 8, 6, 9]
trails = [(0, 1), (1, 3), (3, 2), (0, 2), (2, 4)]
fewest_climbs(height, trails, 0)
# [0, 0, 1, 1, 2] 0 -> 2 is one climb; 0 -> 1 -> 3 is one climb (3 up to 6);
# 4 needs 0 -> 2 -> 4, two climbs
Up to 10^5 waypoints and 2 * 10^5 trails. Plain BFS counts trails, not climbs, so it's wrong.
⭐ Bonus: Bellman-Ford still passes; a speed test on a big park earns a star in O(n + trails).
Show hint
weights are 0 or 1, so use 0-1 BFS: a deque where free moves go to the front and climbs to the back (Dijkstra works too, with a log factor).