F. Armor and Weaponstime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputMonocarp 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? InputThe 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.OutputPrint one integer — the minimum number of hours Monocarp has to spend to obtain both the n-th armor set and the m-th weapon.ExamplesInput
3 4
0
Output
3
Input
3 4
2
1 1
1 3
Output
2
NoteIn the first example, Monocarp can obtain the strongest armor set and the strongest weapon as follows:  Obtain the 2-nd weapon using the 1-st armor set and the 1-st weapon;  Obtain the 3-rd armor set using the 1-st armor set and the 2-nd weapon;  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:  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);  Obtain the 4-th weapon using the 3-rd armor set and the 1-st weapon. 
3 4
0

3 
['brute force', 'dp', 'greedy', 'shortest paths', '*2800']