Qatlanan Armaturlar
Siz, bəlkə də, bu həftə ad günü üçün Frensisin aldığı məşhur və çox arzulanan konstruktor oyuncağını tanıyırsınız. Bu oyuncaq, hər iki ucunda maqnit olan sərt çubuqlar (hamısı eyni uzunluqda) vasitəsilə bir-birinə bağlana bilən bir sıra metal kürələrdən ibarətdir. Çubuqların ucları metal kürələrə yapışır və sərbəst şəkildə dönə bilər, kürədən hər hansı bir istiqamətdə uzana bilər (əsasən sferik bir birləşmə əmələ gətirərək), sizə müxtəlif maraqlı strukturlar yaratmağa imkan verir. Frensis bir neçə belə strukturlar yığmışdır və indi öz yaradıcılıqlarını otağının bir küncündə asaraq saxlamaq istəyir. O, bəzi strukturlarında, bir kürəni götürüb tutduqda, bütün çubuqların cazibə qüvvəsi və sferik birləşmələr səbəbindən tək, nazik bir şaquli xəttə çökdüyünü (şəkilə baxın) müşahidə edir. Frensis, hər birini ən qısa çökən xəttə səbəb olan kürə ilə tavana bərkidərək yaradıcılıqlarını asmaq istəyir. O, tək nazik xətt kimi asılmayan qurğuları çox yer tutduğunu hesab edir və onları atır. Şəkil: Frensisin quruluşlarından biri (yuxarıda), eyni şəkildə uzunluğu 2 olan düz xətt qurğusuna çökən (sol aşağıda) və heç bir kürə ilə asıldıqda tək xəttə çökə bilməyən bir struktur (sağ aşağıda). Orta diaqramda göstərilən kürələr arasındakı üfüqi boşluqlar yalnız təsviri məqsədlər üçündür! Riyazi olaraq, qurğu tək, sonsuz nazik bir şaquli xətt olardı. Sadəlik üçün metal kürələri sonsuz kiçik nöqtələr və çubuqları vahid uzunluqlu xətt seqmentləri kimi qəbul edə bilərik. Frensisin qurğularının nə qədər yer tutacağını və hansını atacağını müəyyən etmək üçün bir proqram yaza bilərsinizmi? Sizin vəzifəniz, tək kürə ilə asıldıqda çökən qurğunun mümkün olan ən qısa uzunluğunu tapmaq və ya qurğunu tək xəttə çökəcək şəkildə asmağın mümkün olmadığını bildirməkdir.
Giriş verilənləri
Girişdə analiz etməyiniz üçün bir neçə test halı olacaq. Hər bir test halı tam bağlı bir qurğunu təsvir edir (yəni boş, qoşulmamış komponentlər yoxdur). Test halının ilk sətri, quruluşda istifadə olunan kürələrin (1 ≤ n ≤ 100) və çubuqların (0 ≤ m ≤ 1000) sayını göstərən iki tam ədəd, n və m, ilə ayrılmış bir boşluqdan ibarətdir. Kürələr 1-dən n-ə qədər unikal olaraq nömrələnmişdir. Növbəti m giriş sətri hər biri iki tam ədəd, a_i və b_i (1 ≤ a_i, b_i ≤ n), ehtiva edir ki, bu da Frensisin qurğusunda kürə a-nı kürə b-yə bağladığını göstərir. Qeyd edək ki, bir çubuğun hər iki ucu bir kürəyə bağlana bilməz və heç bir iki çubuq eyni iki kürəni bağlamayacaq. Giriş test halları arasında boş bir sətir var, aşağıdakı nümunə girişdə göstərildiyi kimi. "0 0" ehtiva edən tək bir sətir girişin sonunu göstərir; bu halı emal etməyin.
Çıxış verilənləri
Hər bir giriş test halı üçün, çökən qurğunun mümkün olan ən qısa uzunluğunu ehtiva edən tək bir sətir çap edin. Əgər təsvir edilən qurğunu tək kürə ilə asmaq və beləliklə xəttə çökdürmək mümkün deyilsə, "impossible" çap edin.