육각타일미로 탈출기

윤수는 파티에 가는 길에 악랄한 종현에게 당해 육각타일미로에 빠졌다. 미로는 정육각형 타일로 이루어진 $N$행 $M$열의 격자이다. 같은 열에 있는 두 칸을 비교하면, 짝수 번째 행의 칸이 홀수 번째 행의 칸보다 반 칸 오른쪽에 있다. 다음 그림은 $N=4$이고 $M=7$인 육각타일미로이다.

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

윤수는 서둘러 파티에 가고 싶어 한다. 탈출구까지 가장 적은 타일을 지나는 경로를 최단 경로라고 하며, 시작 타일은 포함하지 않고 탈출구 타일은 포함한다. 윤수가 탈출구에 도달하는 최단 경로의 타일 개수를 구하라.

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

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

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

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