Guess

بازی «واژه‌ی من را حدس بزن» یک بازی معروف ایرانی است که بین دو نفر انجام می‌شود. این بازی به این صورت انجام می شود که ابتدا نفر اول یک کلمه از یک واژه‌نامه (که نفر دوم نیز به آن دسترسی دارد)، انتخاب می‌کند و به خاطر می‌سپارد. سپس روی یک کاغد که جلوی چشمان نفر دوم هم هست به تعداد حروف آن کلمه (مثلاً n حرف)، پاره‌خط‌های افقی مجاور هم می‌چیند. نفر دوم تلاش می‌کند با انتخاب حرف به حرف، کلمه مورد نظر نفر اول را حدس بزند. در هر گام، نفر دوم یک حرف انتخاب می‌کند و به نفر اول می‌گوید و نفر اول در پاسخ:

• اگر آن حرف در کلمه مورد نظر موجود باشد آن را در مکان اصلیش، بالای پاره‌خط می‌نویسد. در صورتی که کلمه کامل شود (همه حروف آن نوشته شود)، نفر دوم برنده خواهد بود.
• و اگر آن حرف در کلمه موجود نباشد، آن حرف را در اولین جای خالی از سمت چپ، زیر پاره‌خط‌ها یادداشت می‌کند. اگر به‌علت پر بودن فضای زیر پاره‌خط‌ها، نفر اول نتواند آن حرف را یادداشت کند (یعنی نفر دوم تا پیش از این حرف، $n$ حرف اشتباه گفته باشد)، در این صورت نفر اول برنده و نفر دوم بازنده خواهد بود. در صورت برنده شدن نفر اول، او باید کلمه مورد نظر را در انتها به نفر دوم بگوید.

بعنوان مثال فرض کنید نفر اول (الف) کلمه RED را انتخاب کرده باشد و نفر دوم (ب) حروف D, C, E, A و R را به ترتیب انتخاب کرده باشد. شکل زیر گام های مختلف این بازی را نشان می دهد. دقت کنید که در این مثال نفر دوم برنده است؛ اما اگر در گام آخر نفر دوم، حرف S را انتخاب می‌کرد، بازنده بازی بود.

آیدین یکی از طرفدارهای پر و پا قرص این بازی می‌باشد. او به این می اندیشد که اگر واژه‌نامه به اندازه کافی بزرگ و دارای واژه‌های متناسب و خوبی باشد، نفر اول با انجام یک بازی ناجوانمردانه و تغییر کلمه در حین بازی، می‌تواند همیشه برنده بازی باشد؛ چرا که کلمه‌ی انتخاب شده جایی نوشته نمی‌شود و تنها نفر اول آن را به خاطر می‌سپارد. بنابراین او می‌تواند در حین بازی کلمه را به کلمه جدیدی که با پاسخ وی به حروف گفته شده توسط نفر دوم مطابقت دارد تغییر دهد. به عنوان مثال اگر واژه‌های RED, BED, LED و TED در واژه‌نامه موجود باشد او می تواند مطمئن باشد که نفر اول بعد از گام چهارم حتما برنده است.

در واقع از گام چهار به بعد، هر حرفی نفر دوم انتخاب کند، نفر اول آن را پایینِ پاره‌خط‌ها می گذارد و با این کار یکی از کلمات RED, BED, LED و TED را از دست می‌دهد و در انتها الزاماً حداقل یک کلمه دارد که با حالت نهایی سازگار بوده و آن را به نفر اول بگوید.

آیدین به این فکر می کند که اگر واژه‌نامه مناسب باشد، ممکن است حتی از همان ابتدا نفر اول برد خود را تضمین کند. به‌عنوان مثال اگر از کلمات دو حرفی برای این بازی استفاده شود و واژه‌نامه حاوی کلمات {ME,MD,DE,ED,AS,IS,AI,SI} باشد، نفر اول می‌تواند به‌گونه‌ای بازی کند که حتماً برنده شود. این‌که نفر اول چگونه بازی کند که برنده شود به شما واگذار می‌شود!

با فرض در اختیار داشتن واژه‌نامه از ابتدا، آیدین دوست دارد بداند آیا نفر اول می‌تواند با هر استراتژی اتخاذ شده توسط نفر دوم و جلوی هر بازی‌ِ نفر دوم، همواره برنده بازی باشد.

• ورودی شامل چند واژه‌نامه‌ی مستقل است. اولین خط ورودی عدد صحیح $C$ است که تعداد واژه‌نامه‌ها را مشخص می‌کند. در ادامه واژه‌نامه‌ها به‌صورت بلوک‌های جداگانه به دنبال هم ظاهر می‌شوند. می‌توانید فرض کنید $1\leq C \leq 20$ است.
• اولین خط هر واژه‌نامه، تعداد واژه‌ها ($K$) را مشخص می‌کند و به دنبال آن در خطوط بعدی واژه‌ها می‌آیند که با یک یا چند space, tab و break-line از هم جدا شده‌اند. واژه‌ها از حروف بزرگ انگلیسی تشکیل شده‌اند و هر کدام کمتر از ۷ حرف دارند. در ضمن در هیچ واژه‌ای حروف تکراری موجود نیست؛ به‌عبارت دیگر هر حرف حداکثر یک بار در هر واژه ظاهر شده است.
• می توانید فرض کنید اندازه فایل ورودی حداکثر ۵۰۰KB است.
• هیچ واژه‌نامه‌ای کم‌تر از یک و بیش‌تر از ۱۰۰۰ واژه ندارد.
• در ۲۰ درصد تست‌ها، تمام کلمات تمام واژه‌ها حداکثر ۳ حرف دارند و هر واژه‌نامه حداکثر شامل ۱۰۰ واژه است.
• در ۵۰ درصد تست‌ها، واژه‌ها حداکثر ۴ حرف دارند و هر واژه‌نامه حداکثر ۳۰۰ کلمه دارد.

برای هر یک از واژه‌نامه‌ها، باید یک خط حاوی Yes یا No چاپ شود. Yes در صورتی‌که نفر اول می‌تواند همواره و مستقل از آن‌که نفر دوم چگونه بازی کند، برنده شود؛ و No در غیر این صورت. به خاطر داشته باشید که نفر اول در انتهای بازی باید یک کلمه از واژه‌نامه را به نفر دوم بگوید که با تمام پاسخ‌هایی که او به حروف گفته شده توسط نفردوم داده، سازگار باشد.

• محدودیت زمان: ۵ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• سوال قبل