Armor and Weapons
Description
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.
Input
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.
Output
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.
Samples
3 4
0
3
3 4
2
1 1
1 3
2
Note
In 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.