write a go solution for 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?

Input Format:
The first line contains two integers n and m (2<=n,m<=2*10^5) — the number of armor sets and the number of weapons, respectively.

The second line contains one integer q (0<=q<=min(2*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<=a_i<=n; 1<=b_i<=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 Format:
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.

Note:
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.. Output only the code with no comments, explanation, or additional text.