Problem
Çiftçi John, art arda 1&N numaralı ineklerinin sağlığıyla ilgilenmeye devam ediyor.
Geçenlerde FD hepsini kontrol etti ve bazılarının hasta olduğunu öğrendi. FD, ahırdaki videoyu kullanarak, hangi inek çiftlerinin hastalığı yaymak için etkileşime girdiğini öğrenebilir. FD, videodaki inek çiftlerinin etkileşiminin (t,x,y) gerçekleştiği zamanı gösteren bir liste topladı, yani t zamanında inek x inek y ile etkileşime girdi. FD ayrıca aşağıdakileri de bilir:
- Başlangıçta tam olarak bir inek enfekte oldu (sıfır hasta).
- Bir inek enfekte olduğunda, enfeksiyonu bir sonraki K etkileşimine geçirir (muhtemelen aynı partneri birçok kez kapsamıştır). K kez bulaştıktan sonra, enfeksiyonu bulaştırmayı bırakır (enfekte olduğunu anlayınca toynaklarını iyice yıkamaya başlar).
- Bir kez hastalandığında hasta kalmaya devam eder.
Ne yazık ki PD, N ineğinden hangisinin "Sıfır Hasta" olduğunu bilmiyor ve K!'nin değerini bilmiyor. Verilerine dayanarak bu bilinmeyenlerin aralığını daraltmasına yardım edin. Cevabın var olduğu garanti edilir.
Girdi
İlk giriş satırı N (2≤N≤100) ve T'yi (1≤T≤250) içerir. Bir sonraki satır, N FD ineklerin mevcut durumunu açıklayan, 0 - sağlıklı, 1 - hasta olan, 0 ve 1'den oluşan bir uzunluk N dizisi içerir. Aşağıdaki T satırlarının her biri, FD etkileşimleri listesinden bir girişi açıklar ve üç sayıdan oluşur; t, x, y; burada t, pozitif bir tam sayı etkileşim süresidir (t≤250), x ve y, 1&N aralığı, hangi ineklerin T zamanında etkileşime girdiğini gösterir. Bir T zamanında birden fazla etkileşim olmaz.
Künye
Üç tamsayı x, y, z içeren bir satır yazdırın; burada x, "hasta sıfır" olabilecek farklı ineklerin sayısıdır y - giriş verilerine uyan K'nin mümkün olan en küçük değeri z - giriş verilerine uyan K'nin mümkün olan en büyük değeri K için üst sınır yoksa, "Sonsuz" yazdırın; z için K=0'ın mümkün olduğuna dikkat edin.
Örnekler
| # |
Girdi |
Çıktı |
| 1 |
4 3
1100
7 1 2
5 2 3
6 2 4
| 1 1 Sonsuz |