Şəbəkə Şirkəti#3423
"' Tutaq ki, siz CluNet adlı şəbəkə şirkəti üçün məsləhətçisiniz və onların belə bir problemi var. Hazırda işlədikləri şəbəkə, N düyün və M kənardan ibarət olan əlaqəli qraf G = (V, E) ilə modelləşdirilib. Hər bir kənar e, iki şirkətdən biri tərəfindən - yaradıcı adlarla X və Y adlandırılan - CluNet-ə icarəyə verilən fiber-optik kabellərdir. Onların planı, G qrafının bir örtən ağacını T seçmək və T kənarlarına uyğun olan bağlantıları təkmilləşdirməkdir. Onlar artıq X və Y şirkətləri ilə bir razılaşma əldə ediblər ki, seçilən T ağacında K kənar X şirkətinə məxsus olacaq və N−K−1 kənar Y şirkətinə məxsus olacaq.
CluNet rəhbərliyi indi belə bir problemlə üzləşir. Onlara heç də aydın deyil ki, bu şərtlərə cavab verən bir örtən ağac mövcuddurmu, yoxsa mövcuddursa, onu necə tapmaq olar. Beləliklə, bu problemi sizə təqdim edirlər.
Giriş bir sıra test hallarını ehtiva edir.
Hər bir test halı üç tam ədəd N (1 ≤ N ≤ 1000), M (1 ≤ M ≤ 3000) və K (0 ≤ K ≤ N−1) olan bir sətirlə başlayır.
Sonrakı M sətir kənarları təsvir edir. i-ci sətir üç tam ədəd x_i, y_i və c_i ehtiva edir. i-ci kənar x_i-ci və y_i-ci zirvələri birləşdirir. c_i i-ci kənarın hansı şirkətə məxsus olduğunu göstərir. c_i ya 0, ya da 1 ola bilər; 0 X deməkdir və 1 Y deməkdir.
Giriş üç sıfır ehtiva edən bir sətirlə bitir. Bu sətir işlənməməlidir.
Hər bir test halı üçün, nümunə çıxışda göstərildiyi kimi cavabı çıxarın. Hər bir çıxışın ilk sətiri 1-dən başlayaraq test halı nömrəsini göstərməlidir.
Növbəti sətirdə "mümkün" və ya "mümkünsüz" yazın. Əgər şərti təmin edən örtən ağacı qura bilirsinizsə, "mümkün" yazın. Əks halda, "mümkünsüz" yazın.
Əgər örtən ağacı qura bilirsinizsə, növbəti sətirdə istifadə etdiyiniz kənarların nömrələrini (1-dən başlayaraq) yazın. Hər bir nömrə bir boşluqla ayrılmalıdır.
Hər bir test halından sonra bir boş sətir yazmalısınız. "'
Nümunə 1