2763 「JOI 2013 Final」现代豪宅

题目译自 JOI 2013 Final T3「現代的な屋敷」

你在某个很大的豪宅里迷路了。这个豪宅由东西方向 $ M $ 列，南北方向 $ N $ 行的正方形房间组成。从西面开始第 $ x $ 列 $ (1 \leq x \leq M) $ ，从南面开始第 $ y $ 行 $ (1 \leq y \leq N) $ 的房间用 $ (x,y) $ 表示。

相邻的两个房间之间都有一扇门。对于每扇门，门关上表示不可通行，门打开表示可以通行。当门打开时，从门一边的房间走到另一边的房间需要 $ 1 $ 分钟。另外，一些房间中有一个开关，如果连续 $ 1 $ 分钟按住这个开关，那么所有关上的门会打开，所有打开的门会关闭。

现在，连接东西两个房间的门全都是关上的，连接南北两个房间的门全都是打开的。你现在在房间 $ (1,1) $ ，要在最短时间内移动到房间 $ (M,N) $ 。

任务

给出豪宅的大小 $ M,N $ ，以及存在开关的 $ K $ 个房间的位置 $ (X_1,Y_1),(X_2,Y_2), \ldots ,(X_K,Y_K) $ 。开始时，连接东西两个房间的门全都是关上的，连接南北的两个房间全都是打开的。请编写程序求出从房间 $ (1,1) $ 移动到房间 $ (M,N) $ 最少需要多少时间。不过，当房间 $ (M,N) $ 不能到达时，请输出 $ -1 $ 。

输入标准如下： - 第一行为三个以空格分开的整数 $ 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),...,(X_K,Y_K) $ 间彼此相异。

输出一行一个整数：表示移动所需的最短时间。如果不能到达房间 $ (M,N) $ 则输出 $ -1 $ 。

对于此样例，可以通过以下的行动来在 $ 4 $ 分钟之内从房间 $ (1,1) $ 到达房间 $ (3,2) $ 。这是最短用时。 1. 移动到房间 $ (1,2) $ 。 1. 在房间 $ (1,2) $ 中按住开关。 1. 移动到房间 $ (2,2) $ 。 1. 移动到房间 $ (3,2) $ 。

以上行动可以用下图表示。图中向右为东，向上为北。图中的 $ × $ 图案表示你所在的位置， $ ○ $ 图案表示开关的位置。

对于此样例，不能到达房间 $ (3,2) $ 。

初始状态：

请注意：房间 $ (1,1) $ 和房间 $ (M,N) $ 中也可能存在开关。

对于所有数据，$ 2 \leq M, N \leq 10^5,$ $ 1 \leq K \leq 2×10^5,$ $ 1 \leq X_i \leq M,$ $ 1 \leq Y_i \leq N$。