پیش‌زمینه:

در اکثر زبان‌ها مانند زبان فارسی کلمات مرکب وجود دارند. این نوع کلمات از یک ریشه تشکیل شده‌اند که به ابتدا و یا انتهای آن‌ها پیش‌وندها و یا پس‌وندهایی اضافه شده است. اما بسیار اتفاق می‌افتد که بیش از یک پس‌وند و پیش‌وند در ساخته شدن یک کلمه نقش دارند. (مانند: انقلابیگری، باهوشی، بی‌خردی و …)

اما هر پس‌وند یا پیش‌وندی، به همه‌ی کلمات نمی‌چسبد، بلکه اضافه شدن این پس‌وند‌ها و پیش‌وندها وابسته به نقش کلمه است. (مثلا پیش‌وند «بی» تنها به کلمه‌ای اضافه می‌شود که نقش اسمی داشته باشد.)

هنگام تحلیل صرفی کلمات لازم است این پس‌وند‌ها و پیش‌وند‌ها از داخل کلمه استخراج شوند.

در فایل ورودی یک کلمه نوشته شده است. این کلمه شامل تعدادی پس‌وند و پیش‌وند است. ریشه‌ی این کلمه دارای نقش خاصی است بنابراین تنها پس‌وند و یا پیش‌وندهای مطابق با این نقش می‌توانند به این ریشه اضافه شوند و بعد از اضافه شدن این پس‌وند یا پیش‌وند نقش کلمه تغییر یافته است و در مرحله‌ی بعد پس‌وند یا پیش‌وندهای مطابق با نقش جدید تنها می‌توانند اضافه شوند و این روند تا اضافه کردن آخرین پسوند یا پیش‌وند ادامه می‌یابد.

هدف از این مسئله این است که چک شود که آیا کلمه‌ی داده شده کلمه‌ای مجاز است یا نه؟ به این معنی که با توجه به نقش ریشه‌ی کلمه و تغییراتی که هر پس‌وند یا پیش‌وند در نقش کلمه می‌دهند، چک کند که آیا اصولا اضافه کردن پس‌وندها و پیش‌وندها به این طریق مجاز است یا نه؟

در سطر اول ای فایل تعداد کلمه‌ها $(1\leq N \leq 60)$ داده شده است. در $N$ سطر بعدی فایل در هر سطر دقیقا یک کلمه داده شده است. برای نشان دادن پس‌وند‌ها و پیش‌وندها از اعداد استفاده شده است. و به جای ریشه‌ی کلمه، نقش آن که یک حرف بزرگ انگلیسی است آمده است. همه اجزا (پس‌وند، پیش‌وند، نقش ریشه) با یک «/» از هم جدا شده‌اند. در هر کلمه مجموعا بیش‌تر از ۲۰۰ پس‌وند و پیش‌وند وجود ندارد. ولی طول هر کلمه لزوما کم‌تر از ۲۵۶ نیست و هیچ space اضافه‌ای در کلمات وجود ندارد.

در سطر بعدی فایل ورودی تعداد قواعد تغییر نقش $(M)$ داده شده است. در $M$ سطر بعدی فایل ۳ تایی‌هایی مانند $3\quad A \quad B$ داده شده‌اند که نشان می‌دهد پیش‌وند یا پس‌وند ۳، می‌تواند به کلمه‌ای با نقش $A$ اضافه شود و نقش آن را به $B$‌تغییر می‌دهد. تعداد نقش‌های ممکن برای کلمات حداکثر ۱۰ است که با حروف $A,B,…,J$ مشخص می‌شوند.

در سطر اول این فایل تعداد کلمه‌ها و در سطرهای بعدی در هر سطر یکی از عبارات valid یا invalid وجود دارد که نشان می‌دهد آیا کلمه‌ی مربوطه معتبر و یا نامعتبر است.

کلمه‌ی $1/A/3/2$ معتبر است چون مسیر زیر وجود دارد:

$\quad\quad$کلمه $\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad$ نقش کلمه

$\quad\quad\quad$ $A$ $\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad$ $A$

$\quad\quad\quad$ $A/3$ $\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad$ $B$

$\quad\quad\quad$ $1/A/3$ $\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad $ $A$

$\quad\quad\quad$ $1/A/3/2$ $\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad $ $C$

• سوال بعد
• سوال قبل