题目描述

题目译自 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$ 。

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

数据范围与提示

对于所有数据，$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$。