冈部喜欢在路灯照亮的小路上漫步穿过他的城市。这样他就不会被小学生殴打。
冈部的城市由二维单元格表示。行从上到下编号为 1 到 n,列从左到右编号为 1 到 m。城市中正好有 k 个小区被路灯照亮。确保左上角的单元格被点亮。
Okabe 从左上角的单元格开始行走,并想要到达右下角的单元格。当然,冈部只会在发光的单元格上行走,并且他只能向上、下、左、右方向移动到相邻的单元格。然而,如果冈部支付 1 个硬币,他还可以一次暂时点亮任何单行或单列中的所有单元格,从而允许他走过一些最初未点亮的单元格。
请注意,Okabe 一次只能点亮一行或一列,并且每次点亮新的行或列时都必须支付一枚硬币。要更改暂时点亮的行或列,他必须站在最初点亮的单元格处。此外,一旦他从行或列中移除临时灯,该行/列中最初未点亮的所有单元格现在都不会点亮。
帮助冈部找到完成他的步行所需支付的最少硬币数量!
输入
输入的第一行包含三个空格分隔的整数 n、m 和 k (2 ≤ n、m、k ≤ 104)。
接下来的 k 行包含两个以空格分隔的整数 ri 和 ci (1 ≤ ri ≤ n, 1 ≤ ci ≤ m) - 第 i 个点亮单元的行和列。
保证所有 k 个点亮单元都是不同的。确保左上角的单元格被点亮。
输出
打印 Okabe 完成行走所需支付的最小硬币数量,如果不可能,则打印 -1。
示例
输入 #1
4 4 5 1 1 2 1 2 3 3 3 4 3
输出 #1
2
输入 #2
5 5 4 1 1 2 1 3 1 3 2
输出 #2
-1
输入 #3
2 2 4 1 1 1 2 2 1 2 2
输出 #3
0
输入#4
5 5 4 1 1 2 2 3 3 4 4
输出#4
3
注意
在第一个样本测试中,Okabe 可以采取路径 $$(1,1)\rightarrow(2,1)\rightarrow(2,3)\rightarrow(3,3)\rightarrow(4,3)\rightarrow(4,4)$$,仅在移动到 (2, 3) 和 (4, 4) 时付费。
在第四个样本中,Okabe 可以采取路径 $$(1,1)\rightarrow(1,2)\rightarrow(2,2)\rightarrow(3,2)\rightarrow(3,3)\rightarrow(4,4)\rightarrow(5,4)$$ $$\rightarrow (5,5)$$,移动到 (1, 2)、(3, 4) 和 (5, 4).