Hadisələrin izlənməsi

Fermer Con, COWVID-19 adlı çox yoluxucu bir mal-qara xəstəliyinin yayılmasından sonra inəklərinin sağlamlığı üçün narahatdır (ardıcıl olaraq 1 .. n nömrələnmişdir).

Son zamanlar Fermer Con bütün inəklərini yoxladı və bəzilərinin xəstəliyə yoluxduğunu aşkar etdi. Mal-qara tövləsindən video yazıları istifadə edərək, inəklər arasında son qarşılıqlı əlaqələri izləyə bilir - məlum olur ki, inəklər bir-birini salamlayanda, təəssüf ki, infeksiyanı bir inəkdən digərinə ötürə bilən bir jest olan dırnaqlarını silkələyirlər. Fermer Con, vaxt nişanları ilə inəklərin təmasda olduğu cütlərin siyahısını tərtib edir, (t, x, y) şəklində qeydlərdən istifadə edir, bu da t vaxtında x inəyinin y inəyi ilə dırnaqlarını silkələdiyini göstərir. Fermer Con həmçinin aşağıdakıları bilir:

(i) Fermada yalnız bir inək xəstəliyi daşımağa başlaya bilər (bu inəyi "sıfır xəstə" adlandıraq).

(ii) İnək yoluxduqdan sonra, növbəti k dırnaq silkələmələri ilə infeksiyanı ötürür (eyni inək tərəfdaşı ilə bir neçə dəfə ola bilər). k dırnaq silkələməsindən sonra infeksiyanı daha ötürmür (bu anda infeksiyanı yaydığını başa düşür və gələcəkdə salamlaşarkən dırnaqlarını diqqətlə yuyur).

(iii) Yoluxduqdan sonra inək yoluxmuş vəziyyətdə qalır.

Təəssüf ki, Fermer Con hansı n inəyinin sıfır xəstə olduğunu və k dəyərini bilmir! Ona bu naməlumları məlumatlarına əsasən daraltmağa kömək edin. Zəmanət verilir ki, ən azı bir ehtimal doğrudur.

Giriş Məlumatları

Birinci sətir n (2 ≤ n ≤ 100) və T (1 ≤ T ≤ 250) ədədlərini ehtiva edir. Növbəti sətir uzunluğu n olan və Fermer Conun n inəyinin cari vəziyyətini təsvir edən 0 və 1 ədədlərini ehtiva edir - 0 sağlam inəyi, 1 isə xəstə inəyi göstərir. Növbəti T sətirin hər biri inəklər arasında təması təsvir edir və t, x və y üç tam ədəddən ibarətdir, burada t (t ≤ 250) təmasın baş verdiyi müsbət tam vaxtdır, x və y isə 1 .. n aralığında olan fərqli tam ədədlərdir, t vaxtında bir-birinə dırnaqlarını silkələyən inəklərin nömrələridir. Hər bir anda yalnız bir təmas baş verir.

Çıxış Məlumatları

Bir sətirdə üç tam ədəd x, y və z çıxarın, burada x sıfır xəstə ola biləcək inəklərin mümkün sayıdır, y məlumatlara uyğun ən kiçik mümkün k dəyəridir və z məlumatlarla uyğun olan ən böyük mümkün k dəyəridir (əgər k üçün yuxarı sərhəd mövcud deyilsə, z üçün "Infinity" çıxarın). Qeyd edin ki, k = 0 ola bilər.

Nümunə

Sıfır xəstə üçün yeganə namizəd 1 nömrəli inəkdir. Bütün k > 0 üçün 1 nömrəli inək 7 vaxtında 2 nömrəli inəyi yoluxdurur, lakin 3 və 4 nömrəli inəklər yoluxmamış qalır.