هر Deterministic Final-State Automation (بطورخلاصه DFA) یک گراف جهت‌دار است که هر راس آن یک ‎state‎ نامیده می‌شود و روی هر یال آن یک حرف الفبا نوشته شده است. هم‌چنین به ازای هر راس ‎$s$‎ حرف روی یال‌هایی که از آن خارج می‌شود متفاوت است. دقت کنید که امکان دارد تعدادی یال با حرف یکسان به یک راس وارد شوند.

هر ‎DFA‎ یک ‎state‎ شروع و تعدادی ‎state‎ پایان دارد. یک ‎DFA‎ یک رشته را می‌پذیرد اگر و فقط اگر یک گشت از ‎state‎ شروع آن به یکی از ‎state‎های پایان آن وجود داشته باشد که اگر حروف نوشته شده روی یال‌های آن را به ترتیب کنار هم بچینیم برابر با رشته مورد نظر شود.

زبان یک ‎DFA‎ مجموعه‌ای از رشته‌هایی است که آن ‎DFA‎ می‌پذیرد. به شما تعدادی رشته داده شده است، برنامه‌ای بنویسید که کمترین ‎$k$‎ای را بیابد که یک ‎DFA‎ با $k$ state وجود داشته باشد که زبان آن برابر با مجموعه رشته‌های ورودی باشد.

• در سطر اول ورودی ‎$1 \leq n \leq 5000$‎ نشانگر تعداد رشته‌های ورودی آمده است.
• در ‎$n$‎ سطر بعد در هر سطر یک رشته آمده است.‎

در تنها سطر خروجی جواب مسئله را چاپ نمایید.‎

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

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

‎‎ ‎ ‎‎