wormholes

Problem Description

You are an inter-galactic traveller in a 1-dimensional space. There are n planets in total, numbered 0 to n-1, all lined up in sequence with each of them a fixed distance apart. The time taken to travel from each planet to the next is 1 light year. For instance, travelling from planet 0 to planet 9 would normally take 9 light years.

However, there are also a number of wormholes that exist that whisk a traveller from planet x to planet y in 1 light year, regardless of how far apart x and y really are. Note that y is always greater than x. In other words, all wormholes will take you further away from planet 1.

Now, your task is to figure out the shortest time you can take to travel from planet 0 to planet n-1, using the optimal selection of wormholes. You do not need to print out the path you will take, but only the amount of time this path will take, in light years.

The first line of input will give you the number of planets (n), the second line will give you the number of wormholes that exist, and the subsequent lines will give you the pairs of planets that the wormholes can take you from and to. Your output will be a single number (with a newline at the end) indicating the shortest number of light years it will take for you to travel from planet 0 to planet n-1. n will be at most 255.

The number of wormholes will be at most 255 as well.

Sample Input 1

10
2
3 5
7 9

Sample Output 1

7

Sample Input 2

10
2
1 3
2 7

Sample Output 2

5