GPS Mən Səni Sevirəm
Thomas T. Garmin keçən il ad günündə GPS cihazı aldı və ona heyran qaldı! Lakin bəzən Tom GPS-in təklif etdiyi ən qısa marşrut əvəzinə mənzərəli bir yol seçmək istəyirdi. Təlimatı bir az araşdırdıqdan sonra, GPS sisteminin marşrutu müəyyən edərkən istifadə etməyə məcbur ediləcək yolları göstərməklə standart yol tapma alqoritmini dəyişdirə biləcəyini öyrəndi. Bir az təcrübə etdikdən sonra Tom, istədiyi marşrutu əldə etmək üçün tez-tez tək bir yolu məcbur etməyin kifayət olduğunu kəşf etdi. Lakin, bəzi daha mürəkkəb yollar üçün Tom daha çox yolu məcbur etməli idi. Nəhayət, Tom hər səfərdən əvvəl məcbur edəcəyi yolları seçməyə çox vaxt sərf etdiyindən narahat olmağa başladı. İndi, GPS-in möcüzələrindən zövq almaq əvəzinə, o, sürərkən aşağıdakı sual üzərində düşünür: GPS-in mənzərəli marşrutu daha az məcburi yollarla seçməsini təmin edə bilərdimi?
Bu sevgini xilas edə bilərsinizmi, yoxsa Tom və onun GPS-i ayrı yollarla getməyə məhkumdur?
Giriş verilənləri
Hər test halı üçün giriş bir neçə sətirdən ibarət olacaq. İlk sətir n < 100 olan tək bir tam ədədi ehtiva edəcək və bu, yolların son nöqtələrinin sayını göstərir, nömrələnmiş 0 -dan n-1-ə qədər. Sonra n sətir gələcək, hər biri n qeyri-mənfi tam ədədi ehtiva edəcək. Əgər i sətirindəki j-ci dəyər müsbətdirsə, bu, son nöqtə i-dən son nöqtə j-ə qədər olan yolun uzunluğunu göstərir; əgər dəyər 0-dırsa, bu, həmin iki son nöqtə arasında yol olmadığını göstərir. Bu sətirlərdən sonra m p_1 p_2 p_{3 }... p_m formasında bir sətir gələcək, bu, Tomun istədiyi mənzərəli marşrutu göstərir - marşrut m-1 yoldan ibarətdir və son nöqtələr p_1 və p_m arasında gedir, son nöqtələr p_2, p_3 və s. bu sırayla ziyarət edilir. Son test halı '0' ehtiva edən bir sətirlə bitəcək.
Qeyd edək ki, Tom məcburi yollarını GPS-ə göstərərkən həm istiqamətini, həm də sırasını göstərir. Bütün marşrutlar sadə yollardır və bütün yolların uzunluqları ≤ 100-dür.
Çıxış verilənləri
Hər test halı üçün aşağıdakı kimi bir sətir çıxış verin:
Case n: k
burada k GPS-in göstərilən marşrutu seçməsi üçün Tomun məcbur etməli olduğu ən az yol sayıdır. Əgər bir neçə ən qısa yol varsa, GPS-in həmişə bunların ən mənzərəli olanını seçdiyini fərz etməlisiniz. Buna görə, əgər Tomun marşrutu məcburi yolların müəyyən bir dəstini istifadə edən ən qısa yollardan biridirsə, GPS onu seçəcək.