Space Runner

An employee, A, must arrive at the company before $6:00$ every morning or lose his salary for the month. A is known to sleep in, so to avoid the harsh penalty he buys a special device called the space runner. This device can cover exactly $2^k$ kilometers in one second (where $k$ is any natural number). However, the device uses a longint for storage so that the total distance covered cannot exceed maxlongint kilometers.

The journey from A's home to his company is represented by a directed graph. The home is node $1$ and the company is node $n$. Every edge in the graph has a length of $1$ kilometer. In each second, A can choose any power‐of‐two jump (i.e. $2^k$ kilometers) provided that a contiguous path of exactly $2^k$ edges exists starting from his current node. Your task is to help A determine the minimum number of seconds required to reach node $n$. It is guaranteed that there is at least one path from node $1$ to node $n$.

inputFormat

The first line contains two space-separated integers $n$ and $m$, representing the number of nodes and the number of directed edges respectively.

Each of the following $m$ lines contains two integers $u$ and $v$, which indicate a directed edge from node $u$ to node $v$. Remember that every edge is exactly $1$ kilometer long.

outputFormat

Output a single integer: the minimum number of seconds required for A to travel from node $1$ to node $n$ using valid power-of-two jumps.

sample

4 4
1 2
2 3
3 4
1 4

1