Boru təmizlənməsi
Linçepinqdə su nəqliyyat sistemi olduqca mürəkkəbdir. Linçepinqin ətrafında bir neçə quyu var və bu quyulardan su çıxarılır. Su, borular vasitəsilə digər yerlərə daşınır. Hər bir boru, quyulardan birindən şəhərin müəyyən bir yerinə gedən düz bir kanaldır.
Bütün borular yerin altında eyni dərinlikdə yerləşir. Buna görə də, iki boru kəsişəndə, onlar kəsişmə yaradır. Xoşbəxtlikdən, boru sistemi elə qurulub ki, hər belə kəsişmədə dəqiq iki boru qarşılaşır. Quyular kəsişmə hesab edilmir. Hər bir quyuya istənilən sayda boru (sıfır və ya daha çox iki daxil olmaqla) qoşula bilər.
Kəsişmələr problem yaradır, çünki kir (əhəng və digər elementlərin qarışığı "qalır") orada ilişib qalmağa meyllidir. Bu kir boruların çürüməsinə və dağılmasına səbəb olur, bu da böyük çuxurların yaranmasına gətirib çıxarır. Belə çuxurlar Linçepinqdə tələbələrə hipnoz təsiri göstərir, onları təhsillərini laqeyd etməyə və savadsız qalmağa məcbur edir ki, bu da nəinki boru sisteminin, həm də cəmiyyətin özünün strukturunun çökməsinə səbəb olacaq. Buna görə də boruları mütəmadi olaraq təmizləmək lazımdır. Linçepinqin su borularına cavabdeh olan Nordic Water Extraction and Redistribution Company (NWERC) bu vəzifəni yerinə yetirmək üçün kifayət qədər robot parkına malikdir. Robot borunun başladığı quyuda yerləşdirilə bilər. Sonra robot boru boyunca sonuna qədər gedir və yolda bütün kəsişmələri təmizləyir. Sonuna çatdıqda, robot geri dönür və başladığı quyudan geri qayıdır. Robotların toqquşmasının qarşısını almaq üçün hökumət qaydalarında nəzərdə tutulur ki, iki borunun kəsişməsində maksimum yalnız birindən robot keçə bilər.
Bütün su təchizatı sistemi təmizləmə zamanı söndürülməli olduğundan (başqa bir hökumət tənzimləməsi), NWERC bütün kəsişmələri təmizləmək üçün eyni vaxtda işə başlayan bir partiya təmizləyici robotlardan istifadə edərək işi tez bir zamanda bitirmək istəyir.
Siz yoxlamalısınız ki, bunu etmək mümkündürmü, yəni robotları elə bir boru dəstinə yerləşdirmək mümkündürmü ki, robotlar bütün kəsişmələri təmizləsin və iki robotun toqquşma riski olmasın.
Giriş Məlumatları
Aşağıdakılardan ibarətdir:
bir sıra iki ədəd w (1 ≤ w ≤ 1000) - quyu sayı və p (1 ≤ p ≤ 1000) - boru sayı;
w sətir, i-ci sətir iki tam ədəd
x[i]vəy[i](-10000 ≤x[i],y[i]≤ 10000) - i nömrəli quyunun mövqeyi (quyular 1-dən w-ə qədər nömrələnib);p sətir üç tam ədəd s (1 ≤ s ≤ w) - borunun başladığı quyunun nömrəsi və x və y (-10000 ≤ x, y ≤ 10000) - borunun bitdiyi yerin mövqeyi.
Hər bir boru dəqiq bir quyuya malikdir - başladığı quyu. İki və ya daha çox borunun qoşulduğu hər hansı bir nöqtə quyudur. İki boru ən çox bir ümumi nöqtəni paylaşır. İki borunun ümumi nöqtəsi birinin və ya hər ikisinin son nöqtəsi ola bilər. Bütün boruların uzunluğu müsbətdir.
Çıxış Məlumatları
Əgər bütün kəsişmələri təmizləmək mümkündürsə, "possible" çıxarın. Əks halda "impossible" çıxarın.