Qırmızı-mavi skelet ağacı
Verilmiş qraf istiqamətsiz, çəkisiz və əlaqəlidir, hər bir kənar mavi və ya qırmızı rəngə boyanmışdır. Verilmiş qraf üçün dəqiq k mavi kənarlı bir skelet ağacı olub-olmadığını müəyyən edin.
Giriş verilənləri
Giriş məlumatları bir neçə test dəsti ehtiva edə bilər. Hər bir test üç tam ədəddən ibarət bir sətirlə başlayacaq:
n m k
burada n (2 ≤ n ≤ 1000) - qrafdakı zirvələrin sayı, m (qrafın strukturu ilə məhdudlaşdırılmışdır) - qrafdakı kənarların sayı və k (0 ≤ k < n) - istənilən ağacda mavi kənarların sayı.
Növbəti m sətirdən hər biri kənarları təsvir edən üç elementdən ibarət olacaq:
c f t
burada c - kənarın rəngini göstərən böyük latın hərfi 'R' və ya 'B', və tam ədədlər f və t (1 ≤ f, t ≤ n, t ≠ f) - müvafiq kənarın birləşdirdiyi zirvələri göstərir. Qrafın əlaqəli olduğu və istənilən iki zirvə arasında ən çox bir kənarın olduğu zəmanət verilir. Giriş məlumatları üç 0 ehtiva edən bir sətirlə bitir.
Çıxış verilənləri
Hər bir test üçün dəqiq k mavi kənarlı bir skelet ağacı qurmaq mümkün olarsa, 1, əks halda 0 ehtiva edən bir sətir çıxarın. Cavabları artıq boşluqlar olmadan və boş sətirlərlə ayırmadan çıxarın.