题目描述

Okabe 喜欢沿着有路灯的小路穿行城市。但是如果沿途的路灯没有点亮，在一片漆黑中，他就会被他那些跑得超级快的小伙伴抛弃。

Okabe 居住的苟城可以用一个二维网格表示。行从上到下编为 $1\sim N$，列从左到右编为 $1\sim N$。有 $K$ 盏路灯是亮着的。初始时左上角的路灯已点亮。

Okabe 开始了他的旅程。他从左上角出发，目的地是右下角。当然，Okabe 只会经过点亮的灯，而且只能向相邻的上、下、左、右单元走。然而，Okabe 也可以支出 $1\tt\ s$ 的寿命来暂时点亮某一行或某一列的灯，从而通过一些最初没有点亮的区域。

值得注意的是，Okabe 在同一时间内只能点亮某一行或某一列的路灯，且在每次点亮新的行列时都必须重新 $-1\tt s$。要更改临时点亮的行和列时，他必须站在一开始就亮着的地方。而当他更改时，被点亮的一整行或一整列灯会同时熄灭。

由于 Okabe 的寿命是有限的，请帮助 Okabe 找出最少需要支出多少寿命来完成这次旅行。

输入格式

第一行包括三个整数 $n$、$m$、$k$，中间用空格隔开。$2 ≤ n, m, k ≤ 10^4$。

接下来的 $k$ 行，每行有两个整数 $r_i$ 和 $c_i\ (1 ≤ r_i ≤ n, 1 ≤ c_i ≤ m)$，表示初始时已经点亮的灯的行和列。

保证每个被点亮的灯的坐标不重合，且左上角的灯一定是亮的。

输出格式

输出 Okabe 到达目的地需要支出的最少寿命。如果不可能到达，输出 $-1$。

4 4 5
1 1
2 1
2 3
3 3
4 3

2

5 5 4
1 1
2 1
3 1
3 2

-1

2 2 4
1 1
1 2
2 1
2 2

0

5 5 4
1 1
2 2
3 3
4 4

3