The government of the square country decided to earn extra money on transit rail transportation. Money was allocated for the new railway network, and the construction began. Typically, the network bandwidth was not considered until after the completion of the project. Help the government determine the maximum train length that can transit a square country.
A square country has a width of $$$x_{max}$$$ ($$$1 \leq x_{max} \leq 10^4$$$) and a length of $$$y_{max}$$$ ($$$1 \leq y_{max} \leq 10^4$$$). The railway network consists of $$$n$$$($$$1 \leq n \leq 10^4$$$) switches and two customs houses, which are connected by $$$m$$$ ($$$1 \leq m \leq 30000$$$) straight railway segments. The coordinates of the switches $$$(x_i, y_i)$$$ are integers, the coordinates of the customs points $$$(s, 0)$$$ and $$$(t, y_{max})$$$ are also integers, and lie on the opposite borders. Sections of the railway road are connected only in switch points (and customs points), and do not intersect at other points. The coordinates of all switches and customs points are different figures.
Through a segment of the railway road, between two switches, a train of length not exceeding the length of this same segment of road can easily pass. The length of the road segment connecting two switches (or customs) is the distance between points on the plane. The length of a train is the number of wagons in it. All cars are the same and have a length of $$$1$$$. Thus, a train of no more than $$$4$$$ cars can pass through a segment of length $$$4.5$$$, and no more than $$$10$$$ cars can pass through a segment of length $$$10$$$.
The train can move along the railroad in any direction. Moreover, it can stop at any moment and change the direction of movement for the opposite. The train cannot occupy more than one switch at a time (but can touch them at its ends). When passing the switch point, the train cannot deviate for more than $$$60$$$ degrees from the previous direction of movement (that is, the train cannot bend arbitrarily – the angle between adjacent cars cannot be sharper than $$$120$$$ degrees).
Using the map of the railways of a square country, determine the maximum length of the train, which can go between two customs. It is assumed that from abroad, the train can leave on any track adjacent to the customs point.
The first line contains $$$2$$$ integers - the country sizes $$$x_{max}$$$ ($$$1 \leq x_{max} \leq 10^4$$$) and $$$y_{max}$$$ ($$$1 \leq y_{max} \leq 10^4$$$).
The second line contains the integer $$$x$$$-coordinates of customs $$$s$$$ and $$$t$$$ ($$$0 \leq s, t \leq x_{max} $$$).
The third line contains $$$2$$$ integers – the number of switches $$$n$$$ ($$$1 \leq n \leq 10^4$$$) and the number of railway segments $$$m$$$ ($$$1 \leq m \leq 30000$$$).
Then come $$$n$$$ lines with integer pairs $$$x_i$$$ and $$$y_i$$$ ($$$0 \leq x_i \leq x_{max}; 0 \leq y_i \leq y_{max} $$$) - coordinates of arrows.
They are followed by $$$m$$$ lines describing the railway sections. Each segment is described by a pair of integers $$$u_i$$$ and $$$v_i$$$ ($$$0 \leq u_i, v_i \leq n + 1$$$) – the numbers of the connected switch points. The switches are numbered from $$$1$$$ to $$$n$$$ in the order they appear in the input. Customs office with coordinates $$$(s, 0)$$$ has number $$$0$$$, and customs office with coordinates $$$(t, y_{max})$$$ has number $$$n + 1$$$.
Sections of the railroad do not intersect, and do not have a common point other than switches (or customs). The segment cannot connect the switch onto itself. Two switches cannot be connected more than once.
If no train can pass between customs, output $$$0$$$. Otherwise, type an integer – the maximum number of cars in a train.
6 16 0 0 4 5 0 4 3 8 0 12 6 8 0 1 1 2 2 3 3 5 2 4
3
| Name |
|---|