Fewest Rolls on a Rope-and-Chute Board

A board has squares numbered 1 .. n in a single line. A token starts on square 1. Each turn you choose a die result k from 1 to 6 and move the token forward k squares; a move that would pass square n is not allowed. shortcuts is a list of pairs [s, e]: whenever the token lands on square s it is immediately moved to square e (a rope if e > s, a chute if e < s).

Return the fewest turns needed to put the token on square n, or -1 if that is impossible.

Examples

Input:  n = 10, shortcuts = [[3, 9]]
Output: 2
Explanation: roll 2 (1 -> 3, rope up to 9), then roll 1 (9 -> 10).

Input:  n = 10, shortcuts = [[4,2],[5,2],[6,2],[7,2],[8,2],[9,2]]
Output: -1
Explanation: squares 4..9 all slide back to 2, so the token can only ever
rest on 1, 2 or 3, and square 10 is more than 6 away from all of them.

Input:  n = 1, shortcuts = []
Output: 0

Constraints

• 1 <= n <= 10**4
• Each square starts at most one shortcut. No shortcut starts on square 1 or square n, and no shortcut starts on a square where another shortcut ends.
• Target O(n) time (each square has at most 6 outgoing moves).

Goals

• Model a board game as an implicit graph whose edges are die rolls
• Apply a shortcut at the moment a square is landed on
• Find the minimum number of turns with BFS