Правительство квадратной страны решило подзаработать на транзитных железнодорожных перевозках. На новую железнодорожную сеть выделили деньги, и стройка началась. Как обычно, пропускной способностью сети озаботились только после завершения проекта. Помогите правительству определить максимальную длину поезда, который может проехать транзитом через квадратную страну.
Квадратная страна имеет ширину $$$x_{max}$$$ ($$$1 \leq x_{max} \leq 10^4$$$) и длину $$$y_{max}$$$ ($$$1 \leq y_{max} \leq 10^4$$$). Железнодорожная сеть состоит из $$$n$$$($$$1 \leq n \leq 10^4$$$) стрелок и двух таможен, которые соединены $$$m$$$ ($$$1 \leq m \leq 30000$$$) прямыми отрезками железной дороги. Координаты стрелок $$$(x_i, y_i)$$$ – целые числа, координаты таможенных пунктов $$$(s, 0)$$$ $$$(t, y_{max})$$$ также целые, и лежат на противоположных границах. Отрезки железной дороги соединяют только стрелки (и таможенные пункты), и не пересекаются в других точках. Координаты всех стрелок и таможенных пунктов различны.
Через отрезок железной дороги между двумя стрелками может проследовать поезд длины не превосходящий длину этого отрезка. Длина отрезка дороги, соединяющего две стрелки (или таможни) – это расстояние между точками на плоскости. Длина поезда – это количество вагонов в нем. Все вагоны одинаковы, и имеют длину $$$1$$$. Таким образом, через отрезок длины $$$4.5$$$ может проехать поезд не более чем из $$$4$$$ вагонов, а через через отрезок длины $$$10$$$ – не более $$$10$$$ вагонов.
Поезд может двигаться по железной дороге в любом направлении. Более того, он может в произвольный момент остановиться и сменить направление движения на противоположное. Поезд не может занимать одновременно более чем одну стрелку (но может касаться их своими концами). При прохождении стрелки, состав не может отклониться более чем на $$$60$$$ градусов от прежнего направления движения (то есть, поезд не может изгибаться произвольно – угол между соседними вагонами не может быть острее $$$120$$$ градусов).
Используя карту железных дорог квадратной страны определите максимальную длину состава, который может проследовать между двумя таможнями. Предполагается, что из-за границы государства поезд может выехать на любой путь, смежный с таможенным пунктом.
Первая строка содержит $$$2$$$ целых числа - размеры страны $$$x_{max}$$$ ($$$1 \leq x_{max} \leq 10^4$$$) и $$$y_{max}$$$ ($$$1 \leq y_{max} \leq 10^4$$$).
Вторая строка содержит целые $$$x$$$-координаты таможен $$$s$$$ и $$$t$$$ ($$$0 \leq s, t \leq x_{max} $$$).
Третья строка содержит $$$2$$$ целых – число стрелок $$$n$$$ ($$$1 \leq n \leq 10^4$$$) и число отрезков железных дорог $$$m$$$ ($$$1 \leq m \leq 30000$$$).
Далее следуют $$$n$$$ строк с парами целых $$$x_i$$$ и $$$y_i$$$ ($$$0 \leq x_i \leq x_{max}; 0 \leq y_i \leq y_{max} $$$) – координаты стрелок.
За ними следуют $$$m$$$ строк, описывающих отрезки железной дороги. Каждый отрезок описывается парой целых $$$u_i$$$ и $$$v_i$$$ ($$$0 \leq u_i, v_i \leq n + 1$$$) – номерами соединяемых стрелок. Стрелки нумеруются числами от $$$1$$$ до $$$n$$$ в порядке появления во входных данных. Таможня с координатами $$$(s, 0)$$$ имеет номер $$$0$$$, а таможня с координатами $$$(t, y_{max})$$$ номер $$$n + 1$$$. Отрезки железной дороги не пересекаются, и не имеют общих точке кроме стрелок (или таможен). Отрезок не может соединять стрелку саму с собой. Две стрелки не могут быть соединены более одного раза.
Выведите $$$0$$$, если никакой поезд не может проехать между таможнями. В противном случае выведите целое число – максимальное количество вагонов в транзитном поезде.
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
