Problem G
Hyperspace Jumps

The Foundation novel by Issac Asimov (1951) has ships that travel faster than light with hyperspace jumps. In these interrelated stories, there are known paths that can be taken but destinations that can not be reached directly with just one jump. This leads one to the realization that it is not the distance between locations that is important, but the number of jumps. With this in mind, your task is to determine how many different ways there may be to get to a given destination from a set starting point if you were limited to no more than a certain number of jumps.

You will be provided with a chart showing pairs of planets that can be reached with a single jump (in either direction).

Input

On the first line you will be given a non-negative number, $d$, for the distance you are restricted to, as measured in jumps. The second line will contain a number, $n$, $(d<=n<=500)$ that indicates how many jumps are listed in the chart that will be provided in the next $n$ lines of input. Jumps will be described by pairs of numbers that will indicate the planets at the ends of the jumps (guaranteed that the two planets will not be the same). Your starting planet will be identified with the number 0 and your destination will be the endpoint with the maximum value. Each line of the chart will have the format: $a$ $b$, $(0<=a,b<=500)$. The order of possible jumps in the chart is arbitrary, and the direction is also arbitrary.

Output

Print a single integer indicating the maximum number of paths you are able to choose from in your trip. None of the paths should include the same planet twice, but should progressively lead toward and end at the destination..

3
7
0 2
0 15
2 15
15 100
30 15
30 0
100 30

5

4
7
0 2
0 15
2 15
15 100
30 15
30 0
100 30

19

4
7
100 30
30 0
30 15
15 100
2 15
0 15
0 2

19