题目描述

你迷路闯入了一座巨大的宅邸。这座宅邸的结构是正方形的房间在东西南北方向上呈网格状排列，东西方向有 $M$ 列，南北方向有 $N$ 行，共有 $M \times N$ 个房间。从西往东数第 $x$ 列（$1 \le x \le M$）、从南往北数第 $y$ 行（$1 \le y \le N$）的房间表示为 $(x, y)$。

在东西南北方向上相邻的任意 $2$ 个房间之间，都由墙壁中央的一扇门相连。每扇门都处于关闭而无法通行的状态，或打开而可以通行的状态之一。当门打开时，在这些房间的中央之间移动需要花费 $1$ 分钟。此外，部分房间的中央设有一个开关，持续按住开关 $1$ 分钟，宅邸内所有门的开关状态都会反转。

现在，连接东西方向相邻的 $2$ 个房间的所有门都是关闭的，连接南北方向相邻的 $2$ 个房间的所有门都是打开的。你现在位于房间 $(1, 1)$ 的中央，希望用最短的时间移动到房间 $(M, N)$ 的中央。

任务

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

限制

• $2 \le M \le 100000$：宅邸在东西方向上的房间个数。
• $2 \le N \le 100000$：宅邸在南北方向上的房间个数。
• $1 \le K \le 200000$：设有开关的房间个数。
• $1 \le X_i \le M$：设有开关的房间在东西方向上的位置。
• $1 \le Y_i \le N$：设有开关的房间在南北方向上的位置。

输入格式

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

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

输出格式

向标准输出打印 $1$ 行，包含一个整数，表示移动所需的最少分钟数。但是，如果无法到达房间 $(M, N)$，则改为输出整数 $-1$。

评分标准

• 在占总分 $20\%$ 的评测数据中，满足 $M \le 1000$ 且 $N \le 1000$。
• 在占总分 $30\%$ 的评测数据中，满足 $K \le 2000$。
• 在占总分 $50\%$ 的评测数据中，至少满足上述 $2$ 个条件之一。此外，不存在同时满足上述 $2$ 个条件的评测数据。

样例 1

输入

3 2 1
1 2

输出

4

样例解释

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

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

此过程中宅邸的状态如下图所示。在图中，右方为东，上方为北，$\times$ 记号表示你的位置，$\bigcirc$ 记号表示开关。

样例 2

输入

3 2 1
2 1

输出

-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

输出

25

样例解释

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