Problem Description

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.

Input Format

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 Format

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$.

3 2 1
1 2

4

3 2 1
2 1

-1

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

25

Hint

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