فهرست مندرجات
Tracking Robots
تعدادی روبات در حال حرکت در یک منطقه هستند و مدام مکانشان را به سرور می‌فرستند. با توجه به اطلاعات گرفته شده توسط روبات‌ها، سرور باید تعداد روبات‌ها را به‌دست بیاورد.
فرض کنید منطقه‌ای که روبات‌ها در آنجا هستند یک چندضلعی است. این چندضلعی به $N$ ناحیه مختلف با شماره‌های $1, ..., N$ افراز شده است. در ابتدا همه‌ی روبات‌ها در ناحیه $1$ قرار دارند. سپس شروع به حرکت در منطقه می‌کنند. وقتی که یک روبات به یک ناحیه‌ی جدید وارد می‌شود، شماره آن ناحیه را برای سرور می‌فرستد. توجه کنید که روبات‌ها می‌توانند بیش از یک بار به یک ناحیه داخل و یا از آن خارج شوند.
سرور یک دنباله طولانی از اطلاعات فرستاده شده توسط روبات‌ها به‌دست آورده، اما اینکه هر کدام از این اطلاعات توسط کدام روبات فرستاده شده معلوم نیست. با دانستن اطلاعات سرور و نقشه منطقه، شما باید به سرور کمک کنید تا تعداد روبات‌ها را به‌دست آورد.
شما باید حداقل و حداکثر تعداد روبات ممکن که می‌توانستند این دنباله‌ی اطلاعات را تولید کنند به‌دست آورید، با این فرض که هر روبات حداقل یک بار، شماره یک ناحیه را برای سرور فرستاده است.
ورودی
- ورودی از چند سناریو تشکیل شده است. در خط اول هر سناریو عدد‌های $N (1 \leq N \leq 100)$، تعداد ناحیه‌ها و $M (1 \leq M \leq 200)$، طول دنباله اطلاعات گرفته شده توسط سرور، آمده است.
- هر یک از $N$ خط بعدی مشخصات ناحیه‌ها را بیان می‌کند، خط $i$ ام بیانگر مشخصات ناحیه $i$ ام است. هر خط با یک عدد $c_{i}$ شروع شده که نشان‌‌دهنده تعداد همسایه‌های ناحیه $i$ ام است. سپس در همین خط $c_{i}$ عدد آمده که شماره همسایه‌های ناحیه $i$ را نشان می‌دهد.
- در خط آخر نیز $M$ عدد آمده که شماره ناحیه‌هایی که سرور از روبات‌ها گرفته را (به همان ترتیبی که سرور آن‌ها را دریافت کرده) نشان می‌دهد.
- ورودی با خطی شامل دو عدد $0$ تمام می‌شود.
خروجی
برای هر سناریو در یک خط به ترتیب حداقل و حداکثر تعداد روبات‌ها را چاپ کنید.
محدودیت‌ها
- محدودیت زمان: ۱۰ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت