+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- پویان یک نوجوان تپل است که تصمیم گرفته است با درست کردن و خوردن معجون، وزن خود را کاهش دهد. پویان دستورالعمل ساخت تعدادی معجون را از بزرگان عرصه‌ی کاهش وزن دریافت کرده و قصد دارد آن‌ها را بسازد. هر معجون از ترکیب تعدادی چاشنی است که هر چاشنی یا یکی از مواد اولیه‌ی آشپزی است و یا نوعی معجون است. (که در صورت معجون بودن دستورالعمل خود را دارد.) برای ساخت یک معجون باید همه‌ی معجون‌های داخل چاشنی‌های آن را در ظرف‌های جدا آماده کرده، سپس یک ظرف خالی جدید برداشته و این معجون‌ها را در آن ریخته و مواد اولیه‌ی آشپزی را نیز اضافه کرده و با هم مخلوط کرد. نمیتوان معجون‌ها را در یکی از ظرف‌های خودشان باهم مخلوط کرد. پس از استفاده از چاشنی موجود در یک ظرف، ظرف خالی شده و میتوانیم از آن برای مخلوط کردن چاشنی‌های دیگر استفاده کنیم. برای مثال فرض کنید A (یک معجون) با ترکیب B (یک معجون) و namak (یک ماده‌اولیه) بوجود می‌آید. باید در ابتدا معجون B را در یک ظرف جدا درست کرد و یک ظرف خالی برداشته و در آن B و namak را قاطی کرده تا A در آن ظرف بوجود بیاید. حال ظرفی که قبل شامل B‌ بوده خالی است و میتوان از آن استفاده دیگر کرد! واضح است که تعداد ظرف‌های مورد نیاز پویان برای ساخت معجون، به ترتیب ساخت معجون‌های قبلی‌اش بستگی دارد. با ورودی گرفتن دستورالعمل، بگویید در ترتیبی که در آن از کمترین تعداد ظرف استفاده میشود، این کمترین تعداد ظرف چقدر است. **به ورودی‌های مثال‌ و توضیحاتشان توجه کنید!** # ورودی در سطر اول ورودی عدد $n$ آمده است که برابر تعداد معجون‌ها است. در $i$مین سطر از هریک از $n$ سطر بعدی ابتدا نام $i$مین معجون و سپس دستورالعمل آن آمده‌ است. در ابتدای دستورالعمل عدد $k_i$ آمده که نمایانگر تعداد چاشنی‌های معجون $i$م است و پس از آن نام آن $k_i$ چاشنی آمده است. نام معجون‌ها بصورت کلمات حداکثر ۲۰ کاراکتری از حروف بزرگ انگلیسی در ورودی آمده‌اند. نام مواد اولیه آشپزی بصورت کلمات حداکثر ۲۰ کاراکتری از حروف کوچک انگلیسی در ورودی آمده‌اند. معجون‌ها اسامی مختلفی دارند و تضمین میشود هر معجونی در دستورالعمل ساخت دقیقن یک معجون دیگر استفاده میشود بجز معجون نهایی که در دستورالعمل ساخت هیچ معجونی استفاده نمیشود. همچنین میتوان همه‌ی معجون‌ها را ساخت؛ یعنی دنباله‌ی وابستگی از یک معجون به خودش وجود ندارد. تنها یک معجون نهایی وجود دارد که از آن در ساخت معجون‌های دیگر استفاده نمیشود. $$2 \le k_i \le 10$$ $$1 \le n \le 1000$$ # خروجی تنها سطر خروجی باید شامل تنها یک عدد باشد که برابر با کمترین تعداد ظرف است که پویان میتواند با استفاده از آن معجون‌ را درست کند. # مثال ## ورودی نمونه ۱ ``` 3 SOUP 3 CHIZ namak aab SABZI 2 piaz gharch CHIZ 2 morgh SABZI ``` ## خروجی نمونه ۱ ``` 2 ``` در این نمونه برای ساخت SOUP در ۲ ظرف، چنین میکنیم: ۱. با ترکیب piaz و gharch در ظرف شماره ۱، SABZI را میسازیم. ۲. با ترکیب morgh و SABZI در ظرف شماره ۲، CHIZ را میسازیم. (اکنون ظرف شماره‌ی ۱ با برداشتن SABZI از داخلش، خالی شد.) ۳. با ترکیب CHIZ و namak و aab‌ در ظرف شماره ۱،‌ SOUP را میسازیم. ## ورودی نمونه ۲ ``` 5 MILKSHAKE 4 bastani shir TAM MIVE MIVE 5 golabi moz havij khiar anbe TAM 2 CHIZ CHOCOLATE CHIZ 2 goody darchin CHOCOLATE 2 sharbat cocoa ``` ## خروجی نمونه ۲ ``` 3 ``` برای ساخت MILKSHAKE دلخواهمان،‌ حق انتخاب داریم که اول MIVE را درست کنیم و یا اول TAM‌ را، که پس از آن با ترکیبشان با shir و bastabi یک MILKSHAKE بسازیم. اگر اول MIVE را درست کنیم، به ۴ ظرف نیاز پیدا خواهیم کرد ولی اگر اول TAM را بسازیم و سپس MIVE را، با ۳ ظرف میتوانیم به هدف خود برسیم.

حل سؤال در بانک سؤالات