Armor and Weapons
Contest: Educational Codeforces Round 117 (Rated for Div. 2)
Difficulty rating: 2800
Tags: brute force, dp, greedy, shortest paths

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 \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 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.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

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.

Example input:
3 4
0

Example output:
3

Example input:
3 4
2
1 1
1 3

Example output:
2

Editorial:
Among two armor sets, one with the greater index is always better. The same can be said about two different weapons. So, it is always optimal to use and obtain the best possible weapon or armor.
This observation allows us to model this problem with dynamic programming or shortest paths: let $$$dp_{x,y}$$$ be the minimum time in which Monocarp can obtain the armor $$$x$$$ and the weapon $$$y$$$; and in each transition, we either get the best weapon we can or the best armor we can. Similarly, we can build a graph where the vertices represent these pairs $$$(x, y)$$$, and the edges represent getting the best possible weapon/armor, and find the shortest path from $$$(1, 1)$$$ to $$$(n, m)$$$ using BFS.
Unfortunately, it is $$$O(nm)$$$. But we can modify the BFS in the following fashion: let's analyze each layer of BFS (a layer is a set of vertices with the same distance from the origin). In each layer, there might be some redundant vertices: if two vertices $$$(x, y)$$$ and $$$(x', y')$$$ belong to the same layer, $$$x' \le x$$$ and $$$y' \le y$$$, then the vertex $$$(x', y')$$$ is redundant.
If we filter each layer, removing all redundant vertices from it and continuing BFS only from non-redundant ones, the solution will be fast enough. To prove it, let's analyze the constraints on the answer. Suppose $$$n \ge m$$$. The answer can be bounded as $$$O(\log m + \frac{n}{m})$$$, since we can reach the pair $$$(m, m)$$$ in $$$O(\log m)$$$ steps using something similar to Fibonacci sequence building, and then go from $$$(m, m)$$$ to $$$(n, m)$$$ in $$$\frac{n}{m}$$$ steps. And the number of non-redundant states on each layer is not greater than $$$m$$$ (because, of two states with the same weapon or the same armor set, at least one is redundant). So, if we don't continue BFS from redundant vertices, it will visit at most $$$O(m \cdot (\log m + \frac{n}{m})) = O(m \log m + n)$$$ vertices. There might be another logarithm in the asymptotic complexity of the solution, if you use something like a set to store all combinations that synergize well, but this implementation is still fast enough.