Armor and Weapons

题意翻译

有 $ n $ 套不同的盔甲和 $ m $ 种不同的武器。 有一个列表，包含 $q$ 对装备 $ (i, j) $ ，每对包含一套盔甲和一种武器。 对于盔甲 $i$ 和武器 $j$ ： - 若 $ (i, j) $ 出现在列表中，则它们产生的 power 为 $i+j+1$ . - 否则，产生的 power 为 $i+j$ . 起初，具有的装备为 盔甲 $1$ 和武器 $1$ 。如果想要获得盔甲 $k$ 或武器 $k$ ,必须从具有的装备中找出一套盔甲和一件武器 $(i,j)$ ，满足 $(i,j)$ 的 power 至少为 $k$ 。通过这种方式，每获得一套盔甲或一件武器，花费一小时。 新获得的盔甲或武器可以再用来获取其他盔甲或武器，当然，也可以用旧的获取。 求出获得盔甲 $n$ 和武器 $m$ ，所用的最小时间。

题目描述

Monocarp plays a computer game. There are $ n $ different sets of armor and $ m $ different weapons in this game. If a character equips the $ i $ -th set of armor and wields the $ j $ -th weapon, their power is usually equal to $ i + j $ ; but some combinations of armor and weapons synergize well. Formally, there is a list of $ q $ ordered pairs, and if the pair $ (i, j) $ belongs to this list, the power of the character equipped with the $ i $ -th set of armor and wielding the $ j $ -th weapon is not $ i + j $ , but $ i + j + 1 $ . Initially, Monocarp's character has got only the $ 1 $ -st armor set and the $ 1 $ -st weapon. Monocarp can obtain a new weapon or a new set of armor in one hour. If he wants to obtain the $ k $ -th armor set or the $ k $ -th weapon, he must possess a combination of an armor set and a weapon that gets his power to $ k $ or greater. Of course, after Monocarp obtains a weapon or an armor set, he can use it to obtain new armor sets or weapons, but he can go with any of the older armor sets and/or weapons as well. Monocarp wants to obtain the $ n $ -th armor set and the $ m $ -th weapon. What is the minimum number of hours he has to spend on it?

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 2 \le n, m \le 2 \cdot 10^5 $ ) — the number of armor sets and the number of weapons, respectively. The second line contains one integer $ q $ ( $ 0 \le q \le \min(2 \cdot 10^5, nm) $ ) — the number of combinations that synergize well. Then $ q $ lines follow, the $ i $ -th line contains two integers $ a_i $ and $ b_i $ ( $ 1 \le a_i \le n $ ; $ 1 \le b_i \le m $ ) meaning that the $ a_i $ -th armor set synergizes well with the $ b_i $ -th weapon. All pairs $ (a_i, b_i) $ are distinct.

输出格式

Print one integer — the minimum number of hours Monocarp has to spend to obtain both the $ n $ -th armor set and the $ m $ -th weapon.

输入输出样例

输入样例 #1

3 4
0

输出样例 #1

3

输入样例 #2

3 4
2
1 1
1 3

输出样例 #2

2

说明

In the first example, Monocarp can obtain the strongest armor set and the strongest weapon as follows: 1. Obtain the $ 2 $ -nd weapon using the $ 1 $ -st armor set and the $ 1 $ -st weapon; 2. Obtain the $ 3 $ -rd armor set using the $ 1 $ -st armor set and the $ 2 $ -nd weapon; 3. Obtain the $ 4 $ -th weapon using the $ 3 $ -rd armor set and the $ 2 $ -nd weapon. In the second example, Monocarp can obtain the strongest armor set and the strongest weapon as follows: 1. Obtain the $ 3 $ -rd armor set using the $ 1 $ -st armor set and the $ 1 $ -st weapon (they synergize well, so Monocarp's power is not $ 2 $ but $ 3 $ ); 2. Obtain the $ 4 $ -th weapon using the $ 3 $ -rd armor set and the $ 1 $ -st weapon.