Your brother, who recently broke his leg, needs to take the subway from your house to the pharmacy to get his prescription of pain medication.

This subway system is made of ~L~ lines running across the city, numbered ~1~ through ~L~. Your brother can freely travel from one spot on one line to any other spot on the same line. However, your house and the pharmacy are not on the same subway line, so your brother is going to need to change lines.

Changing lines requires going up or down a floor in a subway station. Unfortunately, due to your brother's broken leg, he needs the assistance of an escalator to change lines. Not every line changing station is built with escalators, and some line changing stations only have escalators going in one direction (i.e. for example, it may be possible to go from Line ~1~ to Line ~5~, but not from Line ~5~ to Line ~1~ using escalators).

As a regular subway user, you have recorded the availability of escalators on the subway system. For example, you may have recorded that there is an escalator allowing a line change from somewhere on Line ~1~ to somewhere on Line ~5~ (the actual position on the lines doesn't matter). There may be multiple escalators connecting one line to another.

Please find the least number of line changes your brother must make to get to the pharmacy. (Don't worry about travel times or anything like that, just minimize the number of line changes based on the available escalators to get from the house to the pharmacy). It is guaranteed that your brother is able to make it to the pharmacy.

Note: It is not required (and not possible given the information provided) to visualize the actual layout of the subway system to solve the problem. You only need to know which line changes are possible to make.

Input Specification

The first line of input will contain ~4~ space-separated integers. The first integer, ~L~ ~(2 \le L \le 1000)~, is the number of lines (numbered ~1~ through ~L~). The second integer is the subway line that your brother's house is on. The third integer is the subway line that the pharmacy is on. The fourth integer, ~N~ ~(1 \le N \le 5000)~, is the number of escalators across the subway system connecting different lines.

The next ~N~ lines of input contain two space-separated integers. Each pair of integers represents an escalator, connecting the subway line denoted by the first integer to the subway line denoted by the second integer, and in that direction only.

Output Specification

Output one integer, the least number of line changes your brother needs to do to get to the pharmacy.

Constraints

• For 3 of 10 marks, ~N < 100~ and ~L < 100~
• For the remaining 7 marks, there are no additional constraints

Sample Input

8 1 6 9
1 2
2 3
1 4
4 7
7 8
3 2
8 6
3 5
6 5

Sample Output

4

Explanation for Sample Output

Your brother starts on Line 1. In order to reach the pharmacy on Line 6, he can take this path:

Line 1 -> Line 4 -> Line 7 -> Line 8 -> Line 6

This path requires four transfers. It is easy to see that this path requires the least number of transfers.