====== شَفَق ====== کابوس(($doom$):‎ حکم فَنا؛ که آخرین روشنی روز به‌هنگام غروب است‎(.‎ درس نظریه‌ی زبان‌ها و ماشین‌ها از محدوده‌ی خوابتان تجاوز کرده و تراوشات آن به این امتحان عملی نیز رسیده است. در یک گرامر مستقل از متن، یک متغیر را ‎«سازنده»‎ می‌نامیم، اگر با قرار دادن آن به‌عنوان متغیر شروع،بتوان به حداقل یک رشته‌ی نهایی (تنها شامل ترمینال‌ها) رسید. مثلاً در گرامر زیر، تنها متغیرهای ‎$D$‎ و ‎$E$‎ سازنده‌اند: {{ :سوالات_المپیاد:دوره‌ی_تابستان:دوره‌ی_۱۶:عملی:ششششششششششش.png |}}‎ حالا مسئله چیست؟ یک مسئله‌ی بسیار ساده ‎)‎مانند خیلی دیگر از مسائل نظریه‌ی زبان‌ها و ماشین‌ها!) برنامه‌ای بنویسید که با گرفتن یک گرامر مستقل از متن، متغیرهای سازنده‌ی آن را خروجی دهد. در گرامر ورودی این مسئله، الفبا (مجموعه‌ی ترمینال‌ها) شامل اعداد صحیح منفی بزرگ‌‌تر از ‎-1000‎ است. مجموعه‌ی متغیرها نیز با اعداد صحیح مثبت کوچک‌تر از ‎1000‎ نمایش داده می‌شود. ===== ورودی‎ ===== * در سطر اوّل، ‎$n$‎، تعداد قاعده‌های گرامر آمده است. * در هر یک از ‎$n$‎ سطر بعد، اطلاعات مربوط به یک قاعده آمده است.هر یک از این سطرها با شماره‌ی متغیر سمت چپ قاعده آغاز می‌شوند و در ادامه، شماره‌ی ترمینال‌ها و متغیرهای رشته‌ی سمت راست قاعده نوشته شده‌اند. هر سطر با یک $0$‎ پایان می‌یابد و اعداد این سطرها با یک فاصله از هم جدا شده‌اند. * ‎ $1 \leq n \leq 500$‎ و هر سطر شامل حداکثر ‎۲۰۰‎ عدد خواهد بود. ===== خروجی‎ ===== در تنها سطر خروجی، شماره‌ی متغیرهای سازنده‌ی گرامر را با یک فاصله از هم بنویسید. ===== محدودیت‌ها ===== * محدودیت زمان: ۱ ثانیه * محدودیت حافظه: ۲۵۶ مگابایت ‎ ===== ورودي و خروجي نمونه ===== ^ ورودي نمونه ^ خروجي نمونه ^ |8 \\ 1 2 0 \\ 1 3 4 0 \\ 2 2 -2 1 0 \\ 3 1 2 0 \\ 4 0 \\ 4 5 0 \\ 5 -2 4 0 \\ 5 1 0|4 5| * [[سوال ۵|سوال بعد]] * [[سوال ۳|سوال قبل]]