복도 이동하기

문제

충남대학교 공과대학 5호관의 4층 복도는 항상 컴퓨터인공지능학부 학생들로 붐빈다. 서현이는 복도의 한쪽 끝에서 반대쪽 끝으로 이동하고자 한다.

4층 복도는 $2 \times N$ 크기의 2차원 격자로 생각할 수 있다. 격자의 가장 왼쪽 위 칸은 $(1, 1)$이고, 가장 오른쪽 아래 칸은 $(2, N)$이다. 격자의 각 칸에는 학생이 서 있을 수도 있고 없을 수도 있다. 학생이 서 있는 칸으로는 이동할 수 없다.

서현이는 격자 밖으로 나갈 수 없고, 현재 칸과 상하좌우로 인접한 칸 중 학생이 서 있지 않은 칸으로 이동할 수 있다. 한 번 이동하는 데에는 $1$초가 걸린다.

서현이가 $(1, 1)$에서 출발하여 $(2, N)$에 도착하는 데 필요한 최소 시간을 구하라.

입력

첫째 줄에 복도의 길이 $N$과 복도에 서 있는 학생의 수 $M$이 공백으로 구분되어 주어진다. $(3 \le N \le 10^9; 0 \le M \le 100,000)$

다음 $M$개의 줄 중 $i$번째 줄에는 $i$번째 학생이 서 있는 위치를 의미하는 두 정수 $u_i$, $v_i$가 공백으로 구분되어 주어진다. $(1 \le u_i \le 2; 2 \le v_i \le N - 1)$

주어지는 학생의 위치는 모두 서로 다르다.

학생이 서 있는 칸들을 피해 $(1, 1)$에서 $(2, N)$으로 이동할 수 있는 경로가 존재함이 보장된다.

출력

서현이가 $(1, 1)$에서 $(2, N)$으로 이동하는 데 필요한 최소 시간을 초 단위로 출력한다.

예제 입력 1

7 3
1 2
2 4
1 6

예제 출력 1

9

예제 입력 2

1000000000 1
1 2

예제 출력 2

1000000000