تتبع جهات الاتصال
Problem
يواصل المزارع جون العناية بصحة أبقاره ، المرقمة على التوالي 1 & hellip؛ N.
في الآونة الأخيرة ، فحصت إدارة الدفاع عنهم جميعًا ووجدت أن بعضهم مريض. باستخدام فيديو من الحظيرة ، يمكن لـ FD اكتشاف أزواج الأبقار التي تفاعلت لنشر المرض. جمعت FD قائمة تشير إلى الوقت الذي حدث فيه تفاعل أزواج الأبقار في الفيديو (t ، x ، y) ، مما يعني أنه في الوقت المناسب تفاعلت t بقرة x مع بقرة y. تعرف FD أيضًا ما يلي:
- على & nbsp ؛ أصيب بقرة واحدة في البداية (المريض صفر).
- على & nbsp؛ بمجرد إصابة بقرة بالعدوى ، تنقل العدوى إلى تفاعلاتها التالية من النوع K (ربما تشمل نفس الشريك عدة مرات). بعد K مرات من انتقال العدوى ، توقفت عن نقل العدوى (بعد أن أدركت أنها مصابة بالعدوى ، بدأت في غسل حوافرها جيدًا).
- على & nbsp؛ عندما تمرض ، تظل مريضة.
لسوء الحظ ، لا يعرف PD أي من أبقاره N هي "Patient Zero" ، ولا يعرف قيمة K !. ساعده في تضييق نطاقات هذه الأشياء المجهولة بناءً على بياناته. الجواب مضمون.
إدخال
يحتوي سطر الإدخال الأول على N (2 & le؛ N & le؛ 100) و T (1 & le؛ T & le؛ 250). يحتوي السطر التالي على سلسلة طولها N ، تتكون من 0 و 1 ، تصف الحالة الحالية للأبقار N FD ، 0 - صحية ، 1 - مريضة. يصف كل سطر من سطور T التالية إدخالاً من قائمة تفاعلات FD ، ويتكون من ثلاثة أرقام ، t ، x ، y ، حيث t هو وقت تفاعل عدد صحيح موجب (t & le ؛ 250) ، x و y هي أعداد صحيحة مختلفة في الفاصل الزمني 1 & hellip؛ N ، يشير إلى الأبقار التي تفاعلت في الوقت T. لا يحدث أكثر من تفاعل واحد في وقت واحد T.
بصمة
اطبع سطرًا واحدًا يحتوي على ثلاثة أعداد صحيحة x ، y ، z ، حيث x هو عدد الأبقار المختلفة التي يمكن أن تكون "المريض صفر" y - أصغر قيمة ممكنة لـ K تلائم بيانات الإدخال z - أكبر قيمة ممكنة لـ K تلائم بيانات الإدخال إذا لم يكن هناك حد أعلى لـ K ، اطبع "Infinity" ؛ لـ z. لاحظ أن K = 0 ممكن.
أمثلة
| # |
إدخال |
الإخراج |
<الجسم>
| 1 |
4 3
1100
7 1 2
5 2 3
6 2 4
| 1 1 إنفينيتي
|