Pişiklərinizi qoruyun#3543
Nicholas Y. Alford pişikləri çox sevirdi. Onun kənddə bir bağı var idi və burada çoxlu pişik saxlayırdı. Pişiklər o qədər şirin idilər ki, kənddəki insanlar da onları sevirdilər.
Bir gün, pis bir cadugər kəndə gəldi. O, pişiklərin hər kəs tərəfindən sevilməsinə paxıllıq etdi. Bağında sehrli dirəklər basdırdı və dirəklər arasında uzanan sehrli hasarlarla pişikləri əhatə etdi. O dedi: "Pişiklər çirkin qoca pişiklərə çevrilənə qədər hasarların içində qapalıdır." bir lənət kimi və getdi.
Nicholas hasarları çəkiclə qırmağa çalışdı, amma hasarlar onun səylərinə qarşı keçilməz idi. O, kilsəyə getdi və bir keşişdən kömək istədi. Keşiş kitabları araşdırdı və sehrli hasarların müqəddəs su ilə məhv edilə biləcəyini tapdı. Hasarı məhv etmək üçün lazım olan müqəddəs suyun miqdarı hasarın uzunluğuna mütənasib idi. Lakin, müqəddəs su olduqca bahalı idi. Buna görə də, o, bütün pişiklərini xilas etmək üçün lazım olan minimum müqəddəs su miqdarını almağa qərar verdi. Nə qədər müqəddəs su tələb olunacaq?
Giriş aşağıdakı formatda verilmişdir:
N M x_1 y_1 ...: x_N y_N p_1 q_1 ... p_M q_M
Girişin ilk sətri iki tam ədəd N (2 ≤ N ≤ 10000) və M (1 ≤ M) ehtiva edir. N sehrli dirəklərin sayını, M isə sehrli hasarların sayını göstərir. Növbəti N sətir dirəklərin koordinatlarını təsvir edir. Hər sətir iki tam ədəd x_i və y_i (-10000 ≤ x_i, y_i ≤ 10000) ehtiva edir. Növbəti M sətir hasarların hər iki ucunu təsvir edir. Hər sətir iki tam ədəd p_j və q_j (1 ≤ p_j, q_j ≤ N) ehtiva edir. Bu, hasarın p_j-ci dirək ilə q_j-ci dirək arasında uzandığını göstərir.
Aşağıdakıları qəbul edə bilərsiniz:
Heç bir dirək eyni koordinatlara malik deyil.
Bir dirək hasarın ortasında yerləşmir.
Heç bir hasar bir-birini kəsmir.
Hər qapalı sahədə ən azı bir pişik var.
Hasarı qismən məhv etmək mümkün deyil.
Sehrli hasarın bir vahid uzunluğunu məhv etmək üçün bir vahid müqəddəs su tələb olunur.
Bütün pişiklərini xilas etmək üçün lazım olan minimum müqəddəs su miqdarını ehtiva edən bir sətir çıxarın. Proqramınız ondalık nöqtədən sonra istənilən sayda rəqəm çıxara bilər. Lakin, mütləq səhv 0.001 və ya daha az olmalıdır.
Nümunə 1
Nümunə 2
Nümunə 3
Nümunə 4