← 返回题目列表

Codeforces · 821/D

D. 冈部和城市

中文机器翻译题面 查看原题

冈部喜欢在路灯照亮的小路上漫步穿过他的城市。这样他就不会被小学生殴打。

冈部的城市由二维单元格表示。行从上到下编号为 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).