P15808 [JOI 2013 Final] Modern Mansion / Modern Mansion

You got lost in a huge mansion. This mansion consists of square rooms arranged in a grid in the east-west and north-south directions: there are $M$ columns from west to east and $N$ rows from south to north, for a total of $M \times N$ rooms. Let $(x, y)$ denote the room in the $x$-th column from the west ($1 \leq x \leq M$) and the $y$-th row from the south ($1 \leq y \leq N$). Any two adjacent rooms in the east, west, south, or north directions are connected by a door located at the center of the wall. Each door is either closed and impassable, or open and passable. When a door is open, moving between the centers of the two rooms takes 1 minute. Also, the center of some rooms has a switch; holding down a switch for 1 minute will toggle (switch) the open/closed state of all doors in the mansion. At present, all doors connecting two east-west adjacent rooms are closed, and all doors connecting two north-south adjacent rooms are open. You are now at the center of room $(1, 1)$, and you want to reach the center of room $(M, N)$ in the shortest time. ### Task You are given the mansion size $M, N$ and the positions of the $K$ rooms with switches: $(X_1, Y_1), (X_2, Y_2), \dots, (X_K, Y_K)$. Starting from the state where all doors between east-west adjacent rooms are closed and all doors between north-south adjacent rooms are open, find the minimum time (in minutes) needed to move from the center of room $(1, 1)$ to the center of room $(M, N)$. If it is impossible to reach room $(M, N)$, report that.

Read the following data from standard input. - The first line contains three space-separated integers $M, N, K$. $M$ is the number of rooms in the east-west direction, $N$ is the number of rooms in the north-south direction, and $K$ is the number of rooms with switches. - Each of the next $K$ lines, the $i$-th line ($1 \leq i \leq K$), contains two space-separated integers $X_i, Y_i$. This means there is a switch at the center of room $(X_i, Y_i)$. The $K$ pairs $(X_1, Y_1), (X_2, Y_2), \dots, (X_K, Y_K)$ are all distinct.

Output one line to standard output containing a single integer: the minimum number of minutes required to move. If it is impossible to reach room $(M, N)$, output $-1$.

### Sample Explanation 1 In this example, you can move from the center of room $(1, 1)$ to the center of room $(3, 2)$ in 4 minutes with the following actions, and this is the shortest time. 1. Move to the center of room $(1, 2)$. 2. Press the switch at the center of room $(1, 2)$. 3. Move to the center of room $(2, 2)$. 4. Move to the center of room $(3, 2)$. The mansion state at that time is shown in the figure below. In the figure, right is east, up is north, × marks your position, and ○ marks a switch. :::align{center}  ::: ### Sample Explanation 2 In this example, you cannot reach room $(3, 2)$. ### Sample Explanation 3 In this example, the initial mansion state is shown in the figure below. Note that there may also be a switch at the center of room $(1, 1)$ or room $(M, N)$. :::align{center}  ::: ### Constraints $2 \leq M \leq 100\,000$　Number of rooms in the east-west direction of the mansion $2 \leq N \leq 100\,000$　Number of rooms in the north-south direction of the mansion $1 \leq K \leq 200\,000$　Number of rooms with switches $1 \leq X_i \leq M$　East-west coordinate of a room with a switch $1 \leq Y_i \leq N$　North-south coordinate of a room with a switch ### Scoring In the scoring testdata, the part worth 20% of the score satisfies $M \leq 1000$ and $N \leq 1000$. In the scoring testdata, the part worth 30% of the score satisfies $K \leq 2000$. In the scoring testdata, the part worth 50% of the score satisfies at least one of the above two conditions. Also, there is no scoring testdata that satisfies both conditions at the same time. --- Translated by DeepSeek V3.2. # Input Format # Output Format # Hint Translated by ChatGPT 5