कॉन्टैक्ट ट्रेसिंग
Problem
किसान जॉन अपनी गायों के स्वास्थ्य की देखभाल करना जारी रखता है, जिसकी संख्या लगातार 1…N है।
हाल ही में एफडी ने उन सभी की जांच की तो पता चला कि उनमें से कुछ बीमार हैं। खलिहान से वीडियो का उपयोग करके, एफडी यह पता लगा सकता है कि किन गायों के जोड़े ने बीमारी फैलाने के लिए परस्पर क्रिया की। FD ने उस समय को इंगित करने वाली एक सूची एकत्र की है, जिस समय वीडियो (t,x,y) में गायों के जोड़े की बातचीत हुई, जिसका अर्थ है कि उस समय t गाय x ने गाय y के साथ बातचीत की। एफडी निम्नलिखित भी जानता है:
<ओल>
शुरू में ठीक एक गाय संक्रमित हुई थी (रोगी शून्य)।
गाय के संक्रमित होने के बाद, वह संक्रमण को अपने अगले K अंतःक्रियाओं में स्थानांतरित कर देती है (संभवतः एक ही साथी को कई बार शामिल करना)। संचरण के K समय के बाद, वह संक्रमण को प्रसारित करना बंद कर देती है (यह महसूस करने पर कि वह संक्रमित हो रही है, वह अपने खुरों को अच्छी तरह से धोना शुरू कर देती है)।
एक बार बीमार होने के बाद, वह बीमार रहती है।
दुर्भाग्य से, पीडी नहीं जानता कि उसकी कौन सी एन गाय "रोगी शून्य" है, और वह के के मूल्य को नहीं जानता है। उसके डेटा के आधार पर इन अज्ञात की सीमाओं को कम करने में उसकी मदद करें। उत्तर मौजूद होने की गारंटी है।
इनपुट
पहली इनपुट पंक्ति में N (2≤N≤100) और T (1≤T≤250) शामिल हैं। अगली पंक्ति में लंबाई एन की एक स्ट्रिंग है, जिसमें 0 और 1 शामिल हैं, एन एफडी गायों की वर्तमान स्थिति का वर्णन करते हुए, 0 - स्वस्थ, 1 - बीमार। निम्नलिखित टी लाइनों में से प्रत्येक एफडी इंटरैक्शन की सूची से एक प्रविष्टि का वर्णन करती है, और इसमें तीन नंबर होते हैं, टी, एक्स, वाई, जहां टी एक सकारात्मक पूर्णांक इंटरैक्शन समय (t≤250) है, x और y अलग-अलग पूर्णांक हैं अंतराल 1…N,, यह दर्शाता है कि T के समय किन गायों ने परस्पर क्रिया की। एक समय में एक से अधिक अंतःक्रिया नहीं होती है।
छाप
तीन पूर्णांक x, y, z वाली एक पंक्ति प्रिंट करें, जहाँ x विभिन्न गायों की संख्या है जो "रोगी शून्य" हो सकती है y - K का सबसे छोटा संभव मान जो इनपुट डेटा z को फिट करता है - K का सबसे बड़ा संभव मान जो इनपुट डेटा को फिट करता है यदि K के लिए कोई ऊपरी सीमा नहीं है, तो "इन्फिनिटी" प्रिंट करें; जेड के लिए। ध्यान दें कि K=0 संभव है।
उदाहरण
<टेबल क्लास = "टेबल-एसएम टेबल-बॉर्डर टेबल-स्ट्राइप्ड टेबल-लिस्ट-टेस्ट">
<सिर>
<थ वर्ग = "अंक"> #
<वें>इनपुट
<वें>आउटपुट
<शरीर>
| 1 |
4 3
1100
7 1 2
5 2 3
6 2 4
| 1 1 इन्फिनिटी |