说明

你误入了一座巨大的宅邸。这座宅邸由正方形的房间在东西南北方向上呈网格状排列构成，东西方向有 $M$ 列，南北方向有 $N$ 行，总计 $M \times N$ 个房间。用 $(x, y)$ 表示西起第 $x$ 列 ($1 \leq x \leq M$)，南起第 $y$ 行 ($1 \leq y \leq N$) 的房间。

在东西南北方向上相邻的两个房间之间，由位于墙壁中央的门连接。每扇门要么处于关闭且无法通行的状态，要么处于打开且可以通行的状态。当门打开时，在这些房间的中央之间移动需要花费 1 分钟。此外，一些房间的中央设有开关，持续按住开关 1 分钟，宅邸内所有门的开闭状态就会切换。

目前，连接东西相邻两个房间的所有门都是关闭的，连接南北相邻两个房间的所有门都是打开的。你现在位于房间 $(1, 1)$ 的中央，想要以最短的时间移动到房间 $(M, N)$ 的中央。

任务

给定宅邸的大小 $M, N$ 以及设有开关的 $K$ 个房间的位置 $(X_1, Y_1), (X_2, Y_2), \dots, (X_K, Y_K)$。从连接东西相邻房间的所有门关闭、连接南北相邻房间的所有门打开的状态开始，求出从房间 $(1, 1)$ 中央移动到房间 $(M, N)$ 中央所需的最短时间（以分钟为单位）。如果无法到达房间 $(M, N)$，请指出这一点。

输入格式

从标准输入读取以下数据。

• 第一行包含三个用空格分隔的整数 $M, N, K$。$M$ 表示宅邸东西方向的房间数，$N$ 表示宅邸南北方向的房间数，$K$ 表示设有开关的房间数。
• 接下来的 $K$ 行中，第 $i$ 行 ($1 \leq i \leq K$) 包含两个用空格分隔的整数 $X_i, Y_i$。这表示房间 $(X_i, Y_i)$ 的中央有一个开关。$K$ 个二元组 $(X_1, Y_1), (X_2, Y_2), \dots, (X_K, Y_K)$ 彼此不同。

输出格式

向标准输出输出一行，包含一个整数，表示移动所需的最短分钟数。如果无法到达房间 $(M, N)$，则输出整数 $-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

提示

样例解释 1

在这个例子中，可以通过以下行动在 4 分钟内从房间 $(1, 1)$ 中央移动到房间 $(3, 2)$ 中央，这是最短时间。

1. 移动到房间 $(1, 2)$ 的中央。
2. 按下房间 $(1, 2)$ 中央的开关。
3. 移动到房间 $(2, 2)$ 的中央。
4. 移动到房间 $(3, 2)$ 的中央。

此时的宅邸状态如下图所示。图中右方向为东，上方向为北，× 标记表示你的位置，○ 标记表示开关。

:::align{center} :::

样例解释 2

在这个例子中，你无法到达房间 $(3, 2)$。

样例解释 3

在这个例子中，初始的宅邸状态如下图所示。请注意，房间 $(1, 1)$ 或房间 $(M, N)$ 的中央也可能有开关。

:::align{center} :::

限制

$2 \leq M \leq 100\,000$　宅邸东西方向的房间数
$2 \leq N \leq 100\,000$　宅邸南北方向的房间数
$1 \leq K \leq 200\,000$　设有开关的房间数
$1 \leq X_i \leq M$　设有开关的房间的东西方向位置
$1 \leq Y_i \leq N$　设有开关的房间的南北方向位置

评分标准

在评分数据中，占分值 20% 的部分满足 $M \leq 1000$, $N \leq 1000$。
在评分数据中，占分值 30% 的部分满足 $K \leq 2000$。
在评分数据中，占分值 50% 的部分满足上述两个条件中的至少一个。此外，不存在同时满足这两个条件的评分数据。

翻译由 DeepSeek V3.2 完成