Gəlin Yaşıl Olaq
Khairy gənc, ağıllı və çox istedadlı bir siyasətçidir. Lakin o, hələ də inanır ki, uğur qazanmaq, xüsusilə də bir şey əldə etmək üçün şəxsi əlaqələr şəbəkəsi vacibdir. Gələn ay onun siyasi partiyasının Ali Şurasına seçkilər keçiriləcək. O, seçkilərdə iştirak edib qalib gəlmək istəyir. Buna görə də, nüfuzlu siyasətçilərin dəstəyinə ehtiyacı var.
Vaxt azalır, buna görə də o, bir strategiya planlaşdırır. Əgər o, birbaşa ən nüfuzlu şəxslə görüşə bilmirsə, digər siyasətçilərdən istifadə edərək onu bu liderə təqdim etmələrini istəyəcək. Bunu etmək üçün o, siyasətçilər arasındakı əlaqələrin gücünü modelləşdirir.
İki nəfər arasındakı əlaqənin gücü belə təmsil olunur: Sadiq (1), Yaxın (2), Dostlar (3) və Tanış (4). İki siyasətçi arasında, adətən, onlardan biri ünsiyyəti təşviq edəcək. Düşmən üçün heç bir təmsil yoxdur. Sadiq bir dostun Khairy-ni kiməsə təqdim etməsi tanışdan daha yaxşıdır. Beləliklə, Khairy ən nüfuzlu siyasətçi ilə görüşmək üçün istifadə etdiyi əlaqələrin gücünün cəmini minimuma endirmək istəyir.
N siyasətçinin siyahısından, onların əlaqə gücləri verilmişdir, Khairy-nin ən nüfuzlu siyasətçi ilə görüşməsi üçün istifadə edəcəyi siyasətçilərin siyahısını tapın, belə ki, istifadə etdiyi bütün əlaqələrin gücünün cəmi minimum olsun.
Giriş verilənləri
Girişin ilk sətri T sayını göstərir, bu isə işlərin sayıdır, 1 < T < 1000. Bu, test işləri ilə davam edir. Hər bir iş bir neçə sətrdən ibarətdir. İlk sətir 2 ədəd ehtiva edir, birincisi əlaqələrin sayını göstərən N, N ≤ 200, ikincisi isə siyasətçilərin sayını göstərən M, 5 ≤ M ≤ 20. Növbəti N sətirin hər biri üç tam ədəd ehtiva edir ki, bu da siyasətçi x, onun dostu y (0 ≤ x, y < M) və əlaqənin gücü z (1 ≤ z ≤ 4) ilə təmsil olunur. Siyasətçi x=0 Khairy-ni, siyasətçi x=M-1 isə ən nüfuzlu siyasətçini təmsil edir.
Çıxış verilənləri
Hər bir test işi üçün çıxış Case #x: formatında bir sətir ehtiva edir, burada x işin nömrəsidir (başlayaraq 1-dən), ardınca iki nöqtə və görüşüləcək siyasətçilərin ardıcıllığı gəlir. Əgər bir neçə uyğun siyasətçi ardıcıllığı varsa, onlardan hər hansı birini çap edin. Siyahı 0 (Khairy-nin id-si) ilə başlamalı və M-1, ən nüfuzlu siyasətçi ilə bitməlidir. Əgər Khairy-nin ən nüfuzlu siyasətçi ilə görüşməsi mümkün deyilsə, -1 çap edin.
Birinci iş üçün izah: Khairy siyasətçi 1-dən (güc 2, yaxın) siyasətçi 3-ə (güc 4, tanış) onu təqdim etməsini xahiş edə bilər, o da nəhayət Khairy-ni siyasətçi 4-ə (güc 4, tanış) təqdim edə bilər. Bu vəziyyətdə istifadə olunan ümumi güc 2+4+4 = 10 olur.
Khairy birbaşa siyasətçi 4 ilə danışa bilər (güc 3, dost). Amma əgər Khairy siyasətçi 2-dən (güc 1, sadiq) onu siyasətçi 4-ə (güc 1, yenə sadiq) təqdim etməsini xahiş etsə – bu vəziyyətdə istifadə olunan ümumi güc 2 olur ki, bu da digər iki vəziyyətdən daha yaxşıdır və Khairy daha yaxşı təəssürat yarada bilər.