GPS Mən Səni Sevirəm#2680
Thomas T. Garmin keçən il ad günündə GPS hədiyyə aldı və o, bu hədiyyəni çox bəyəndi! Təəssüf ki, bəzən Tom GPS-in təklif etdiyi ən qısa marşrut əvəzinə, daha mənzərəli marşrutu seçmək istəyirdi. O, istifadəçi kitabçasını bir az oxudu və öyrəndi ki, GPS-in alqoritmini elə dəyişmək mümkündür ki, istədiyin yolları məcburi olaraq istifadə etməyə məcbur edəsən. Bir qədər sınaqdan sonra Tom başa düşdü ki, çox vaxt yalnız bir yolu məcburi seçmək istədiyi marşruta çatmaq üçün kifayət edir. Lakin daha mürəkkəb marşrutlar üçün bir neçə yolu məcburi seçməli olurdu. Sonda Tom özü-özünə sual verməyə başladı: bəlkə də, hər səfərdən əvvəl seçiləcək yolları təyin etməyə çox vaxt sərf edir? İndi GPS-dən zövq almaq əvəzinə, səfərlərində bu sual üzərində düşünür: görəsən, seçilmiş mənzərəli marşrutu GPS-in vasitəsilə daha az sayda məcburi yol seçməklə qət etmək olardımı?
Bu məhəbbəti xilas edə biləcəksinizmi, yoxsa Tom və onun GPS-i yollarını ayırmağa məhkumdurlar?
Hər test üçün daxil olan məlumat bir neçə sətrdən ibarətdir. Birinci sətirdə n < 100 ədədi verilir, bu -dan n-1-ə kimi nömrələnmiş yol sonluqlarının sayını göstərir. Sonra sətir verilir, onların hər birində qeyri-mənfi tam ədəd yerləşir. Əgər -ci sətirin -ci ədədi müsbətdirsə, bu nöqtəsindən nöqtəsinə yolun uzunluğunu bildirir; əgər -dırsa, bu iki nöqtə arasında yol yoxdur deməkdir. Bu sətrlərdən sonra aşağıdakı formda bir sətir verilir: m\ p_1\ p_2\ p_{3}\ ...\ p_m — burada Tomun istədiyi mənzərəli marşrut göstərilir: marşrutda m-1 yol var və p_1-dən p_m-ə gedir, ardıcıllıqla p_2, p_3 və s. nöqtələrdən keçir. Sonuncu testdən sonra bir sətirdə yazılır.
Nəzərə alın ki, Tom məcburi yolları GPS-ə bildirərkən həm istiqaməti, həm də ardıcıllığı müəyyən edir. Bütün marşrutlar sadə polad yollardır və bütün yol uzunluqları -dür.
Hər test üçün çıxışda aşağıdakı formatda bir sətir yazın:
Case n: k
burada elə ən kiçik sayda yoldur ki, Tom onların GPS tərəfindən seçilməsinə zəmanət verməlidir ki, GPS göstərilən marşrutu seçsin. Qəbul edin ki, əgər bir neçə ən qısa yol varsa, GPS bu yollar arasında ən mənzərəli olanını seçir. Yəni əgər Tomun marşrutu məcburi yollar dəstindəki ən qısa yollardan biridirsə, GPS məhz onu seçəcək.
Nümunə 1