کنار هم چیدن قطعه‌ها - نسخه‌ی بزرگ

Time Limit: 40 Seconds    Memory Limit: 65536 KB

توجه: از ۳۰ نمره‌ی اختیاری، ۵ نمره مربوط به قسمت «ب» (تئوری) و ۲۵ نمره مربوط به قسمت «ت» است که یک مسئله‌ی پیاده‌سازی است.

فرض کنید تعدادی قطعه‌ی چوبی با شکل‌های مختلف داده شده. هر قطعه از کنارهم قرار گرفتن تعدادی مربع 1x1 تشکیل شده، به‌طوری‌که هر مربع لااقل با یک مربع دیگر یک ضلع مشترک دارد. مثلا در شکل زیر چند قطعه‌ی نمونه نشان داده شده:

مسئله این است که برای یک m و n داده شده، آیا می‌توان با کنار هم قرار دادن این قطعه‌ها، یک مستطیلی m x n را به‌طور کامل پوشاند به‌طوری‌که که قطعه‌ها روی هم قرار نگیرند یا نه؟ برای سادگی فرض کنید که قطعه‌ها را نمی‌توان چرخاند یا پشت‌ورو کرد (به‌جز قسمت «ب»).

بدیهی است که اگر تعداد خانه‌های همه‌ی قطعه‌ها برابر m x n نباشد، پاسخ مسئله منفی خواهد بود ولی به‌وضوح این یک شرط لازم (و نه کافی) است. به‌عنوان نمونه اگر m=3 و n=5 باشد، با قطعه‌های بالا می‌توان یک مستطیل m x n را پوشاند:

برنامه‌ای بنویسید که با دریافت مشخصات بلوک‌ها و اعداد m و n، مشخص کند که آیا پاسخ مسئله‌ی فوق مثبت است یا نه (فرض کنید چرخش و پشت‌ورو کردن قطعه‌ها مجاز نیست). تعداد قطعه‌ها حداکثر ۲۰ و مقدار m x n حداکثر ۸۰ است. برنامه‌ی شما برای هر ورودی باید در حداکثر ۳ ثانیه پاسخ را بیابد.

ورودی: در خط اول ورودی، یک عدد k <= 20 نوشته شده که تعداد مجموعه‌های ورودی است. بعد از آن برای هر مجموعه‌ی ورودی، در خط اول سه عدد p, m, n نوشته شده که p تعداد قطعه‌ها، m تعداد سطرها و n تعداد ستون‌های مستطیل است. سپس در p خط بعدی، هر خط مشخصات یک بلوک را دارد که با عدد c، برابر با تعداد خانه‌های آن قطعه، شروع می‌شود و بعد از آن 2c عدد صحیح نوشته شده که هر زوج مختصات یک قطعه را نشان می‌دهد (ابتدا شماره‌ی سطر بعد ستون). فرض کنید که مختصات اولین خانه همیشه (0, 0) است و مختصات بقیه‌ی خانه‌ها به نسبت خانه‌ی اول داده شده.

خروجی: به ازاء هر مجموعه‌ی ورودی، یک خط خروجی وجود دارد که شامل 0 یا 1 است. پاسخ 1 را به‌عنوان «آری» و 0 را به‌عنوان «خیر» بنویسید.

Input

Output

 

Sample Input

2
3 2 4
2 0 0 1 0
2 0 0 1 0
4 0 0 1 0 1 -1 1 -2
4 3 5
5 0 0 0 1 1 1 2 0 2 1
5 0 0 1 -1 1 0 1 1 2 0
3 0 0 0 1 1 0
2 0 0 0 1

Sample Output

0
1

Submit