육각타일미로 탈출기

윤수는 파티로 가는 길에 악랄한 종현에게 당해 육각타일미로에 빠졌다. 미로는 일정한 크기의 정육각형 타일로 구성된 $N$행 $M$열의 격자 형태로 이루어져 있다. 같은 열에 위치한 두 칸을 비교했을 때, 짝수 번째 행의 칸은 홀수 번째 행의 칸보다 반 칸 오른쪽에 위치해 있다. 다음 그림은 $N=4$이고 $M=7$인 육각타일미로를 나타낸 것이다.

윤수는 항상 $(0,0)$에서 출발하며 탈출구는 항상 $(N-1, M-1)$에 존재한다. 종현은 윤수의 탈출을 막기 위해 $K$개의 장애물을 타일 위에 두었다. 윤수는 타일 위에서는 인접한 타일로 이동할 수 있지만 장애물이 있는 타일로는 이동할 수 없다. 두 타일이 하나의 변을 공유한다면 서로 인접하다고 한다.

윤수는 서둘러 파티를 가고 싶기 때문에 미로를 탈출할 수 있는 최단 경로를 찾으려고 한다. 최단 경로는 육각타일미로에서 탈출구까지 가장 적은 개수의 타일을 지나는 경로를 말하는데, 이때 시작하는 타일은 포함하지 않고 탈출구가 있는 타일은 포함한다. 윤수가 탈출구에 도달하기 위한 최단 경로의 타일의 개수를 알아보자.

첫 번째 줄에 미로의 크기를 나타내는 수 $N$, $M$과 장애물의 개수 $K$가 공백으로 구분되어 주어진다.

두 번째 줄부터 다음 $K$개의 줄에 걸쳐 장애물의 위치 $(Y_k, X_k)$를 나타내는 두 수 $Y_k,$ $X_k$가 공백으로 구분되어 주어진다. 두 장애물의 위치가 같은 경우는 주어지지 않는다. 시작하는 타일과 탈출구가 있는 타일에는 장애물이 존재하지 않는다.

윤수가 탈출구에 도달하기 위한 최단 경로의 타일의 개수를 출력한다. 단, 탈출구에 도달할 수 없을 경우 -1을 출력한다.

• $2 \le N \le 1\,000$
• $2 \le M \le 1\,000$
• $0 \le K \le N×M-2$
• $0 \le Y_k \le N - 1$
• $0 \le X_k \le M - 1$
• 입력으로 주어지는 모든 수는 정수이다.