횡단보도

당신은 집으로 가는 도중 복잡한 교차로를 만났다! 이 교차로에는 사람이 지나갈 수 있는 $N$ 개의 지역이 있고 그 지역 사이를 잇는 몇 개의 횡단보도가 있다. 모든 지역은 횡단보도를 통해 직, 간접적으로 연결되어 있다. 편의상 $N$ 개의 지역을 $1$부터 $N$까지로 번호를 붙이자.

당신은 이미 멀리서 교차로의 신호를 분석했기 때문에 횡단보도에 파란불이 들어오는 순서를 알고 있다. 횡단보도의 주기는 총 $M$ 분이며 $1$분마다 신호가 바뀐다. 각 주기의 $1+i (0 \le i < M)$ 번째 신호는 $i, M+i, 2M+i, 3M+i, \cdots$ 분에 시작해서 $1$분 동안 $A\_i$번 지역과 $B\_i$번 지역을 잇는 횡단보도에 파란불이 들어오고, 다른 모든 횡단보도에는 빨간불이 들어온다. 한 주기 동안 같은 횡단보도에 파란불이 여러 번 들어올 수 있다.

횡단보도에 파란불이 들어오면 당신은 해당 횡단보도를 이용하여 반대편 지역으로 이동할 수 있으며 이동하는 데 $1$분이 걸린다. 횡단보도를 건너는 도중에 신호가 빨간불이 되면 안되기 때문에 신호가 $s \sim e$ 시간에 들어온다면 반드시 $s \sim e-1$ 시간에 횡단보도를 건너기 시작해야 한다.

횡단보도와 신호의 정보가 주어질 때, 시간 $0$분 에서 시작해서 $1$번 지역에서 $N$번 지역까지 가는 최소 시간을 구하는 프로그램을 작성하여라.

첫 번째 줄에는 지역의 수 $N$, 횡단보도의 주기 $M$이 공백으로 구분되어 주어진다.

두 번째 줄부터 $M$ 개의 줄 중 $1+i$ 번째 줄에는 $i, M+i, 2M+i, 3M+i, \cdots$ 분에 시작해서 $1$분동안 파란불이 들어오는 횡단보도의 두 끝점 $A\_i$, $B\_i$가 공백으로 주어진다.

첫 번째 줄에 $1$ 번 지역에서 $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)$
• 모든 지역은 횡단보도를 통해 서로 직, 간접적으로 연결되어 있다.
• 입력으로 주어지는 모든 수는 정수다.