配点: 100 点
你走进了一座大宅邸。这座宅邸的房间呈方形,呈南北、东西方格子状排列。 M 柱,南北方向 N 行总计 它具有 M \times N 块排列的结构。从西边来 x 列目 (1 \leqq x \leqq M),从南边 y 行目 (1 \leqq y \leqq N) 由 (x, y) 代表。
毗邻北、南、东、西 2 房间由墙中央的门连接。每扇门要么关闭且无法通行,要么打开且可通行。当门打开时在房间的中心之间移动。 需要 1 分钟。另外,部分房间中央设有开关; 1 如果按住它一分钟,宅邸中的所有门都会在打开和关闭状态之间切换。
现在东西相邻 2 连接房间的门全部关闭,南北相邻。 2 连接房间的所有门都打开。你现在在房间里 (1, 1) 在房间中央 我想在最短的时间内移动到 (M, N) 的中心。
課題
豪宅的大小 M, N 并带有开关 K 房间位置 给出 (X_1, Y_1), (X_2, Y_2), \ldots, (X_K, Y_K) 。东边和西边毗邻 2 连接房间的门全部关闭,南北相邻。 2 首先打开所有连接房间的门,并且 (1, 1) 从房间的中心 编写一个程序,求移动到 (M, N) 中心所需的最少分钟数。不过,房间 如果您无法到达 (M, N) ,请指出。
制限
| 2 \leqq M \leqq 100\,000 | 豪宅东西方向房间数 |
| 2 \leqq N \leqq 100\,000 | 宅邸南北方向房间数 |
| 1 \leqq K \leqq 200\,000 | 有开关的房间数量 |
| 1 \leqq X_i \leqq M | 有开关房间的东西位置 |
| 1 \leqq Y_i \leqq N | 有开关房间的南北位置 |
入力
从标准输入读取以下数据。
- 1 行包含一个整数 M, N, K 以空格作为分隔符。M 是豪宅东西方向的房间数,N 是豪宅南北方向的房间数,K 代表有开关的房间数量。
- 继续 K 行 i 行目 (1 \leqq i \leqq K) 是一个整数 X_i, Y_i 以空格作为分隔符。这是房间 (X_i, Y_i) 表示中央有一个开关。K 一套 (X_1, Y_1), (X_2, Y_2), \ldots, (X_K, Y_K) 彼此不同。
出力
指示移动所需的最小分钟数的整数被发送到标准输出。 输出为 1 行。不过,房间 如果无法达到 (M, N) ,则改为整数 输出 -1 。
採点基準
评分数据中,分配的分数 20 对于%,M \leqq 1\,000,N \leqq 1\,000 很满意。
评分数据中,分配的分数 30 对于%,K \leqq 2\,000 很满意。
评分数据中,分配的分数 50 对于 %,这些 2 至少满足以下条件之一。还有,这些 2 没有满足这两个条件的评分数据。
入力例 1
3 2 1 1 2
出力例 1
4
在此示例中,执行以下操作 4 几分钟内即可到达房间 您可以移动到 (1, 1) 从房间的中心 编写一个程序,求移动到 (3, 2) 的中心,这是最短的。 移至
- 部屋 (1, 2) 的中心。 按下
- 部屋 (1, 2) 中心的开关。
- 部屋 (2, 2) 的中心。 按下
- 部屋 (3, 2) 的中心。 按下
此时豪宅的状态如下图所示。图中,右侧方向为东,上方方向为北,x 标记代表您的位置,○ 标记代表开关。

入力例 2
3 2 1 2 1
出力例 2
-1
在此示例中,您在房间中 无法到达 (3, 2) 。
入力例 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
出力例 3
25
在这个例子中,第一座豪宅如下图所示。房间 (1, 1) 和房间 (M, N) 中间可能有一个开关。
