ردیابی تماس
Problem
کشاورز جان همچنان مراقب سلامت گاوهایش است که به شماره 1…N متوالی هستند
اخیرا FD همه آنها را بررسی کرد و متوجه شد که برخی از آنها بیمار هستند. با استفاده از ویدئویی از انبار، FD می‌تواند دریابد که کدام جفت گاو برای گسترش بیماری با هم تعامل داشته‌اند. FD لیستی را جمع آوری کرده است که نشان می دهد در آن زمان تعامل جفت گاوها در ویدیو (t,x,y) رخ داده است، به این معنی که در زمان t cow x با گاو y تعامل داشته است. FD همچنین موارد زیر را می داند:
- در ابتدا دقیقاً یک گاو آلوده شد (بیمار صفر).
- هنگامی که گاو آلوده می‌شود، عفونت را به تعاملات K بعدی خود منتقل می‌کند (احتمالاً چندین بار شامل یک شریک زندگی می‌شود). پس از K بار انتقال، انتقال عفونت را متوقف می کند (با فهمیدن اینکه در حال عفونت است، شروع به شستشوی کامل سم های خود می کند).
- هنگامی که بیمار می‌شود، بیمار می‌ماند.
متأسفانه، PD نمی داند کدام یک از گاوهای N او "بیمار صفر" است و او ارزش K را نمی داند. به او کمک کنید تا محدوده این مجهولات را بر اساس داده هایش محدود کند. وجود پاسخ تضمین شده است.
ورودی
اولین خط ورودی شامل N (2≤N≤100) و T (1≤T≤250) است. خط بعدی شامل یک رشته به طول N، متشکل از 0 و 1 است که وضعیت فعلی N گاو FD، 0 - سالم، 1 - بیمار را توصیف می کند. هر یک از خطوط T زیر یک ورودی از لیست برهمکنش های FD را توصیف می کند و از سه عدد t، x، y تشکیل شده است که t یک زمان برهمکنش عدد صحیح مثبت است (t≤250)، x و y اعداد صحیح مختلف در بازه 1…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 بی نهایت |