#P1612F. Armor and Weapons
Armor and Weapons
Description
Monocarp plays a computer game. There are different sets of armor and different weapons in this game. If a character equips the -th set of armor and wields the -th weapon, their power is usually equal to ; but some combinations of armor and weapons synergize well. Formally, there is a list of ordered pairs, and if the pair belongs to this list, the power of the character equipped with the -th set of armor and wielding the -th weapon is not , but .
Initially, Monocarp's character has got only the -st armor set and the -st weapon. Monocarp can obtain a new weapon or a new set of armor in one hour. If he wants to obtain the -th armor set or the -th weapon, he must possess a combination of an armor set and a weapon that gets his power to 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 -th armor set and the -th weapon. What is the minimum number of hours he has to spend on it?
The first line contains two integers and () — the number of armor sets and the number of weapons, respectively.
The second line contains one integer () — the number of combinations that synergize well.
Then lines follow, the -th line contains two integers and (; ) meaning that the -th armor set synergizes well with the -th weapon. All pairs are distinct.
Print one integer — the minimum number of hours Monocarp has to spend to obtain both the -th armor set and the -th weapon.
Input
The first line contains two integers and () — the number of armor sets and the number of weapons, respectively.
The second line contains one integer () — the number of combinations that synergize well.
Then lines follow, the -th line contains two integers and (; ) meaning that the -th armor set synergizes well with the -th weapon. All pairs are distinct.
Output
Print one integer — the minimum number of hours Monocarp has to spend to obtain both the -th armor set and the -th weapon.
Samples
Note
In the first example, Monocarp can obtain the strongest armor set and the strongest weapon as follows:
- Obtain the -nd weapon using the -st armor set and the -st weapon;
- Obtain the -rd armor set using the -st armor set and the -nd weapon;
- Obtain the -th weapon using the -rd armor set and the -nd weapon.
In the second example, Monocarp can obtain the strongest armor set and the strongest weapon as follows:
- Obtain the -rd armor set using the -st armor set and the -st weapon (they synergize well, so Monocarp's power is not but );
- Obtain the -th weapon using the -rd armor set and the -st weapon.