Hexagonal Tile Maze Escape

Yunsu fell into a hexagonal tile maze on the way to a party, after being tricked by the nasty Jonghyun. The maze is a grid of regular hexagonal tiles with $N$ rows and $M$ columns. Compare two cells in the same column: a cell in an even-numbered row is half a cell to the right of a cell in an odd-numbered row. The figure below shows a hexagonal tile maze with $N=4$ and $M=7$.

Yunsu always starts at $(0,0)$, and the exit is always at $(N-1, M-1)$. Jonghyun placed $K$ obstacles on the tiles to block Yunsu's escape. On a tile, Yunsu can move to an adjacent tile, but cannot move onto a tile that has an obstacle. Two tiles are adjacent if they share a side.

Yunsu is in a hurry to get to the party. A shortest path is a path to the exit that passes through the fewest tiles. The starting tile is not counted, and the exit tile is counted. Find the number of tiles on the shortest path from the start to the exit.

The first line contains the maze size $N$ and $M$ and the number of obstacles $K$, separated by spaces.

From the second line, the next $K$ lines each contain the position of an obstacle $(Y_k, X_k)$, separated by a space. No two obstacles are at the same position. The starting tile and the exit tile never have an obstacle.

Print the number of tiles on the shortest path from the start to the exit. If Yunsu cannot reach the exit, print -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$
• All numbers in the input are integers.