Problem Description

You have gotten lost in a large mansion. This mansion consists of square rooms arranged in a grid pattern from west to east and from south to north, with $M$ rooms in the east-west direction and $N$ rooms in the north-south direction, totaling $M \times N$ rooms. The room located 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$) is represented as $(x, y)$.

The rooms adjacent to each other in the east-west or north-south direction are connected by doors in the middle of the walls. Each door can be either closed (impassable) or open (passable). When a door is open, it takes 1 minute to move between the centers of the connected rooms. Additionally, some rooms have switches in their centers. Pressing a switch for 1 minute toggles the state of all doors in the mansion (open to closed or closed to open).

Currently, all doors connecting rooms adjacent in the east-west direction are closed, and all doors connecting rooms adjacent in the north-south direction are open. You are currently in the center of room $(1, 1)$ and want to move to the center of room $(M, N)$ in the shortest time possible.

Input Format

Read the following data from standard input:

• The first line contains integers $M$, $N$, and $K$ separated by spaces. $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.
• The next $K$ lines contain integers $X_i$ and $Y_i$ separated by spaces, indicating that there is a switch in the center of room $(X_i, Y_i)$. The $K$ pairs $(X_1, Y_1), (X_2, Y_2), \ldots, (X_K, Y_K)$ are all distinct.

Output Format

Output an integer on a single line, representing the shortest time in minutes 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)$, output the integer $-1$ instead.

Sample Input and Output

Sample Input #1

3 2 1
1 2

Sample Output #1

4

Sample Input #2

3 2 1
2 1

Sample Output #2

-1

Sample Input #3

8 9 15
3 1
3 2
3 7
3 8
1 1
4 5
4 3
5 6
5 8
6 3
6 2
7 5
8 9
8 6
8 5

Sample Output #3

25

Notes/Hints

Task

Given the size of the mansion $M$, $N$ and the positions of the $K$ rooms with switches $(X_1, Y_1), (X_2, Y_2), \ldots, (X_K, Y_K)$, write a program to determine the shortest time in minutes to move from the center of room $(1, 1)$ to the center of room $(M, N)$, starting with all doors connecting rooms adjacent in the east-west direction closed and all doors connecting rooms adjacent in the north-south direction open. If it is impossible to reach room $(M, N)$, indicate this.

Constraints

$2 \leq M \leq 100,000$ (number of rooms in the east-west direction)
$2 \leq N \leq 100,000$ (number of rooms in the north-south direction)
$1 \leq K \leq 200,000$ (number of rooms with switches)
$1 \leq X_i \leq M$ (east-west position of the room with a switch)
$1 \leq Y_i \leq N$ (north-south position of the room with a switch)

Grading Criteria

For 20% of the scoring data, $M \leq 1,000$ and $N \leq 1,000$.

For 30% of the scoring data, $K \leq 2,000$.

For 50% of the scoring data, at least one of the above two conditions is satisfied. There is no scoring data that satisfies both conditions.

见题面 Input 部分

见题面 Output 部分