A board has squares numbered 1 to N². You start on square 1. Each throw of a six-sided die moves you forward 1 to 6 squares (you choose the outcome, and you cannot move past N²). Some squares start a jump: landing on square a immediately moves you to square b (a ladder if b > a, a snake if b < a). Jumps are not chained: after a jump you stay where it lands until the next throw.
Print the fewest throws needed to reach square N², or -1 if it cannot be reached.
Constraints
- 2 ≤ N ≤ 100
- squares 1 and N² never start a jump
- no square starts more than one jump
Input and output
- Input
- Line 1: N and k. Next k lines: a b, a jump from a to b.
- Output
- One integer.
Examples
Input 1
3 2
3 8
6 2Output
2Throw a 2 to reach 3, ride the ladder to 8, then throw a 1 to reach 9: two throws.
Input 2
3 6
2 1
3 1
4 1
5 1
6 1
7 1Output
-1Every square you can reach from 1 is a snake back to 1, so the last square is out of reach.
Show hints
- Each square is a node; each throw is an edge to up to six squares.
- All throws cost the same, so breadth-first search finds the fewest.
Show the explanation
Model the board as a graph where every throw is one edge of equal cost: from square s, for each die value d the destination is s + d, replaced by the jump target if s + d starts a jump. With unit costs, BFS from square 1 visits squares in order of throws used, so the first time it reaches N² is the answer. Mark squares visited when you enqueue them so each is processed once; if the queue empties first, print −1.
Original UniCircle question. Last reviewed 22 Oct 2026.