Handsome Jonathan, Mr. Panda, Rar the Cat, Bernard the mouse and Mark the Fish were bored of setting problems and decided to explore a new game - Snake and Ladders
As they are playing this snake and ladders game over the internet, the board comprises of N squares, where N can be as large as 1million due to the lack of space constraints.
The squares are numbered from 1 to N where square 1 is where all the players will start and square N is where they are supposed to end up at. The goal of this game is to reach square N before all the other player does.
In order to advance, players are supposed to roll a six-sided dice and the number rolled will be the number of squares they will advance. Eg: If Jonathan is at square 3 and he rolls 5, he will advance to square 8.
In the event that a player exceeds the N squares, for example: Mr. Panda is at square N-1 and he rolls 3. He will then 'bounce back' for the remaining steps after he reaches square N. In this case, Mr. Panda will end up at N-2 after his turn as he will travel 1 step to square N then 'bounce back' two remaining steps to square N-2.
However, the main point of this game are the snakes and ladders. (See Below) When a player lands at the foot of a ladder, he MUST climb up the ladder to a square with a larger number. However, when a player lands at the head of a snake, he will end up sliding down the snake to a square with a lower number. (An alternative explanation would be that the snake will eat you and excrete you on the square where the tail is)
While playing, Jonathan wonders what is the minimum number of dice rolls required for any player to win the game.
However, Mr. Panda, Rar the Cat, Bernard and Mark are all very lazy to code the solution to this problem and decides to set it for contest instead... yay.
The first line of input will consist of 2 integers, N and S. N is the number of squares of the board and S is the total number of snakes and ladders combined.
Subsequent S lines will consist of 2 integers each: A and B. A is the starting square of the snake/ladder and B is the ending square of the snake/ladder. If A < B, then it is a ladder and if A > B, it would be a snake. There can only be at most one snake or ladder originating from a single square but multiple snakes and ladders can end at the same square.
Square N and 1 will not be the start of any ladder or snake and it is guaranteed that there will not be a 'cycle' of snakes and ladders which players cannot get out of.
Output a single integer, the minimum number of dice rolls for any player to win the game.
In the event that no player can win the game, print -1 instead.
Subtask 1 (0 points): Sample
Subtask 2 (27 points): S = 0
Subtask 3 (28 points): Each square will have at most one snake or one ladder touching it (start + end at that square)
Subtask 4 (45 points): No further restrictions
The sample input corresponds to the image above. To clarify, when a player lands at square 62, he will slide down the snake to square 19 and then climb the ladder to square 38. He effectively 'lands' at square 38.