NC53184. 现代豪宅
描述
题目译自 JOI 2013 Final T3「現代的な屋敷」
你在某个很大的豪宅里迷路了。这个豪宅由东西方向M列，南北方向N行的正方形房间组成。从西面开始第x列)
，从南面开始第y行)
的房间用(x,y)表示。
相邻的两个房间之间都有一扇门。对于每扇门，门关上表示不可通行，门打开表示可以通行。当门打开时，从门一边的房间走到另一边的房间需要1分钟。另外，一些房间中有一个开关，如果连续1分钟按住这个开关，那么所有关上的门会打开，所有打开的门会关闭。
现在，连接东西两个房间的门全都是关上的，连接南北两个房间的门全都是打开的。你现在在房间(1,1)，要在最短时间内移动到房间(M,N)。
任务
给出豪宅的大小M,N，以及存在开关的K个房间的位置%2C(X_2%2CY_2)%2C%20%5Cldots%2C(X_K%2CY_K))
。开始时，连接东西两个房间的门全都是关上的，连接南北的两个房间全都是打开的。请编写程序求出从房间(1,1)移动到房间(M,N)最少需要多少时间。不过，当房间(M,N)不能到达时，请输出-1。
相邻的两个房间之间都有一扇门。对于每扇门，门关上表示不可通行，门打开表示可以通行。当门打开时，从门一边的房间走到另一边的房间需要1分钟。另外，一些房间中有一个开关，如果连续1分钟按住这个开关，那么所有关上的门会打开，所有打开的门会关闭。
现在，连接东西两个房间的门全都是关上的，连接南北两个房间的门全都是打开的。你现在在房间(1,1)，要在最短时间内移动到房间(M,N)。
任务
给出豪宅的大小M,N，以及存在开关的K个房间的位置
输入描述
输入标准如下：
第一行为三个以空格分开的整数M,N,K。M表示东西方向上房间的个数，N表示南北方向上房间的个数，K表示存在开关的房间的个数。接下来K行中的第i行为两个以空格分开的整数
。表示房间
中存在开关。这K个二元组
间彼此相异。
输出描述
输出一行一个整数：表示移动所需的最短时间。如果不能到达房间(M,N)则输出-1。
示例1
输入:
3 2 1 1 2
输出:
4
说明:
对于此样例，可以通过以下的行动来在4分钟之内从房间(1,1)到达房间(3,2)。这是最短用时。移动到房间(1,2)。
在房间(1,2)中按住开关。
移动到房间(2,2)。
移动到房间(3,2)。
以上行动可以用下图表示。图中向右为东，向上为北。图中的×图案表示你所在的位置，○○图案表示开关的位置。
示例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)中也可能存在开关。