Outpost Naviqasiya#6607
Şəhər zombilər tərəfindən ələ keçirilib və siz və komandanızın ehtiyatları tükənmək üzrədir. Dəqiq kəşfiyyat və planlaşdırma nəticəsində sizə təhlükəsiz məntəqələrin siyahısı və ərazidə müşahidə olunan zombilərin sayı ilə bağlı hesabat təqdim edilib. Hər bir məntəqə radio şəbəkəsinin bir hissəsidir və yerləşdiyi yerin adı olaraq radio çağırış işarəsindən istifadə edir.
Komandanızın məhdud miqdarda sursatı var və yalnız müəyyən ölçüdəki zombi qruplarını dəf edə bilər. Hər bir sursat vahidi bir səfərdə bir zombini dəf edə bilər. Yolu təhlükəsiz keçmək üçün yolda qarşılaşdığınız zombi sayına bərabər miqdarda sursat sərf etməlisiniz. Kəşfiyyat məlumatlarına əsasən, ehtiyac duyduğunuz ehtiyatların olduğu bir məntəqəyə ən az zombi qarşılaşması ilə təhlükəsiz bir yol tapın. Səyahətinizə ilk siyahıya alınmış məntəqədən başlayacaqsınız və həmin məntəqədəki sursatla başlayacaqsınız. Ehtiyac duyduğunuz ehtiyatların olmadığı, lakin sursat olan başqa bir məntəqə ola bilər. Əgər həmin məntəqəyə səyahət etsəniz, bütün sursatını toplaya bilərsiniz. Ehtiyac duyduğunuz ehtiyatların olduğu istənilən sayda məntəqə ola bilər, lakin yalnız birinə səyahət etməyiniz kifayətdir.
Hər hansı bir səbəbdən bir yolu bir neçə dəfə keçməli olsanız, hər sonrakı səfərdə ilk səfərdə qarşılaşdığınız qədər zombi ilə qarşılaşacaqsınız və zombilər əlavə zombi qarşılaşmaları kimi sayılır. Zombilər güllələrlə asanlıqla öldürülmür.
Girişin ilk sətri test hallarının sayını, C (1 ≤ C ≤ 50) verəcək.
Hər bir test halı üçün, məntəqələrin sayını, N (1 ≤ N ≤ 100) və yolların sayını, R (0 ≤ R ≤ 200) verən tək bir sətir olacaq.
1 1
Hər bir məntəqə üçün, çağırış işarəsini (A-Z və 0-9 aralığında 6 simvol), məntəqədəki sursat miqdarını A, (0 ≤ A ≤ 100), və məntəqənin ehtiyac duyduğunuz ehtiyatlara malik olub-olmadığını göstərən bir ifadəni ("yes" və ya "no") verən tək bir sətir olacaq.
CLLSGN 0 yes
Hər bir yol üçün, bağladığı 2 məntəqənin çağırış işarələrini və yolda qarşılaşacağınız zombi sayını, Z (0 ≤ Z ≤ 100) verən tək bir sətir olacaq.
OTPST1 OTPST2 5
Hər bir test halı üçün, ehtiyac duyduğunuz ehtiyatların olduğu bir məntəqəyə təhlükəsiz bir yol üçün minimum zombi qarşılaşmalarının sayını verən tək bir sətir çap edin. Əgər ehtiyatlara təhlükəsiz bir yol yoxdursa, "No safe path" ifadəsini verən tək bir sətir çap edin.
Nümunə 1