The Mansion

You are trapped in a huge mansion. The mansion is a grid of square rooms with $N$ rows and $M$ columns. The room that is the $x$-th from the left ($1 \le x \le M$) and the $y$-th from the bottom ($1 \le y \le N$) is denoted $(x, y)$.

Between every pair of adjacent rooms there is exactly one door, and each door is either open or closed. Passing through an open door into a neighboring room takes $1$ minute. You may only move through open doors, and you cannot change a door's state directly.

Some rooms have a switch at their center. Holding a switch down for $1$ minute flips the state of every door in the mansion: every open door becomes closed and every closed door becomes open.

Initially, only the doors between vertically adjacent rooms (one directly above the other) are open; all other doors are closed.

You are currently at the center of room $(1, 1)$ and want to reach the center of room $(M, N)$. Find the minimum time needed to get there.

The first line contains the mansion size $M$, $N$ and the number of rooms that have a switch, $K$, separated by spaces. Each of the next $K$ lines contains the position $x_i$, $y_i$ of a room that has a switch. ($2 \le M, N \le 100000$, $1 \le K \le 200000$)

Print the minimum time to reach room $(M, N)$ on the first line. If $(M, N)$ cannot be reached, print $-1$.