Crosswalk

On your way home you have come across a busy intersection. This intersection has $N$ areas that people can pass through, and several crosswalks connecting these areas. Every area is connected to every other, directly or indirectly, through crosswalks. For convenience, number the $N$ areas from $1$ to $N$.

You analyzed the intersection's signals from afar, so you know the order in which the crosswalks get a green light. A signal cycle lasts $M$ minutes, and the signal changes every minute. The $1+i$-th signal of each cycle ($0 \le i < M$) starts at minutes $i, M+i, 2M+i, 3M+i, \cdots$ and for $1$ minute gives a green light to the crosswalk connecting area $A_i$ and area $B_i$, while every other crosswalk gets a red light. The same crosswalk can get a green light several times within one cycle.

When a crosswalk has a green light, you can use it to move to the area on the other side, and the move takes $1$ minute. The signal must not turn red while you are crossing, so if the signal is green during time $s \sim e$, you must start crossing the crosswalk during time $s \sim e-1$.

Given the crosswalks and the signal information, write a program that finds the minimum time needed to get from area $1$ to area $N$, starting at minute $0$.

The first line gives the number of areas $N$ and the signal cycle length $M$, separated by a space.

Of the $M$ lines starting from the second line, the $1+i$-th line gives the two endpoints $A_i$ and $B_i$ of the crosswalk that gets a green light for $1$ minute starting at minutes $i, M+i, 2M+i, 3M+i, \cdots$, separated by a space.

On the first line, print the minimum time in minutes needed to get from area $1$ to area $N$.

• $2 \leq N \leq 100\,000$
• $1 \leq M \leq 700\,000$
• $1 \leq A_i, B_i \leq N$ $(0 \le i < M)$
• $A_i \ne B_i$ $(0 \le i < M)$
• Every area is connected to every other, directly or indirectly, through crosswalks.
• All numbers in the input are integers.